Консультация № 176147
19.01.2010, 23:01
0.00 руб.
0 4 1
Здравствуйте эксперты, есть такая задачка:
Построить машину Тьюринга для распознавания последовательности символов на ленте. Построить машину Поста для той же задачи.
Последовательно 01373
С машиной Тьюринга знаком вроде, то что она двигает головку и меняет внутренние состояние и переписывает ленту, но что значит – распознавать последовательность.
Объясните или дайте ссылку на материал
Заранее спасибо.

Обсуждение

Неизвестный
20.01.2010, 05:25
общий
это ответ
Здравствуйте, Tribak.



Определение свойства распознавания машиной Тьюринга и программа для последовательности 01373:

http://picasaweb.google.ru/ParkerSubscribe/RFPro#5428641747087982290


Для машины поста надо уточнить постановку задачи, т.к. "Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. " Т.е. символы 3 и 7 в явном виде недопустимы.

http://ru.wikipedia.org/wiki/Машина_Поста



С уважением, Антон.
5
Неизвестный
20.01.2010, 08:16
общий
а на картинке не видно что к чему, можно побольше разрешение?
Неизвестный
20.01.2010, 08:24
общий
Tribak:
Source: http://docs.google.com/View?id=ddh7j7ps_7d3p5qvfr
давно
Профессор
230118
3054
17.10.2011, 14:01
общий
17.10.2011, 14:02

Форма ответа