Вычислимые функции. 
Машина Тьюринга и невычислимые функции

Вычислимая функция — это такая функция, вычисление значений которой может быть проведено с помощью заранее заданного алгоритма.

«Вычислимые по Тьюрингу» функции — это функции, вычисляющимся на машинах Тьюринга.

Машина Тьюринга и алгоритмически неразрешимые функции

За время своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем.

Успехи математики к концу XIX века привели к формированию мнения, которое выразил Д. Гильберт — «в математике не может быть неразрешимых проблем», в связи с этим формулировка проблем Гильбертом на конгрессе 1900 года в Париже была руководством к действию, констатацией отсутствия решений в данный момент.

Первой фундаментальной теоретической работой, связанной с доказательством алгоритмической неразрешимости, была работа Курта Гёделя — его известная теорема о неполноте символических логик. Это была строго формулированная математическая проблема, для которой не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем был значительно расширен. Сегодня принято при доказательстве алгоритмической неразрешимости некоторой задачи сводить ее к ставшей классической задаче — «задаче останова» .