Стоит задача определения результативности алгоритма, которая является необходимым условием для реализации.
Определение. РЕЗУЛЬТАТИВНОСТЬ – есть получение результата за конечное время (конечное число шагов).
ПРОБЛЕМА ОСТАНОВКИ

Необходимо решить задачу: по любому алгоритму машины Тьюринга и данным (состояние ленты машины Тьюринга) определить приведут ли вычисления функции к некоторому результату (машина Тьюринга остановится) или нет (машина Тьюринга не остановится).
Для решения поставленной задачи необходимо построить некоторый алгоритм (машину Тьюринга) такой, что в результате вычисления функции даст истину, если машина Тьюринга останавливается, или лож, если не останавливается.

То есть мы должны построить машину Тьюринга , которая для любой машины Тьюринга и любых исходных данных для этой машины Тьюринга определит останавливается ли или нет. Такая задача получила название ПРОБЛЕМА ОСТАНОВКИ.