The website "komp-model.narod.ru." is not registered with uCoz.
If you are absolutely sure your website must be here,
please contact our Support Team.
If you were searching for something on the Internet and ended up here, try again:

About uCoz web-service

Community

Legal information

Майер Р.В. Задачи, алгоритмы, программы

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

Задача 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 .

Сайт управляется системой uCoz