Статья 291

Следующей будет исполняться команда. Если же не выполнено, проверяется в определении предусмотрено, что список альтернатив исчерпывающий.
Тьюринг показал, что теоретически достаточно рассматривать память как ленту, которая может неограниченно увеличиваться в одну сторону, а в каждой ячейке иметь либо 0, либо 1. Тогда единственные возможные действия - оставить содержимое ячейки тем же либо заменить его на противоположное. В книге собрано множество определений абстрактных машин, и каждое из них можно свести к другому подходящей кодировкой входов и выходов. Таким образом, любая функция, вычислимая на одной машине, вычислима и на другой конечно, если пренебречь размером требуемой памяти и временем работы машины.
Так появились важнейшие для применений логики понятия
функция - та, для которой имеется абстрактная машина, вычисляющая ее за конечное время,
разрешимая задача - та, для которой имеется машина, проверяющая за конечное число шагов для любых входных данных, имеется ли решение данной задачи, и, если имеется, строящая его,
неразрешимая задача - задача, для которой нет такой машины.