МАШИНЫ ПОСТА И ТЬЮРИНГА

Задача 1.

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

Алгоритм вычитания целых чисел для машины Поста приведен ниже. В первых двух строчках указывается положение каретки и состояние ленты, на которой в унарной системе счисления записаны два числа (в данном случае 6 и 4). В результате исполнения программы на ленте останется число 2 в унарной системе счисления.

                                              
7                      -- координата каретки 
VVVVVV-VVVV-------------------------   лента  
1 сместить влево, команда 2
2 если пусто -- команда 1, если метка -- команда 3 
3 удалить метку, команда 4
4 сместить вправо, команда 5
5 если пусто -- команда 4, если метка -- команда 6 
6 удалить метку, команда 7      
7 сместить вправо, команда 8
8 если пусто -- команда 9, если метка -- команда 1
9 остановить МП.

Используется программа ПР-1, результат - на рис. 1.

Программа ПР-1.

   Вычитание 6 - 2 = 4
V V V V V V - V V - - - - - - - - - - - - - - - - - - - - | 1 |
------------M
V V V V V V - V V - - - - - - - - - - - - - - - - - - - - | 2 |
----------M
V V V V V - - V V - - - - - - - - - - - - - - - - - - - - | 3 |
----------M
V V V V V - - V V - - - - - - - - - - - - - - - - - - - - | 4 |
------------M
V V V V V - - V V - - - - - - - - - - - - - - - - - - - - | 5 |
--------------M
V V V V V - - - V - - - - - - - - - - - - - - - - - - - - | 6 |
--------------M
V V V V V - - - V - - - - - - - - - - - - - - - - - - - - | 7 |
----------------M
V V V V V - - - V - - - - - - - - - - - - - - - - - - - - | 8 |
--------------M
V V V V V - - - V - - - - - - - - - - - - - - - - - - - - | 9 |
------------M
V V V V V - - - V - - - - - - - - - - - - - - - - - - - - | 10 |
----------M            
V V V V V - - - V - - - - - - - - - - - - - - - - - - - - | 11 |
--------M
V V V V - - - - V - - - - - - - - - - - - - - - - - - - - | 12 |
--------M
V V V V - - - - V - - - - - - - - - - - - - - - - - - - - | 13 |
----------M
V V V V - - - - V - - - - - - - - - - - - - - - - - - - - | 14 |
------------M
V V V V - - - - V - - - - - - - - - - - - - - - - - - - - | 15 |
--------------M
V V V V - - - - V - - - - - - - - - - - - - - - - - - - - | 16 |
----------------M
V V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 17 |
----------------M
V V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 18 |
------------------M
КОНЕЦ РАБОТЫ

Рис. 1. Вычитание целых чисел.

Задача 2.

Напишите компьютерную программу, моделирующую машину Поста, которая увеличивает целое число на 2.

Алгоритм увеличения целого числа на 2 представлен ниже:

3                            -- координата каретки 
VVVVVVV-----------------------------  лента 
1 сместить вправо, команда 2
2 если пусто - команда 3, если метка - команда 1 
3 поставить метку, команда 4
4 сместить вправо, команда 5
5 поставить метку, команда 6
6 остановить МП.

Для реализации этого алгоритма в процедуру Programma программы ПР-1 необходимо вставить следующий код:

x:=3;                           {координата головки} 
lenta:='VVVVVVV------------------------------------';
kom[1]:='right'; k[1]:=2;
kom[2]:='if';    k[2]:=3; kk[2]:=1;
kom[3]:='metka'; k[3]:=4;
kom[4]:='right'; k[4]:=5;
kom[5]:='metka'; k[5]:=6;
kom[6]:='stop';  k[6]:=0;

Результат работы программы -- на рис. 2. 

   Сложение 7 + 2 = 9
V V V V V V V - - - - - - - - - - - - - - - - - - - - - - | 1 |
----M
V V V V V V V - - - - - - - - - - - - - - - - - - - - - - | 2 |
------M
V V V V V V V - - - - - - - - - - - - - - - - - - - - - - | 3 |
--------M
V V V V V V V - - - - - - - - - - - - - - - - - - - - - - | 4 |
----------M
V V V V V V V - - - - - - - - - - - - - - - - - - - - - - | 5 |
------------M
V V V V V V V - - - - - - - - - - - - - - - - - - - - - - | 6 |
--------------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 7 |
--------------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 8 |
----------------M
V V V V V V V V V - - - - - - - - - - - - - - - - - - - - | 9 |
----------------M
КОНЕЦ РАБОТЫ

Рис. 2. Увеличение числа на 2

Задача 3.

Напишите компьютерную программу, моделирующую машину Поста, которая уменьшает целое число на 2.

Пусть на ленте машины Поста записано число 6, каретка находится напротив левой ячейки (координата x=1). Для вычитания из любого целого N числа 2 в процедуру Programma программы ПР-1 следует вставить следующий код: 

x:=1; lenta:='VVVVVV-------------------------------';
kom[1]:='right'; k[1]:=2; 
kom[2]:='if';    k[2]:=3; kk[2]:=1;
kom[3]:='left';  k[3]:=4; 
kom[4]:='erase'; k[4]:=5; 
kom[5]:='left';  k[5]:=6; 
kom[6]:='erase'; k[6]:=7; 
kom[7]:='stop';

Результат работы программы -- на рис. 3. 

  Вычитание 6 - 2 = 4
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 1 |
M
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 2 |
--M
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 3 |
----M
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 4 |
------M
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 5 |
--------M
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 6 |
----------M
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 7 |
------------M
V V V V V V - - - - - - - - - - - - - - - - - - - - - - - | 8 |
----------M
V V V V V - - - - - - - - - - - - - - - - - - - - - - - - | 9 |
----------M
V V V V V - - - - - - - - - - - - - - - - - - - - - - - - | 10 |
--------M
V V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 11 |
--------M
КОНЕЦ РАБОТЫ

Рис. 3. Уменьшение целого числа на 2

Задача 4.

Напишите компьютерную программу, моделирующую машину Поста, которая складывает два целых числа.

Программа сложения целых чисел на машине Поста выглядит так: 

5                             -- координата каретки 
VVVV-VVV------------------------------------- лента
1 поставить метку, команда 2    
2 сместить вправо, команда 3    
3 если пусто -- команда 4, если метка -- команда 2
4 сместить влево, команда 5
5 удалить метку, команда 6
6 остановить МП.

В программу ПР-1 следует вставить код:

x:=5;           {сложение двух чисел}
lenta:='VVVV-VVV------------------------------------';
komand[1]:='metka'; k[1]:=2;
komand[2]:='right'; k[2]:=3;
komand[3]:='if';    k[3]:=4; kk[3]:=2;
komand[4]:='left';  k[4]:=5;
komand[5]:='erase'; k[5]:=6;
komand[6]:='stop';  k[6]:=0;

Результат работы программы - на рис. 4. 

  Сложение 4 + 3 = 7
V V V V - V V V - - - - - - - - - - - - - - - - - - - - - | 1 |
--------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 2 |
--------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 3 |
----------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 4 |
------------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 5 |
--------------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 6 |
----------------M
V V V V V V V V - - - - - - - - - - - - - - - - - - - - - | 7 |
--------------M
V V V V V V V - - - - - - - - - - - - - - - - - - - - - - | 8 |
--------------M
КОНЕЦ РАБОТЫ

Рис. 4. Сложение двух целых чисел

Задача 5.

Напишите компьютерную программу, моделирующую машину Поста, которая умножает целое число на 2. 

