В недерминированной машине Тьюринга существуют команды с одинаковыми левыми частями и разными правыми:
В недерминированной машине Тьюринга управляющая головка стоит на месте, а движется лента:
Внутренний алфавит машины Тьюринга - набор символов, которые располагаются на ленте машины Тьюринга:
Для задания машины Тьюринга необходимо задать один входной алфавит:
Заключительное состояние машины Тьюринга - состояние, в котором происходит остановка машины:
Класс примитивно-рекурсивных функций строго содержится в классе частично-рекурсивных:
Команда машины Тьюринга указывает только направление движения управляющей головки:
Любой алгоритм может быть всегда сведен к численному алгоритму:
Машина Тьюринга - чисто техническое понятие:
Область применимости алгоритма А - совокупность тех объектов, к которым он применим:
При построении примитивно-рекурсивных функций используется только один оператор рекурсии:
Программа машины Тьюринга - конечное непустое множество попарно согласованных команд:
Программы работы машины Тьюринга можно задать в виде таблицы:
Условия любой задачи могут быть однозначно заданы с помощью ее Геделевского номера:
Частично рекурсивная функция может быть получена из исходных с помощью применения конечного числа раз подстановок, примитивных рекурсий и мю-оператора: