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

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