x:=2; {Умножение числа на 2}
lenta:='-VVV-------------------------------------';
kom[1]:='right';  k[1]:=2;
kom[2]:='if';     k[2]:=3; kk[2]:=1;
kom[3]:='left';   k[3]:=4;
kom[4]:='erase';  k[4]:=5;
kom[5]:='right';  k[5]:=6;
kom[6]:='metka';  k[6]:=7;
kom[7]:='right';  k[7]:=8;
kom[8]:='metka';  k[8]:=9;
kom[9]:='left';  k[9]:=10;
kom[10]:='if';    k[10]:=11; kk[10]:=9;
kom[11]:='left';  k[11]:=12;
kom[12]:='if';    k[12]:=11; kk[12]:=13;
kom[13]:='erase'; k[13]:=14;
kom[14]:='left';  k[14]:=15;
kom[15]:='if';    k[15]:=20; kk[15]:=16;
kom[16]:='right'; k[16]:=17;
kom[17]:='if';    k[17]:=16; kk[17]:=18;
kom[18]:='right'; k[18]:=19;
kom[19]:='if';    k[19]:=6; kk[19]:=18;
kom[20]:='right'; k[20]:=21;
kom[21]:='if';    k[21]:=20; kk[21]:=22;
kom[22]:='right'; k[22]:=23;
kom[23]:='if';    k[23]:=24; kk[23]:=22;
kom[24]:='metka'; k[24]:=25;
kom[25]:='right'; k[25]:=26;
kom[26]:='metka'; k[26]:=27;
kom[27]:='stop';  k[28]:=0;

Результат решения представлен на рис. 5. Возможен другой способ решения:

x:=9; lenta:='-VVVVV---------------------------';
kom[1]:='metka'; k[1]:=2;
kom[2]:='right'; k[2]:=3;
kom[3]:='metka'; k[3]:=4;
kom[4]:='left';  k[4]:=5;
kom[5]:='if';    k[5]:=6; kk[5]:=4;
kom[6]:='left';  k[6]:=7;
kom[7]:='if';    k[7]:=6; kk[7]:=8;
kom[8]:='erase'; k[8]:=9;
kom[9]:='left'; k[9]:=10;
kom[10]:='if'; k[10]:=15; kk[10]:=11;
kom[11]:='right'; k[11]:=12;
kom[12]:='if'; k[12]:=11; kk[12]:=13;
kom[13]:='right'; k[13]:=14;
kom[14]:='if'; k[14]:=1; kk[14]:=13;
kom[15]:='stop'; k[15]:=0;


   Умножение 3 * 2 = 6
- V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 1 |
--M
- V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 2 |
----M
- V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 3 |
------M
- V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 4 |
--------M
- V V V - - - - - - - - - - - - - - - - - - - - - - - - - | 5 |
------M
- V V - - - - - - - - - - - - - - - - - - - - - - - - - - | 6 |
------M
- V V - - - - - - - - - - - - - - - - - - - - - - - - - - | 7 |
--------M
- V V - V - - - - - - - - - - - - - - - - - - - - - - - - | 8 |
--------M
- V V - V - - - - - - - - - - - - - - - - - - - - - - - - | 9 |
----------M
- V V - V V - - - - - - - - - - - - - - - - - - - - - - - | 10 |
----------M
- V V - V V - - - - - - - - - - - - - - - - - - - - - - - | 11 |
--------M
- V V - V V - - - - - - - - - - - - - - - - - - - - - - - | 12 |
------M
- V V - V V - - - - - - - - - - - - - - - - - - - - - - - | 13 |
----M
- V - - V V - - - - - - - - - - - - - - - - - - - - - - - | 14 |
----M
- V - - V V - - - - - - - - - - - - - - - - - - - - - - - | 15 |
--M
- V - - V V - - - - - - - - - - - - - - - - - - - - - - - | 16 |
----M
- V - - V V - - - - - - - - - - - - - - - - - - - - - - - | 17 |
------M
- V - - V V - - - - - - - - - - - - - - - - - - - - - - - | 18 |
--------M
- V - - V V - - - - - - - - - - - - - - - - - - - - - - - | 19 |
----------M
- V - - V V - - - - - - - - - - - - - - - - - - - - - - - | 20 |
------------M
- V - - V V V - - - - - - - - - - - - - - - - - - - - - - | 21 |
------------M
- V - - V V V - - - - - - - - - - - - - - - - - - - - - - | 22 |
--------------M
- V - - V V V V - - - - - - - - - - - - - - - - - - - - - | 23 |
--------------M
- V - - V V V V - - - - - - - - - - - - - - - - - - - - - | 24 |
------------M
- V - - V V V V - - - - - - - - - - - - - - - - - - - - - | 25 |
----------M
- V - - V V V V - - - - - - - - - - - - - - - - - - - - - | 26 |
--------M
- V - - V V V V - - - - - - - - - - - - - - - - - - - - - | 27 |
------M
- V - - V V V V - - - - - - - - - - - - - - - - - - - - - | 28 |
----M
- V - - V V V V - - - - - - - - - - - - - - - - - - - - - | 29 |
--M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 30 |
--M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 31 |
M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 32 |
--M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 33 |
----M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 34 |
------M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 35 |
--------M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 36 |
----------M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 37 |
------------M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 38 |
--------------M
- - - - V V V V - - - - - - - - - - - - - - - - - - - - - | 39 |
----------------M
- - - - V V V V V - - - - - - - - - - - - - - - - - - - - | 40 |
----------------M
- - - - V V V V V - - - - - - - - - - - - - - - - - - - - | 41 |
------------------M
- - - - V V V V V V - - - - - - - - - - - - - - - - - - - | 42 |
------------------M
КОНЕЦ РАБОТЫ

