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

В заключение опишем, что такое универсальная машина Тьюринга. В обычной машине Тьюринга программа «зашита» в устройство управления, а входная информации (условия задачи) записывается на бесконечной ленте. В универсальной машине в устройстве управления записана программа, реализующая алгоритм подражания, т. е. программную реализацию правил работы любой машины (см. п.15.2), вернее, правила обращения с ее программой. Тогда входной информацией для универсальной машины является па­ра - слово и_т, стандартно кодирующее машину-алгоритм, решающий данный класс задач Z; и слово v_z, кодирующее условие задачи . Универсальная машина, используя и_т, перерабатывает v_z в T(v_z).

Ясно, что для построения универсальной машины потребуется использование техники машин с полулентами и универсального алфавита. Эта машина будет работать очень «вяло», теряя очень много времени на переходы от обрабатываемого слова к программе и обратно, однако ясно, что справедлива следующая теорема.

Теорема 15.11 Универсальная машина Тьюринга существует.

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