Задачи по теме «Машина Поста»
№3 Ответ
• программа, применимая к любому состоянию машины Поста:
• программа, не применимая ни к какому состоянию машины Поста, и
зона работы для любого начального состояния бесконечна:
• машина, не применимая ни к какому состоянию машины Поста, и зона
работы для любого начального состояния ограничена одним и тем же
числом ячеек, не зависящим от выбранного начального состояния
ленты:
! 1
–> 1
1. –> 2
2. <– 1