Рис. 5. Умножение целого числа на 2

Задача 6.

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

Используется программа ПР-2. Состояние ленты машины Тьюринга записывается в массиве:

c=('_','1','1','1','1','1','1',
       '_','_','_','_','_','_','_','_');

Положение головки определяется переменной m, исходное состояние машины Тьюринга - переменной q:

m:=2;     { положение головки } 
q:='1';

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

"(Состояние q1) (Читаю символ s1) ==>
(Новое состояние q2) (Напечатать символ s1)
(Сместить головку вправо (R), влево (L) или 
остановиться (S))"

Программа для машины Тьюринга, увеличивающая целое число на 2, состоит из 3 команд: 

kom[1]:='11>11R'; 
kom[2]:='1_>21R'; 
kom[3]:='2_>21S';

Результат ее использования -- на рис. 6.

Программа ПР-2.

_ 1 1 1 1 1 1 _ _  q=1   k=1
====|
_ 1 1 1 1 1 1 _ _  q=1   k=2
======|
_ 1 1 1 1 1 1 _ _  q=1   k=3
========|
_ 1 1 1 1 1 1 _ _  q=1   k=4
==========|
_ 1 1 1 1 1 1 _ _  q=1   k=5
============|
_ 1 1 1 1 1 1 _ _  q=1   k=6
==============|
_ 1 1 1 1 1 1 1 _  q=2   k=7
================|
_ 1 1 1 1 1 1 1 1  q=2   k=8
================|

Рис. 6. Увеличение целого числа на 2

Задача 7.

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

Пусть начальное состояние ленты машины Тьюринга: _11111_1111__ , головка находится напротив левой единицы. МТ находится в состоянии 1. Программа выглядит так:

q "1" "_"
1 2_R
2 21R 31R
3 31R 4_L
4 1_S

В программу ПР-2 следует вставить код:

c=('_','1','1','1','1','1','_','1','1','1','1',
'_','_','_','_'); 

m:=2; q:='1'; 
kom[1]:='11>11R'; 
kom[2]:='1_>21R'; 
kom[3]:='21>21R'; 
kom[4]:='2_>3_L'; 
kom[5]:='31>3_S';

Результат работы программы представлен на рис. 7. 

