Задача 5. Составьте программу машины l. l s0 | q1 s0Лq0 |Лq0
Составьте программу машины l.
Пример 7. Машина R, отправляясь от воспринятого в стандартном положении числа, не самого правого на ленте, идет вправо к стандартному положению ближайшего справа числа. Программа машины R помещена в таблице 10. Таблица 10
Задача 6. Примените машину R к ленте
Пример 8. Машина L, отправляясь от воспринятого в стандартном положении числа, не самого левого на ленте, идет влево к стандартному положению ближайшего слева числа. Задача 7. Составьте программу машины L и проверьте ее работу на ленте
Пример 9. Рассмотрим машину Тьюринга, производящую следующую операцию: если на ленте дан набор чисел x1, x2,..., xn, воспринимаемый машиной в стандартном положении, то машина в заключительном состоянии имеет на ленте набор чисел x1, x2,..., xn, 3, воспринимаемый ею также в стандартном положении. Так работает машина с программой, данной в таблице 11. Таблица 11
Задача 8. Проимитируйте работу машины для записи на ленте
|
