Написание программы для машины Тьюринга

[grow]

Помогите разобраться с задачей плиз.

"Написать программу для Машины Тьюринга с пяти-символьными командами "

Что значит 1 в степени y? и q в степени звездочка?
Очень прошу.

[Профессор Снэйп]

Возможно, $1^y$ --- это $y$ единиц подряд, а $q^\ast$ --- это просто какое-то внутреннее состояние машины (типа того-же $q_0$). Хотя не уверен.

А задание вообще улыбнуло. Написать программу. Какую программу, что она должна делать? "Hello, world" что ли на ленте выписывать?

[grow]

q* это вроде бы конечное состояние..
А программа должна преобразовать слово (или выражение это) до стрелки в слово после стрелки.
Профессор Снэйп, поскажите плиз как и с чего лучше начать построение таблицы..

[Профессор Снэйп]

Я не знаю, что у Вас там за таблицы и зачем их нужно строить.

Модификаций машины Тьюринга известно великое множество. Какая именно из них фигурирует у Вас в задаче, мне неведомо. И пока Вы не опишите свою модификацию (строение машины + система комманд), Вам никто здесь не сможет помочь.

[grow]

Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. ||Для каждой пары (состояние, обозреваемый символ) определена тройка ||(записываемый символ, движение головки, новое состояние). До начала paботы М. Т. находится в начальном состоянии, а головка чтениязаписи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, М. Т. записывает новый символ (может быть, тот же caмый), сдвигает головку влево, вправо или остается на месте и переходит в(новое состояние или остается в прежнем.

Вот документ. На странице 3 рассмотрена система команд

[Профессор Снэйп]

Что-то я не понял. В Вашем документе сказано

Цитата:

Если в какой-то момент времени внутренняя память машины
приходит в заключительное состояние $q_0$, то дальнейших
изменений в машине не происходит и МТ считается
остановившейся.

А в том задании, которые Вы просите помочь Вам решить, машина в стартовой конфигурации находится именно в состояние $q_0$. То есть она не должна работать и не может ничего там преобразовывать, не так ли?

Кроме того, на странице 3, куда Вы нас отсылаете, рассматриваются четырёхсимвольные, а не пятисимвольные команды. Хотя, может, конечно, кто-то и стрелку считает за символ...

Рискну высказать предположение: ссылку Вы дали на лекции, а задачку Вам задал семинарист, который придерживается несколько других обозначений, нежели лектор. Так?

[grow]

получается так.
ну q_0 это не конец у нас...
это начальный символ.
стрелка это преобразование.
тогда не повезло =( не могу нигде найти инфу про пяти-символьные команды..

[Профессор Снэйп]

Так Вы инфу дали не на то, что у Вас, а на то, что первое под руку подвернулось? Так что ли?

[grow]

нет вы что.
описание работы машины и система команд примерно та же. Только вот как быть с 5-ю символами и 1^y

[Профессор Снэйп]

Вот именно, что примерно.

Короче, вот программа:

$$ q_01 \to q_0R $$

$$ q_00 \to q_1L $$

$$ q_11 \to q_20 $$

$$ q_20 \to q_1L $$

$$ q_10 \to q_3R $$

$$ q_30 \to q_31 $$

$$ q_31 \to q_4R $$

$$ q_40 \to q_5R $$

$$ q_50 \to q_51 $$

$$ q_51 \to q_6L $$

$$ q_60 \to q_6L $$

$$ q_61 \to q^\ast L $$

Либо это то, что Вам требуется, либо давайте другие ссылки. Не на то, что примерно, а на то, что точно.

[grow]

Профессор Снэйп
спасибо. сейчас переделаю

[grow]

в общем вот. Если кому-то нужно. Подсказали мне еще это

q_0 0 q_1 0R
q_1 1 q_1 R
q_1 0 q_2 1 R
q_2 q_3 0 R
q_3 q^*1 H


Профессор Снэйп
А так можно сделать?

[Профессор Снэйп]

Откуда я знаю, можно или нельзя?! Всё зависит от того, какая у Вас модификация машины Тьюринга и какую систему команд Вы используете. Вы об этом должны не у меня спрашивать, а у того, кто Вам эту задачу задал.