Основные свойства машины Тьюринга

На примере машины Тьюринга хорошо прослеживаются свойства алгоритмов.

Дискретность. Машина Тьюринга может перейти к (к + 1) шагу только после выполнения каждого шага, т.к. именно каждый шаг определяет, каким будет (к + 1) — й шаг.

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

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

Результативность. Содержательно результаты каждого шага и всей последовательности шагов определены однозначно, следовательно, правильно написанная машина Тьюринга за конечное число шагов перейдет в состояние q0, т. е. за конечное число шагов будет получен ответ на вопрос задачи.

Массовость. Каждая машина Тьюринга определена над всеми допустимыми словами из алфавита, в этом и состоит свойство массовости. Каждая машина Тьюринга предназначена для решения одного класса задач, т. е. для каждой задачи пишется своя (новая) машина Тьюринга.