Теория вычислимости

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение вычислимых функций, данное Геделем, носило синтаксический характер, и лишь установление совпадения этого класса с классом общерекурсивных функций (вместе с формулировкой и «принятием» тезиса Черча) показало действительную значимость теоремы о неполноте. Ершов, Юрий Леонидович

В настоящее время исследования по теории вычислимости активно ведутся во всех странах мира. Россия всегда была одним из мировых центров исследований по теории вычислимости и её приложениям. Эти исследования берут начало от ранних работ Маркова и Мальцева по теории алгоритмов и её связям с алгеброй, ознаменовались решением проблемы Поста Мучником. Эти исследования сегодня продолжаются на очень высоком уровне во многих научных центрах России (школа Ершова в Новосибирске, школа Арсланова в Казани) и других стран бывшего Советского Союза (Алма-Ата, Казахстан).[источник не указан 265 дней]

См. также[править | править вики-текст]

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

Ссылки[править | править вики-текст]