Универсальная машина Тьюринга

Систему команд машины Тьюринга можно интерпретировать и как описание работы конкретного механизма, и как программу, управляющей работой механизма МТ. Обе интерпретации используют на практике. Для современного инженера это обстоятельство вполне естественно. Он хорошо знает, что любой алгоритм управления может быть реализован либо аппаратурно – построением соответствующей схемы, либо программно – написанием программы для универсальной управляющей ЭВМ. В одном случае МТ «запаивается» в электронную схему (часто такой подход применяется в военной технике). Во втором случае мы имеем дело с привычной практикой – разработки приложений на ЭВМ.

Интуитивно понятно, что правильная система команд МТ, если не делать ошибок, однозначно приводит к конечному результату. Это по существу уверенность в существовании алгоритма воспроизведения работы исполнительного механизма машины Тьюринга.

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

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

• Построить машину Тьюринга U, вычисляющую функцию от двух переменных, и такую, что для любой машины T с системой команд , справедливо , если определена и не останавливается, если не останавливается.

Любую МТ U, обладающую указанными свойствами называют универсальной машиной Тьюринга.

Лекция 3