Теория вычислимости
Материал из Википедии — свободной энциклопедии
Теория вычислимости — это раздел математической логики, возникший из изучения вычислимых функций и Тьюринговых степеней. Сейчас поле исследования теории вычислимости расширилось, включив в себя изучение обобщённой вычислимости и определимости.
Знаменитая теорема Гёделя о неполноте, доказанная в 1931 году, привлекла внимание к классу примитивно рекурсивных функций, которые в 1934 году Гёдель расширил до класса общерекурсивных функций. Эквивалентные определения были даны в середине 1930-х годов Клини, Тьюрингом и другими. В соответствии с Тезисом Чёрча эти определения принимаются за описание класса алгоритмически вычислимых функций.
В последнее десятилетие ведётся большая работа по уточнению терминологии теории. В частности, термины «рекурсивная функция» и «рекурсивно перечислимое множество» заменяются на «вычислимая функция» и «вычислимо перечислимое множество».
В настоящее время исследования по теории вычислимости активно ведутся во всех странах мира. Россия всегда была одним из мировых центров исследований по теории вычислимости и её приложениям. Эти исследования берут начало от ранних работ Маркова и Мальцева по теории алгоритмов и её связям с алгеброй, ознаменовались решением проблемы Поста Мучником. Эти исследования сегодня продолжаются на очень высоком уровне во многих научных центрах России и других стран бывшего Советского Союза, таких, как Новосибирск, Казань, Алма-Ата и другие.
Следует выделить: Теорему Райс, Проблему Останова
Математики, заложившие основы теории вычислимости:
 |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
