Восходит к Давиду Гильберту На рубеже 20 века сформулировал мировую проблему

Функции, вычислимые алгоритмом

• алгоритм не определяется формально, а существует как бы в виде «всем понятной механической процедуры».
• Любая функция, вычислимая на интуитивном (содержательном) уровне, должна быть сконструирована из базовых

Вычислимые функции

• Говорят, что машина Тьюринга вычисляет функцию f(x1, x2, ..., xn), если выполняются следующие условия:

• 1) для любых x1, x2, ..., xn, принадлежащих области определения функции, машина Тьюринга из начальной конфигурации, имея на ленте представление аргументов, переходит в заключительную конфигурацию, имея на ленте результат (представление функции);
• 2) для любых x1, x2, ..., xn, не принадлежащих области определения функции, машина Тьюринга из начальной конфигурации работает бесконечно.
• Если начальная и заключительная конфигурации машины Тьюринга являются стандартными, то говорят, что машина Тьюринга правильно вычисляет функцию f.
• Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее.