Здравствуйте!

Надеюсь, это подходящий форум для моего вопроса.

Как лучше всего записать набор правил для машины Тьюринга (т.е. количество правил должно быть минимальным), например, для такой задачи: каретка находится на ячейке с символом '*', записать после него 600 символов 'a'. Можете идею подкинуть?

Здравствуйте, Wotan, Вы писали:

W>Как лучше всего записать набор правил для машины Тьюринга (т.е. количество правил должно быть минимальным), например, для такой задачи: каретка находится на ячейке с символом '*', записать после него 600 символов 'a'. Можете идею подкинуть?

Понятно, что напрямую писать 600 символов -- это надо иметь 600 переходов и соответствующие состояния. Для минимизации количества состояний и переходов можно использовать тот факт, что число 600 -- составное и равно 2*2*2*5*5*3. Соответственно, надо сначала записать два символа a, затем два раза помножить эту запись на два, затем два раза помножить результат на 5, и затем помножить результат на три. Лучше конечно делать это в порядке возрастания множителей, т.е. сначала 2, потом 3, а уже потом 5. Левую звездочку можно использовать как начала записи влево количества на что умножаем.

Здравствуйте, Wotan, Вы писали:

W>Как лучше всего записать набор правил для машины Тьюринга (т.е. количество правил должно быть минимальным), например, для такой задачи: каретка находится на ячейке с символом '*', записать после него 600 символов 'a'. Можете идею подкинуть?

Варианты:
— завести 600 состояний и соответственно, 600 правил
— завести 600 спецсимволов
— завести счётчик в позиционной системе счисления и небольшой набор правил

Моделируем:

*
*600
a*599
aa*598
aaa*597
......
aaa...a*0
aaaaaaa

Я так подозреваю, что это у тебя задачка учебная, поэтому не буду расписывать собственно правила. Удачи!

Здравствуйте, mefrill, Вы писали:

M>Понятно, что напрямую писать 600 символов -- это надо иметь 600 переходов и соответствующие состояния. Для минимизации количества состояний и переходов можно использовать тот факт, что число 600 -- составное и равно 2*2*2*5*5*3. Соответственно, надо сначала записать два символа a, затем два раза помножить эту запись на два, затем два раза помножить результат на 5, и затем помножить результат на три. Лучше конечно делать это в порядке возрастания множителей, т.е. сначала 2, потом 3, а уже потом 5. Левую звездочку можно использовать как начала записи влево количества на что умножаем.

Да, кстати! Блестящая идея.
Её можно развить — не факторизовывать число (а если бы оно было простым?), а разложить в двоичной системе счисления.
600 = 1001011000b
Нам нужны 9 групп правил, удваивающих строку, и 4 правила, дописывающих одиночную букву в хвост.

Про блеск поговорили, теперь про нищету.
Вопрос: сколько времени потратит что твоя, что моя машина? Вынужденная мотаться вдоль однеричной записи, удваивая, а то и упятеряя её?

И сравни с машиной, которую я предложил здесь

Автор: Кодт
Дата: 15.05.08

.

Здравствуйте, Кодт, Вы писали:

К>Про блеск поговорили, теперь про нищету.
К>Вопрос: сколько времени потратит что твоя, что моя машина? Вынужденная мотаться вдоль однеричной записи, удваивая, а то и упятеряя её?

Ну да, там же насколько я понимаю, главная проблема -- это минимизация количества состояний и переходов (то что автор правилами назвал?!). Поэтому время здесь не важно, это такая задача оптимизации хитрая получается.

К>И сравни с машиной, которую я предложил здесь

Автор: Кодт
Дата: 15.05.08

.

Ну да, счетчик это конечно решение. Надо просто подсчитать что дешевле будет, правила по десятичному (или n-ичному) счетчику или что-то типа как ты предложил, умножение на степени двойки или еще другой системы счисления. Это снова задача оптимизации.

Здравствуйте, Кодт, Вы писали:

К>Варианты:
К>- завести 600 состояний и соответственно, 600 правил
К>- завести 600 спецсимволов
К>- завести счётчик в позиционной системе счисления и небольшой набор правил

К>Я так подозреваю, что это у тебя задачка учебная, поэтому не буду расписывать собственно правила. Удачи!

Спасибо за ответы. Да, задача, понятное дело, учебная. Вообще у меня разновидность двумерной машины тьюринга. Количество состояний ограничено количеством символов в кодировке и есть всего 16 цветов. Просто, основная проблема -- это рисовать линии фиксированной длины. И при рисовании линии от одного конца экрана до другого нельзя выходить за его пределы (в таком случае работа машины останавливается).
Думаю, из предложенных вариантов лучше всего подходит вариант с удвоением цепочки. Хотя, может и счетчик подойдет, но к нему придется постоянно мотаться + позаботиться о том, чтобы его стереть. А потенциальных состояний мало...

Здравствуйте, mefrill, Вы писали:

M>Ну да, там же насколько я понимаю, главная проблема -- это минимизация количества состояний и переходов (то что автор правилами назвал?!).

Я точно не знаю, как формально называть "правила"/"переходы" или "правила перехода". На английском, вроде, это звучит как "instruction", т.е. "правило".