Петер Р. Рекурсивные функции

формат djvu
размер 2.85 МБ
добавлен 07 января 2011 г.

Издательство Иностранной литературы, Москва 1954 год.
Перевод с немецкого: В. А. Успенского
Под редакцией и с предисловием А. Н. Колмогорова

Переход от n к n+1 как способ определения теоретико-числовых функций
Рекурсивные функции и отношения
Возвратная рекурсия
Одновременная рекурсия
Рекурсия, при которой производится подстановка некоторой функции на место параметра
Рекурсия по многим переменным
Дальнейшие упрощения
Элементарные функции
Пример теоретико-числовой функции, не являющейся примитивно рекурсивной
Рекурсия со вставками
Диагональный метод и многократные рекурсии
Трасфинитные рекурсии
Рекурсии высших ступеней
Нормальная форма многократных рекурсий
"Гёделизация" рекурсий высших ступеней
Обще-рекурсивные функции
Явная форма обще-рекурсивных функций
Возможности дальнейшего упрощения явной формы
Пример функции, не являющейся обще-рекурсивной
Вычислимые функции
История и приложения
Невозможность эффективного решения проблемы: какие системы равенств определяют обще-рекурсивные функции
Вопрос общей разрешимости арифметических проблем
Расширения понятия рекурсивности. Применения к анализу
Литература

Похожие разделы

Смотрите также

Айзерман М.А., Гусев Л.А., Розоноэр Л.И., Таль А.А. Логика, автоматы, алгоритмы

формат djvu
размер 5.45 МБ
добавлен 13 марта 2009 г.

Категория: Математическая логика. Автор: Таль А. А. , Айзерман М. А. , Гусев Л. А. , Розоноер Л. И. , Смирнова И. М. Название: Логика, автоматы, алгоритмы. Количество страниц: 556. Год издания: 1963. Издательство: Наука. ОГЛАВЛЕНИЕ. Элементы математической логики. Вводные замечания. Основные понятия. Исчисление высказываний. Об исчислении предикатов (двузначных). Технические приложения исчисления высказываний. Однотактные релейно-контактные схемы...

Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов

формат pdf
размер 528.46 КБ
добавлен 15 октября 2009 г.

Учебное пособие. - Улан-Удэ: Изд-во ВСГТУ, 2000 г. - 51 с. В учебном пособии рассмотрены основные понятия теории; формальные модели алгоритмов, дается классификация формальных грамматик, описаны используемые в практике программирования алгоритмы преобразования грамматик и синтеза автоматов. По каждому разделу приведен теоретический материал, даны методические рекомендации и примеры решения задач, а также задания для самостоятельной работы. Сод...

Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Части 1,2,3

формат djvu
размер 1.48 МБ
добавлен 05 мая 2010 г.

М.: МЦНМО, 1999-2000. Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. Начала теории множеств. Множества и мощности. Упорядоченные множества. Языки и исчисления. Логика высказываний. Исчисление высказываний. Языки первого порядка. Исчисление предикатов. Теории и модели. Вычислимые функции. Вычислимость, разрешимость и перечислимость. Универсальные функции и неразрешимость. Нумерации...

Головешкин В.А., Ульянов М.В. Теория рекурсии для программистов

формат djvu
размер 7.44 МБ
добавлен 07 апреля 2010 г.

М.: ФИЗМАТЛИТ, 2006. 296 с. Книга является учебным пособием по теории рекурсии в аспекте ее применения в области проrраммирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алrоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алrоритмов, разработанных на основе рекуррентных соотношений, метода декомпозиции и метода динамичес...

Лекции - Теория алгоритмов

Статья

формат pdf
размер 43.93 МБ
добавлен 04 февраля 2012 г.

Автор не известен. 136 с. Лекции в виде презентации. Содержание. - Алгоритмы в математике. Основные черты алгоритмов. Числовые функциии алгоритмы их вычисления. Примитивно рекурсивные функции. - Частично рекурсивные функции.Тезис Черча. - Машины Тьюринга и машины с неограниченными регистрами. Вычислимость частично рекурсивных функций на МНР. - Нумерации и универсальные функции. - Нормальные алгорифмы. - Алгоритмические проблемы в логике и матем...

Мальцев А.И. Алгоритмы и рекурсивные функции

формат djvu
размер 3.46 МБ
добавлен 23 января 2009 г.

2-е изд. М.: Наука, 1986. -368с. Посвящается одному из актуальных и бурно развивающихся разделов математической логики - теории алгоритмов, а также важнейшим ее связям с другими разделами математики.

Марченков С.С. Элементарные рекурсивные функции

формат djvu
размер 939.59 КБ
добавлен 31 октября 2010 г.

М.: МЦНМО, 2003. - 112 с. Книга написана на основе курсов лекций, которые автор читал на факультете Вычислительной математики и кибернетики МГУ. В книге собраны основное классы «элементарных» рекурсивных функций, изучаемые в теории алгоритмов. Приведены различные определения этих классов, установлены соотношения включения между ними. Получены разнообразные канонические представления элементарных функций, указаны эффективные операции, сохраняющие...

Основы математической логики и теории алгоритмов

формат doc
размер 1.96 МБ
добавлен 22 октября 2009 г.

Автор неизвестен. Конспект лекций по курсу "Матем. логика и теория алгоритмов". 2008 год. - 80 стр. Исчисления высказываний. Определение формального исчисления. Исчисление высказываний генценовского типа. Эквивалентность формул. Нормальные формы. Семантика исчисления секвенций. Исчисление высказываний гильбертовского типа. Алгоритмы проверки общезначимости и противоречивости в ИВ. Логика и исчисления предикатов. Алгебр. системы. Формулы сигнатуры...

Подзоров С.Ю. Теория алгоритмов. Полный конспект лекций по курсу

формат pdf
размер 1002.44 КБ
добавлен 25 ноября 2010 г.

Новосибирск: НГУ, 2005. - 130 с. Курс по теории алгоритмов является составной частью дисциплины "Математическая логика", читаемого на 2-3 курсах механико-математического факультета НГУ. В настоящем курсе подробно рассматриваются конечные автоматы и языки, рекурсивные функции и понятие вычислимости, вопросы сложности вычислений.

Шпоры

Шпаргалка

формат htm
размер 150.58 КБ
добавлен 27 июня 2011 г.

Ответы на вопросы: Машина Тьюринга. Конструирование МТ. Вычислимые по Тьюрингу функции: ПРФ, ЧРФ. Правильная вычислимость. Уточнение понятия алгоритма через машину с неограниченными регистрами. нормальные алгоритмы Маркова. Вычислимые функции и разрешимые множества: вычислимость, разрешимость, перечислимость, множество n-ок нат чисел, диагональная конструкция, главные универсальные функции, универсальная ОРФ, перечислимое неразрешимое множество.r...