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

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

Пример 10.  Просмотрен 52

Рассмотрим машину Тьюринга, которая по записи любого числа на ленте распознает, оно больше нуля или равно нулю. В первом случае машина в качестве результата выдает число 1, записанное через одну пустую клетку справа от воспринимаемого числа, во втором — число 0, записанное также через одну пустую клетку справа от воспринимаемого числа.

Составим сначала схему работы этой машины (рис.).

В соответствии с этой схемой получим программу машины (табл. 12).

Таблица 12

  s0 |
q1 s0Лq2 |Лq2
q2 s0Нq3 |Нq6
q3 s0Пq4 |Пq4
q4 s0Пq5 |Пq4
q5 |Нq0  
q6 s0Пq7 |Пq7
q7 s0Пq8 |Пq7
q8 |Нq9  
q9 |Нq0 |Пq9
Предыдущая статья:Задача 5. Следующая статья:Пример 11.
page speed (0.0187 sec, direct)