Теория вычислимости , также известная как теория рекурсивных функций, — это раздел современной математики , лежащий на стыке математической логики , теории алгоритмов и информатики , возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений . В наши дни поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической логикой , где вместо вычислимости и невычислимости идёт речь о доказуемости и недоказуемости (выводимости и невыводимости) утверждений в рамках каких-либо теорий.

Теория вычислимости берёт своё начало от работы Алана Тьюринга ( 1936 ) «On Computable Numbers, With An Application to Entscheidungsproblem», в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о неразрешимости задачи о её остановке . Знаменитая теорема Гёделя о неполноте ( 1931 ) была доказана в терминах примитивно рекурсивных функций , класс которых в 1934 году Гёдель расширил до класса общерекурсивных функций . Формализм, развитый Гёделем, оказался эквивалентным тьюринговскому (а также многим другим). Вместе с тезисом Чёрча — Тьюринга этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций.

Математики, заложившие основы теории вычислимости

• Курт Гёдель
• Алан Тьюринг
• Стивен Клини
• Алонзо Чёрч
• Эмиль Пост

См. также

• Теорема Райса
• Проблема остановки

Литература

• Булос Дж., Джеффри Р. Вычислимость и логика. — М. : Мир, 1994. — 396 с.
• Ершов Ю.Л. Теория нумераций. — М. : Наука, 1977. — 416 с.
• Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.. — М. : Мир, 1986. — 256 с.
• Клини. Введение в метаматематику. — М. : Издательство иностранной литературы, 1957. — 526 с.
• Мальцев А.И. Алгоритмы и рекурсивные функции. — М. : Наука, 1965. — 392 с.
• Манин Ю.И. Вычислимое и невычислимое. — М. : Советское радио, 1980. — 128 с.
• Минский М. Вычисления и автоматы. — М. : Мир, 1971. — 366 с.
• Ходжерс Х. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 624 с.
• Барвайс Дж. Справочная книга по математической логике в четырёх частях. Часть III. Теория рекурсии.. — М. : Наука, 1982. — 360 с.
• Успенский В.А. Лекции о вычислимых функциях. — М. : Физматгиз, 1960. — 492 с.
• Успенский В.А., Семёнов Л.А. Теория алгоритмов: основные открытия и приложения. — М. : Наука, 1987.
• Шенфилд Дж. Степени неразрешимости. — М. : Наука, 1977. — 192 с.

Ссылки

Для улучшения этой статьи желательно : Оформить статью по правилам . Найти и оформить в виде сносок ссылки на независимые авторитетные источники , подтверждающие написанное . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.