_ 1 1 1 1 1 _ 1 1 1 1 _ _ _ _  q=1   k=1
====|
_ 1 1 1 1 1 _ 1 1 1 1 _ _ _ _  q=1   k=2
======|
_ 1 1 1 1 1 _ 1 1 1 1 _ _ _ _  q=1   k=3
========|
_ 1 1 1 1 1 _ 1 1 1 1 _ _ _ _  q=1   k=4
==========|
_ 1 1 1 1 1 _ 1 1 1 1 _ _ _ _  q=1   k=5
============|
_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=2   k=6
==============|
_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=2   k=7
================|
_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=2   k=8
==================|
_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=2   k=9
====================|
_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=2   k=10
======================|
_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=3   k=11
====================|
_ 1 1 1 1 1 1 1 1 1 _ _ _ _ _  q=3   k=12
====================|

Рис. 7. Сложение целых чисел

Задача 8.

На ленте МТ - конечный набор единиц: _11111__. Напишите программу, которая ставит звездочки вместо первой и последней единицы, остальные стирает.

Пусть машина Тьюринга находится в состоянии 1. В компьютерную программу ПР-2 необходимо вставить следующий код: 

c=('_','1','1','1','1','1','1','1','1',
'1','1','_','_','_','_'); 

m:=1; q:='1'; 
kom[1]:='1_>1_R'; 
kom[2]:='2_>2_L'; 
kom[3]:='3_>3_S'; 
kom[4]:='11>21R'; 
kom[5]:='21>2*R'; 
kom[6]:='31>3*L'; 
kom[7]:='2*>3*L'; 
kom[8]:='3*>3_L';

Результат -- на рис. 8.

_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=1   k=1
==|
_ 1 1 1 1 1 1 1 1 1 1 _ _ _ _  q=2   k=2
====|
_ 1 * 1 1 1 1 1 1 1 1 _ _ _ _  q=2   k=3
======|
_ 1 * * 1 1 1 1 1 1 1 _ _ _ _  q=2   k=4
========|
_ 1 * * * 1 1 1 1 1 1 _ _ _ _  q=2   k=5
==========|
_ 1 * * * * 1 1 1 1 1 _ _ _ _  q=2   k=6
============|
_ 1 * * * * * 1 1 1 1 _ _ _ _  q=2   k=7
==============|
_ 1 * * * * * * 1 1 1 _ _ _ _  q=2   k=8
================|
_ 1 * * * * * * * 1 1 _ _ _ _  q=2   k=9
==================|
_ 1 * * * * * * * * 1 _ _ _ _  q=2   k=10
====================|
_ 1 * * * * * * * * * _ _ _ _  q=2   k=11
======================|
_ 1 * * * * * * * * * _ _ _ _  q=2   k=12
====================|
_ 1 * * * * * * * * * _ _ _ _  q=3   k=13
==================|
_ 1 * * * * * * * _ * _ _ _ _  q=3   k=14
================|
_ 1 * * * * * * _ _ * _ _ _ _  q=3   k=15
==============|
_ 1 * * * * * _ _ _ * _ _ _ _  q=3   k=16
============|
_ 1 * * * * _ _ _ _ * _ _ _ _  q=3   k=17
==========|
_ 1 * * * _ _ _ _ _ * _ _ _ _  q=3   k=18
========|
_ 1 * * _ _ _ _ _ _ * _ _ _ _  q=3   k=19
======|
_ 1 * _ _ _ _ _ _ _ * _ _ _ _  q=3   k=20
====|
_ 1 _ _ _ _ _ _ _ _ * _ _ _ _  q=3   k=21
==|
_ * _ _ _ _ _ _ _ _ * _ _ _ _  q=3   k=22
|
_ * _ _ _ _ _ _ _ _ * _ _ _ _  q=3   k=23
|

Рис. 8. Замена единиц на звездочки и пробелы

Задача 9.

На ленте МТ - конечный набор единиц: _111111__. Напишите программу, которая заменяет единицы звездочками. Головка - левее первой единицы.

Программа для машины Тьюринга имеет вид:

q "_" "1" "*"
1 1_R 3*R
2 2_L 2*R 3*L
3 3_S 2*R 3*L

