Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Как составить Машину Тьюринга?

Автор: Arwen 24.1.2008, 19:24

Всем привет! Завтра у меня экзамен по теории алгоритмов, препод на консультации сказал, что будет спрашивать создание МТ. Причем задачки будут наипростейшие... Но я вот сча сижу, пытаюсь в этом всем разобрацца, и ниче не выходит.... Может мне кто-нибудь подсказать? Вот допустим такое задание: q1  #i1 i2  нужно поменять местами i1 и i2, т.е. получить q1  #i2 i1 Мне даже стыдно такую ерунду спрашивать, так как уверена что это очень легко, но мне нужен хоть какой-то пример!   Помогите плиз, буду очень благодарна))

Автор: Ripper 24.1.2008, 20:04

Я уже плохо помню как такие задания делать. Но вот смотри-ка http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D1%82%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 здесь пример умножения чисел есть Или вот как мы делали слложение (из лекций) 2х чисел (сила представлены в виде x=11111... единиц. т.е. как я понял пять единиц это число 5) q1 * - > q2 l R q1 1 -> q2 l R q2 1 -> q2 1 R q2 * -> q31L q31 -> q31L q3 l -> qzlR единственно помню qz конечное состояние когда Машина Тьюринга прекращат работу. немогу вспомнить че такое l (лямбда). конечная буковка R L E - Right Left или остатся на месте  т.е. задается система команд типа q состояние. потом считываемый символ. -> что будет после того.  Т.е .было q1 *. Значит что состояние 1, и считываем любой символ. дальше переходим в состояние q2 передвигаем головку враво и ещё че то-то (чтож такое лямбда  )  Во! ещё пример нашел q1 1 -> q1 1 R  q1 l -> q1 1 R  Записывает бесконечно вправо всю еденицамии))

Автор: Arwen 24.1.2008, 20:49

Спасибо большое )))) Вроде начинаю догонять ) Поскорей бы уже завтра, отмучится )

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)