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

[karakhan.livejournal.com]

Доброго времени суток.
Подскажите, пожалуйста, где (желательно, в сети) можно почитать подробно про машину Тьюринга.
Заранее благодарю.

Comments

[doctor-tretyak.livejournal.com]

тебе сюда (http://ru.wikipedia.org/wiki/Машина_Тьюринга)

[karakhan.livejournal.com]

Благодарю, там я был. Мне надо несколько поподробнее.
Например, что такое "машина Тьюринга, удваивающая слова", как понять "программа машины Тьюринга для вычисления функции в алфавите {лямбда;1}" и что может значить странная фраза "проблема применимости к начальному слову алгоритмически неразрешима".

[alkoletchik.livejournal.com]

вообще много информации в сети по этому поводу..
http://www.intuit.ru/department/calculate/basecalfun/9/

"машина Тьюринга, удваивающая слова" - на ленте написано слово, запускаешь машину и после ее работы на ленте написано это слово дважды. очень просто, если в принципе представлять, как это работает и как пишется..

"программа машины Тьюринга для вычисления функции в алфавите {лямбда;1}" - задана функция (если это задание какое нибудь, то посмотрите, там должна быть указана конкретная функция), на ленте написано число (написано единицами - унарный код), машина считает функцию от этого числа и пишет на ленту результат..

"проблема применимости к начальному слову алгоритмически неразрешима" - вроде одна из теорем о МТ.. посмотрите, почитайте..


Вы вообще с какой целью интересуетесь? если задание какое, например в инсте, то надо литературу искать из того источника, откуда и задание.. но вообще все просто. думаю, разберетесь без проблем.

[karakhan.livejournal.com]

Грррромадное спасибо!!!