Для решения этой задачи в программу ПР-2 следует вставить код: 

c=('_','_','1','1','1','1','1','1',
'1','1','1','1','_','_','_'); 

m:=1; q:='1';
kom[1]:='1_>1_R'; 
kom[2]:='2_>2_L'; 
kom[3]:='3_>3_S'; 
kom[4]:='11>3*R'; 
kom[5]:='21>2*R'; 
kom[6]:='31>2*R'; 
kom[7]:='2*>3*L'; 
kom[8]:='3*>3*L';

Результат работы программы представлен на рис.9. 

_ _ 1 1 1 1 1 1 1 1 1 1 _ _ _  q=1   k=1
==|
_ _ 1 1 1 1 1 1 1 1 1 1 _ _ _  q=1   k=2
====|
_ _ * 1 1 1 1 1 1 1 1 1 _ _ _  q=3   k=3
======|
_ _ * * 1 1 1 1 1 1 1 1 _ _ _  q=2   k=4
========|
_ _ * * * 1 1 1 1 1 1 1 _ _ _  q=2   k=5
==========|
_ _ * * * * 1 1 1 1 1 1 _ _ _  q=2   k=6
============|
_ _ * * * * * 1 1 1 1 1 _ _ _  q=2   k=7
==============|
_ _ * * * * * * 1 1 1 1 _ _ _  q=2   k=8
================|
_ _ * * * * * * * 1 1 1 _ _ _  q=2   k=9
==================|
_ _ * * * * * * * * 1 1 _ _ _  q=2   k=10
====================|
_ _ * * * * * * * * * 1 _ _ _  q=2   k=11
======================|
_ _ * * * * * * * * * * _ _ _  q=2   k=12
========================|
_ _ * * * * * * * * * * _ _ _  q=2   k=13
======================|
_ _ * * * * * * * * * * _ _ _  q=3   k=14
====================|
_ _ * * * * * * * * * * _ _ _  q=3   k=15
==================|
_ _ * * * * * * * * * * _ _ _  q=3   k=16
================|
_ _ * * * * * * * * * * _ _ _  q=3   k=17
==============|
_ _ * * * * * * * * * * _ _ _  q=3   k=18
============|
_ _ * * * * * * * * * * _ _ _  q=3   k=19
==========|
_ _ * * * * * * * * * * _ _ _  q=3   k=20
========|
_ _ * * * * * * * * * * _ _ _  q=3   k=21
======|
_ _ * * * * * * * * * * _ _ _  q=3   k=22
====|
_ _ * * * * * * * * * * _ _ _  q=3   k=23
==|
_ _ * * * * * * * * * * _ _ _  q=3   k=24
==|

Рис. 9. Замена единиц на звездочки

Задача 10.

На ленте МТ - последовательность _ABBAABAB____. Головка МТ - напротив левого символа. Напишите программу, чтобы МТ группировала символы "A" в правой части строки, а вместо них ставила звездочки.

Программа для машины Тьюринга выглядит так:

q "_" "A" "B" "*" " | "
1 1_R 2*R 1BR 1*R 1|S
2 3|R 2AR 2BR 2*R 3|R
3 4AL 3AR
4 1_R 4AL 4BL 4*L 4|L

В компьютерную программу ПР-2 следует вставить код: 

c=('_','A','B','B','A','A','B','A','B','_',
'_','_','_','_','_'); 

m:=1; q:= '1'; 
kom[1]:='1_>1_R'; 
kom[2]:='2_>3|R'; 
kom[3]:='3_>4AL'; 
kom[4]:= '4_>1_R'; 
kom[5]:='1A>2*R'; 
kom[6]:='2A>2AR'; 
kom[7]:='3A>3AR'; 
kom[8]:='4A>4AL'; 
kom[9]:='1B>1BR'; 
kom[10]:='2B>2BR'; 
kom[11]:='4B>4BL'; 
kom[12]:='1*>1*R'; 
kom[13]:='2*>2*R'; 
kom[14]:='4*>4*L'; 
kom[15]:='1|>1|S'; 
kom[16]:='2|>3|R'; 
kom[17]:='4|>4|L';

