Машина Тюрінга (лабораторна)

Лабораторна робота №3

МАШИНА ТЮРІНГА

Мета: Вивчити основні поняття алгоритмічної системи Тюрінга, і закріпити навички по створенню алгоритмів в даній системі.

Завдання: 1.  Побудувати машину Тьюринга і написати програму, яка в алфавіті Х{0,1,2,3,4,5,6,7} виконує операцію додавання 1 до натурального числа n, записаного в восьмирічній системі счислення.

Виконання роботи:

Uses crt;

Type c=array[1..15] of string;

Const a : c=(‘#’,’2′,’6′,’6′,’6′,’2′,’7′,’#’,’#’,’#’,’#’, ‘#’,’#’,’#’,’#’);

N=50;

Var i,k,m,s,flag : integer;

x1,x2,x4,x5,x6,q: string;

kom : array[1..N] of string;

BEGIN

clrscr;

m:=7;

q:=’1′;

kom[1]:=’10>11S’;

kom[2]:=’11>12S’;

kom[3]:=’12>13S’;

kom[4]:=’13>14S’;

kom[5]:=’14>15S’;

kom[6]:=’15>16S’;

kom[7]:=’16>17S’;

kom[8]:=’17>10L’;

kom[9]:=’1#>11S’;

Repeat

flag:=0; s:=s+1;

For i:=1 to N do

begin

x1:=copy(kom[i],1,1);

x2:=copy(kom[i],2,1);

x4:=copy(kom[i],4,1);

x5:=copy(kom[i],5,1);

x6:=copy(kom[i],6,1);

If (flag=0)and(x1=q)and(x2=a[m]) then

begin

q:=x4;

a[m]:=x5;

If x6=’R’ then

m:=m+1;

If x6=’L’ then

m:=m-1;

If x6=’S’ then

break;

flag:=1;

end;

end;

k:=k+1;

For i:=1 to 15 do

write(a[i],’ ‘);

writeln(‘   q=’,q,’   k=’,k);

delay(50);

sound(1000);

Delay(50);

Nosound;

For i:=1 to m-1 do

write(‘==’);

write(‘|’);

writeln;

until x6=’S’;

Readkey;

END.

Результат роботи:

# 2 6 6 6 2 0 # # # # # # # #    q=1   k=1

==========|

# 2 6 6 6 3 0 # # # # # # # #    q=1   k=2

==========|

Висновок: виконуючи цю лабораторну роботу я вивчила поняття алгоритмічної системи Тьюрінга, і закріпила навички по створенню алгоритмів в даній системі.

Звіт і програма здані викладачеві.