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

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

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

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

• Курт Гёдель
• Алан Тьюринг
• Стивен Клини
• Алонзо Чёрч
• Эмиль Пост

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

نظرية الحسوبية | Teorie vyčíslitelnosti | Berechenbarkeitstheorie | Computability theory (computer science) | Teoría de la computabilidad | نظریه محاسبه‌پذیری | Calculabilité | Teoria della calcolabilità | 計算可能性理論 | 계산 가능성 이론 | Berekenbaarheid | Teoria obliczalności | Computability theory | ทฤษฎีการคำนวณได้