Пример 10.Рассмотрим машину Тьюринга, которая по записи любого числа на ленте распознает, оно больше нуля или равно нулю. В первом случае машина в качестве результата выдает число 1, записанное через одну пустую клетку справа от воспринимаемого числа, во втором — число 0, записанное также через одну пустую клетку справа от воспринимаемого числа. Составим сначала схему работы этой машины (рис.).
В соответствии с этой схемой получим программу машины (табл. 12). Таблица 12
|
