ЛЕКЦИЯ 6. ИСПОЛЬЗОВАНИЕ МАШИН ТЬЮРИНГА ДЛЯ ОБОСНОВАНИЯ УНИВЕРСАЛЬНОСТИ ЯЗЫКА ПРОГРАММИРОВАНИЯ.

Первый язык программирования создала соратница Ч. Бэббеджа Ада Ловлейс (дочь великого английского поэта Байрона). В языке А. Ловлейс были три оператора:

q присвоить (=)

q проверить условие (Если … То …)

q перейти (goto …)

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

Рассмотрим правило

Qj b ® Qi a R.

Его программная реализация такова:

again:

прочитать_символ(X);

Если (X=b) & (Состояние=Qj) То

{

Cостояние= Qi

Записать_символ (a)

Перейти_к_следующей_ячейке

Goto again

}

Else

//Делать обработку других правил

В данном примере предполагается, что команды прочитать_символ, записать_символ, перейти_к_следующей_ячейке понятны вычислительной машине. Первые две - прочитать_символ, записать_символ - это команды чтения/записи. Проблема состоит в том, что лента машины Тьюринга предполагается бесконечной, а память ЭВМ конечна (хотя и очень велика). Таким образом, современные машины моделируют машину Тьюринга с конечной лентой, что, разумеется, делает возможности ЭВМ даже меньшими, чем возможности машин Тьюринга, несмотря на всю простоту последних ! Команда перейти_к_следующей_ячейкесоответствует увеличению счетчика адреса команд и реализуется в современных ЭВМ аппаратно.

Ниже приведен код на языке Паскаль для реализации машины Тьюринга (программа взята с бесплатного сайта рефератов). Входное слово и система команд машины записываются на диске c: в файле turing.txt. Сначала идет строка с указанием длины входного слова, затем (с новой строки) сама входная строка, затем (с новой строки) число команд машины Тьюринга и затем (с новой строки) – команды машины Тьюринга (каждая команда на отдельной строке). Пример команды:

2a3br

(читаем: если машина находится в состоянии 2 и читает символ a, то она переходитв состояние b , пишет символ b и двигает ленту вправо).

program turing;

uses crt;

var MT: array [0..300] of string [5]; {количество команд, состояния должны обозначаться одной буквой или цифрой}

{0 - начальное состояние, f - конечное состояние

MT[i][1] – состояние машины перед обработкой

MT[i][2] – старый (считанный) символ

MT[i][3] - новое состояние

MT[i][4] - новый символ

MT[i][5] - направление обработки ('r' - Right, 'l' - Left)}

inpstr: array [0..255] of char; {обрабатываемая запись на ленте}

idx: integer; {позиция текущего символа в обрабатываемой записи}

Lenrec: integer; {длина входной записи (считывается из входного файла)}

commandNumber: integer; {количество команд машины Тьюринга}

fil: text;

Symbol, State, dir : char;

i: integer;

begin

idx:=3;

Assign(fil,'C:\turing.txt');

Reset(fil);

Readln(fil,Lenrec); //читаем длину входной записи

for i:=0 to Lenrec-1 do

Read(fil, inpstr[i]); //читаем саму запись

Readln(fil);

Readln(fil,commandNumber); //читаем число команд

for i:=0 to commandNumber-1 do

Readln(fil,MT[i]); //читаем сами команды

CloseFile(fil);

Symbol:=inpstr[idx];

State:='0'; {начальное состояние '0'}

while (State <> 'f')

do {и заканчиваем состоянием f}

begin

for i:=0 to commandNumber-1 do

{поиск нужной команды по состоянию и текущему символу}

if (State=MT[i][1]) and (Symbol=MT[i][2]) then

begin

State:=MT[i][3];

inpstr[idx]:=MT[i][4];

dir:=MT[i][5];

if dir='r' then

idx:=idx+1;

if dir='l' then

idx:=idx-1;

break;

end;

Symbol:=inpstr[idx];

end;

writeln(inpstr);

readln;

end.