Результат работы программы -- на рис. 10.

_ A B B A A B A B _ _ _ _ _ _  q=1   k=1
==|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=2
====|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=3
======|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=4
========|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=5
==========|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=6
============|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=7
==============|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=8
================|
_ * B B A A B A B _ _ _ _ _ _  q=2   k=9
==================|
_ * B B A A B A B | _ _ _ _ _  q=3   k=10
====================|
_ * B B A A B A B | A _ _ _ _  q=4   k=11
==================|
_ * B B A A B A B | A _ _ _ _  q=4   k=12
================|
. . . . . . . . . . . . . . . 
_ * B B * * B * B | A A A A _  q=1   k=100
================|
_ * B B * * B * B | A A A A _  q=1   k=101
==================|
_ * B B * * B * B | A A A A _  q=1   k=102
==================|

Рис. 10. Группировка символов A

Задача 11.

На ленте МТ - число в десятичной системе счисления, например, 134999. Напишите программу, увеличивающую это число на 1.

Программа для машины Тьюринга представлена в таблице:

q "_" "1" "2" "3" "4" "5" "6" "7" "8" "9" "0"
1 2_L 11R 12R 13R 14R 15R 16R 17R 18R 19R 10R
2 21S 22S 23S 24S 25S 26S 27S 28S 29S 20L 21S

В программу ПР-2 следует вставить код: 

c=('_','1','3','4','9','9','9','_','_','_','_',
'_','_','_','_'); 

m:=2; q:= '1'; 
kom[1]:='1_>2_L'; 
kom[2]:='2_>2_S'; 
kom[3]:='11>11R'; 
kom[4]:='21>22S'; 
kom[5]:='12>12R'; 
kom[6]:='22>23S'; 
kom[7]:='13>13R'; 
kom[8]:='23>24S'; 
kom[9]:='14>14R'; 
kom[10]:='24>25S'; 
kom[11]:='15>15R'; 
kom[12]:='25>26S'; 
kom[13]:='16>16R'; 
kom[14]:='26>27S'; 
kom[15]:='17>17R'; 
kom[16]:='27>28S'; 
kom[17]:='18>18R'; 
kom[18]:='28>29S'; 
kom[19]:='19>19R'; 
kom[20]:='29>20L';

Результат работы программы -- на рис. 11. 

_ 1 3 4 9 9 9 _ _ _ _ _ _ _ _  q=1   k=1
====|
_ 1 3 4 9 9 9 _ _ _ _ _ _ _ _  q=1   k=2
======|
_ 1 3 4 9 9 9 _ _ _ _ _ _ _ _  q=1   k=3
========|
_ 1 3 4 9 9 9 _ _ _ _ _ _ _ _  q=1   k=4
==========|
_ 1 3 4 9 9 9 _ _ _ _ _ _ _ _  q=1   k=5
============|
_ 1 3 4 9 9 9 _ _ _ _ _ _ _ _  q=1   k=6
==============|
_ 1 3 4 9 9 9 _ _ _ _ _ _ _ _  q=2   k=7
============|
_ 1 3 4 9 9 0 _ _ _ _ _ _ _ _  q=2   k=8
==========|
_ 1 3 4 9 0 0 _ _ _ _ _ _ _ _  q=2   k=9
========|
_ 1 3 4 0 0 0 _ _ _ _ _ _ _ _  q=2   k=10
======|
_ 1 3 5 0 0 0 _ _ _ _ _ _ _ _  q=2   k=11
======|

Рис. 11. Увеличение числа на 1.

Тексты программ находятся в zip-архиве, файл gl-14.pas.

ВВЕРХ

Майер, Р. В. Задачи, алгоритмы, программы / Р. В. Майер [Электронный ресурс]. - Глазов: ГГПИ, 2012 // Web-site http://maier-rv.glazov.net .