Вопрос 31

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

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

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

Это достигается путем кодирования конфигурации и программы любой данной машины Тьюринга в символах входного (внешнего) алфавита универсальной машины. Само кодирование должно выполняться следующим образом:

1) различные буквы должны заменяться различными кодовыми группами, но одна и та же буква должна заменяться всюду, где бы она ни встречалась, одной и той же кодовой группой;

2) строки кодовых записей должны однозначным образом разбиваться на отдельные кодовые группы;

3) должна иметь место возможность распознать, какие кодовые группы соответствуют различным сдвигам, т. е. каждой из букв Л, П, С в отдельности, и различать кодовые гру 2>Таким образом, если какая-либо машина Тьюринга Т решает некоторую задачу, то и универсальная машина Тьюринга способна решить эту задачу при условии, что кроме кодов исходных данных этой задачи на ее ленту будет подан код программы машины Т. Задавая универсальной машине Тьюринга Тu изображение программы любой данной машины Тьюринга Тn и изображение любого ее входного слова xn, получим изображение выходного слова уn, в которое машина Тn переводит слово xn.

Если же алгоритм, реализуемый машиной Тn, не применим к слову xn, то алгоритм, реализуемый универсальной машиной Тu, также не применим к слову, образованному из изображения xn и программы машины Тn.

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

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

1) для описания состояний устройства управления специальной машины Тьюринга, реализующей соответствующий алгоритм;

2) для описания программы, подаваемой на ленту универсальной машины Тьюринга, при реализации соответствующего алгоритма.

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

Вопрос 32

Композиции машин Тьюринга

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

Операции композиции, выполняемые над алгоритмами, позволяют образовы-вать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга—алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию.

Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и

cоответственно Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1, ...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключитель-ный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2.

Произведение машины T1 на машину Т2 обозначается через Т = T1 • T2, или Т = T1 * Т2. Таким образом, машина Т есть произведение машин Т1 и T2, если последовательная работа этих двух машин эквивалентна работе одной машины Т.