| abstract
| - Теория вычислимости — раздел современной математики и теории вычислений, возникший в результате изучения понятий вычислимости и невычислимости; изначально была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений; сейчас поле исследования расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической логикой, где вместо вычислимости и невычислимости исследуется доказуемость и недоказуемость (выводимости и невыводимости) утверждений в рамках каких-либо теорий; берёт свое начало от диссертации Тьюринга (1936), в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о неразрешимости задачи о её остановке. Знаменитая теорема Гёделя о неполноте (1931) была доказана в терминах примитивно рекурсивных функций, класс которых в 1934 году Гёдель расширил до класса общерекурсивных функций. Формализм, развитый Гёделем оказался эквивалентным тьюринговскому (а также многим другим). Вместе с Тезисом Чёрча — Тьюринга этот факт явно продемонстрировал содержательность новой теории, и сейчас эти определения общеприняты в качестве формального аналога алгоритмически вычислимых функций. Определение вычислимых функций, данное Геделем, носило синтаксический характер, и лишь установление совпадения этого класса с классом общерекурсивных функций (вместе с формулировкой и «принятием» тезиса Черча) показало действительную значимость теоремы о неполноте. Ю.Л. Ершов В настоящее время исследования по теории вычислимости активно ведутся во всех странах мира. Россия всегда была одним из мировых центров исследований по теории вычислимости и её приложениям. Эти исследования берут начало от ранних работ Маркова и Мальцева по теории алгоритмов и её связям с алгеброй, ознаменовались решением проблемы Поста Мучником. Эти исследования сегодня продолжаются на очень высоком уровне во многих научных центрах России и других странах бывшего Советского Союза, таких, как Новосибирск, Казань, Алма-Ата и другие. Следует выделить: Теорему Райс, Проблему Останова Математики, заложившие основы теории вычислимости:
* Курт Гёдель
* Алан Тьюринг
* Стивен Клини
* Алонзо Чёрч
* Эмиль Пост
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)