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

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

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

В последнее десятилетие ведётся большая работа по уточнению терминологии теории. В частности, термины «рекурсивная функция» и «рекурсивно перечислимое множество» заменяются на «вычислимая функция» и «вычислимо перечислимое множество».

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

Следует выделить: Теорему Райс, Проблему Останова


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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home