Всего на сайте:
236 тыс. 713 статей

Главная | Информатика

Задача 5.  Просмотрен 51

Составьте программу машины l.

l s0 |
q1 s0Лq0 |Лq0

Пример 7.

Машина R, отправляясь от воспринятого в стандартном положении числа, не самого правого на ленте, идет вправо к стандартному положению ближайшего справа числа.

Программа машины R помещена в таблице 10.

Таблица 10

R s0 |
q1 s0Пq2 |Пq1
q2 s0Пq2 |Пq3
q3 s0Лq0 |Пq3

Задача 6.

Примените машину R к ленте

s0 | | | s0 s0 | | s0 | | s0 s0 s0
      q1           

Пример 8.

Машина L, отправляясь от воспринятого в стандартном положении числа, не самого левого на ленте, идет влево к стандартному положению ближайшего слева числа.

Задача 7.

Составьте программу машины L и проверьте ее работу на ленте

s0 | | | s0 s0 | | s0 | | s0 s0 s0
              q1       

Пример 9.

Рассмотрим машину Тьюринга, производящую следующую операцию: если на ленте дан набор чисел x1, x2, ..., xn, воспринимаемый машиной в стандартном положении, то машина в заключительном состоянии имеет на ленте набор чисел x1, x2, ..., xn, 3, воспринимаемый ею также в стандартном положении.

Так работает машина с программой, данной в таблице 11.

Таблица 11

  s0 |
q1 s0Пq2 |Пq1
q2 |Нq3  
q3 |Нq4 |Пq3
q4 |Нq5 |Пq4
q5 |Нq0 |Пq5

Задача 8.

Проимитируйте работу машины для записи на ленте

s0 | | s0 | | | s0 | s0 s0 s0 s0 s0 s0
                q1       
Предыдущая статья:Задача 3. Следующая статья:Пример 10.
page speed (0.0433 sec, direct)