Полнота формализаций вычислимости. Различные описания были в свое время построены исходя из различных интуитивных представлений о том, каков весь класс вычислимых функций. При этом они привели к одному понятию вычислимости! Последнее утверждение (называемое также “тезисом Черча”) не может быть доказано, но подтверждается всей математической и вычислительной практикой: разные компьютеры могут вычислять одно и то же семейство функций. Каким бы ни был язык программирования, на нем можно написать программу только вычислимой функции (и, как правило, любой функции).

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