Теория вычислимости: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Sonic86 (обсуждение | вклад) м добавил литературу |
Е |
||
Строка 1:
'''Теория вычислимости''', также известная как теория рекурсивных функций, — это раздел современной [[математика|математики]], лежащий на стыке [[Математическая логика|математической логики]], [[Теория вычислений|теории алгоритмов]] и [[Информатика|информатики]],
Теория вычислимости берёт своё начало от работы Алана [[Тьюринг]]а ([[1936]]) «On Computable Numbers, With An Application to Entscheidungsproblem», в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о [[проблема остановки|неразрешимости задачи о её остановке]]. Знаменитая [[теорема Гёделя о неполноте]] ([[1931]]) была доказана в терминах [[Рекурсивная функция (теория вычислимости)#Примитивно рекурсивные функции|примитивно рекурсивных функций]], класс которых в [[1934 год]]у [[Гёдель, Курт|Гёдель]] расширил до класса [[Рекурсивная функция (теория вычислимости)#Общерекурсивная функция|общерекурсивных функций]]. Формализм, развитый Гёделем, оказался эквивалентным тьюринговскому (а также многим другим). Вместе с [[Тезис Чёрча — Тьюринга|Тезисом Чёрча — Тьюринга]] этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций.
| |||