Определение. ДАТЕРМЕНИРОВАННОЙ МАШИНОЙ ТЬЮРИНГА называется такая машина Тьюринга, у которой отображение множества декартового произведения множеств алфавита ленты и состояния устройства управления в множество декартового произведения множеств алфавита ленты, состояния устройства управления и множества перемещения ленты – функционально, то есть не существует двух одинаковых команд в множестве с одинаковой левой частью.
Определение. НЕДЕТЕРМЕНИРОВАННОЙ МАШИНОЙ ТЬЮРИНГА называется такая машина Тьюринга в системе команд которой имеются команды с одинаковой левой частью.

ПРЕДСТАВЛЕНИЕ НЕДЕТЕРМЕНИРОВАННОЙ МАШИНЫ ТЬЮРИНГА
В ВИДЕ ДЕТЕРМЕНИРОВАННОЙ МАШИНЫ ТЬЮРИНГА

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