Машина Тьюринга

[maxmatem]

всем добрый день! просто не никак пока не соображу, надо построить машину Тьюринга для вычисления $f(x;y)=x+y$ алфавит выглядит так $A={O;|}$
$O$-"кружок"
$|$-"палочка"
и числа кодируются так $0$-$O|O$ $1$-$O||O$ и так далее .
допустим надо посчитать сумму $O||O$ и $O||O$ их сумма это $O|||O$разделяет два числа
я хотел посоветоваться именно на счёт самого алгоритма вычисления суммы ,а именно: я думаю что надо вместо нуля который раздляет два числа, записывать $|$ и последнюю(самую правую)$|$ стирать и управляющею головку прводить на влево. так?

[Maslov]

Не очень понятно.
Как выглядит лента с исходными числами, и как она должна выглядеть после того, как сложение выполнено?

-- Чт апр 01, 2010 16:42:22 --

И где изначально располагается каретка?

[maxmatem]

пара чисел на ленте выглядит так $\[OIIOII\underbrace O_{{q_1}} \Rightarrow OII\underbrace O_{{q_0}}I\] $ ну например так!

[Maslov]

Все еще не понятно:
1. Где, собственно, сумма (0|||0) ?
2. Что это за одинокая палочка справа?

[maxmatem]

да я забыл там палку! (0|||0)

[Maslov]

Так: 0||0||0 -> 0|||0** ?
И какой символ вместо звездочки?

[maxmatem]

в каком смысле?

[Maslov]

Начальное состояние ленты: 0||0||0
Что должно находиться в этих 7 ячейках после завершения работы программы?
0|||000 ?

[maxmatem]

ну да именно 0|||000 я понимаю что надо вместо 0 который эти пары разделяет записать | и самые правые две | надо стереть , и передвинуть управляющую головку на самую правую |. так?

[Maslov]

Ну да, если там больше одной правой |. Ну а если одна, то тоже понятно, что делать.

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

[maxmatem]

где можно про это почитать? я с этой программой уж 5-й час ругаюсь! кстати зачем мне произвольное число ноликов когда пара натуральных числ разделяется одним ноликом?

[Maslov]

Почитать вот здесь, например: Хопкрофт Дж. и др. Введение в теорию автоматов, языков и вычислений

А еще вот такая забавная программка есть: JFLAP

[maxmatem]

спасибо! кстати а где в этой книге раздел про машину Тьюринга?

[maxmatem]

всем спасибо я составил!

[Maslov]

maxmatem в сообщении #305376 писал(а):

кстати а где в этой книге раздел про машину Тьюринга?

А "Глава 8. Введение в теорию машин Тьюринга" не подходит?