Теория вычислимости: различия между версиями

Теория вычислимости берёт своесвоё начало от диссертации [[Тьюринг]]а ([[1936]]), в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о [[проблема остановки|неразрешимости задачи о её остановке]]. Знаменитая [[теорема Гёделя о неполноте]] ([[1931]]) была доказана в терминах [[Рекурсивная функция (теория вычислимости)#Примитивно рекурсивные функции|примитивно рекурсивных функций]], класс которых в [[1934 год]]у [[Гёдель, Курт|Гёдель]] расширил до класса [[Рекурсивная функция (теория вычислимости)#Общерекурсивная функция|общерекурсивных функций]]. Формализм, развитый Гёделем, оказался эквивалентным тьюринговскому (а также многим другим). Вместе с [[Тезис Чёрча — Тьюринга|Тезисом Чёрча — Тьюринга]] этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций.