Задача на составление Машины Тьюринга

[serezha_ivanchenko]

Есть такая задача:

Написать программу МТ, которая сдвигает входное слово на заданное число k ячеек вправо, а в освободившиеся k первых после маркера начала ленты ячейки записывает специальный символ $.

Я не могу понять знаки $ нужно записывать от начала ленты, но лента же бесконечная, либо мне надо записывать их на место букв?

[3D Homer]

serezha_ivanchenko в сообщении #1029649 писал(а):

Я не могу понять знаки $ нужно записывать от начала ленты

Да.

serezha_ivanchenko писал(а):

но лента же бесконечная

Конечно. Иначе со сдвигом исходного слова вправо могли бы возникнуть проблемы.

serezha_ivanchenko писал(а):

либо мне надо записывать их на место букв?

Нет, на пустое освободившееся место после сдвига.

[serezha_ivanchenko]

3D Homer
Я все равно не могу понять вот эту формулировку : "...освободившиеся k первых после маркера начала ленты ячейки.."

Ведь лента бесконечная как слева так и справа, записывать первый $ надо на место 1 буквы слова?

[3D Homer]

serezha_ivanchenko в сообщении #1029667 писал(а):

Ведь лента бесконечная как слева так и справа

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

[serezha_ivanchenko]

3D Homer

Спасибо, я понял.

[serezha_ivanchenko]

Еще один вопрос:

Как машине объяснить, что сдвинуть надо на k элементов, как я понимаю это произвольное количество?

[3D Homer]

Здесь есть два варианта: либо $k$ дается машине на вход, либо оно встроено в саму машину, т.е. для каждого $k$ нужно построить свою машину. Судя по условию задачи, второй вариант мне кажется более вероятным.

[serezha_ivanchenko]

3D Homer в сообщении #1029734 писал(а):

Здесь есть два варианта: либо $k$ дается машине на вход, либо оно встроено в саму машину, т.е. для каждого $k$ нужно построить свою машину. Судя по условию задачи, второй вариант мне кажется более вероятным.

Т.е я могу взять для примера любое$k$ .

А если рассмотреть вариант подачи на вход машине, означает ли это что путем хитрых преобразований это значение $k$ должно оказаться на ленте?

[3D Homer]

serezha_ivanchenko писал(а):

Т.е я могу взять для примера любое$k$ .

Скорее всего, вам нужно описать процедуру построения МТ для любого заданного k. Но для начала можно взять какое-то конкретное k.

serezha_ivanchenko писал(а):

А если рассмотреть вариант подачи на вход машине, означает ли это что путем хитрых преобразований это значение $k$ должно оказаться на ленте?

Да, тогда k присутствует на ленте в какой-то кодировке, например, как двоичное число. Но судя по тому, что условие предписывает сдвинуть все "входное слово", мне кажется, что нужно сдвинуть все, что находится на ленте. Поэтому, наверное, k там не находится, хотя это может быть и не так.

[serezha_ivanchenko]

А где можно почитать как такое реализовать, в учебниках и лекциях все заканчивается на простыми примерами, речь даже не идет как построить МТ для любого $k$

[3D Homer]

Сейчас нет возможности порекомендовать книги. Возьмите для начала k = 3 и, начиная с правого края входного слова, скопируйте каждый символ на 3 клетки вправо. Символ запоминайте в состоянии. Не бойтесь заводить новые состояния и символы (например, перечеркнутые исходные символы).

[serezha_ivanchenko]

3D Homer в сообщении #1029749 писал(а):

Сейчас нет возможности порекомендовать книги. Возьмите для начала k = 3 и, начиная с правого края входного слова, скопируйте каждый символ на 3 клетки вправо. Символ запоминайте в состоянии. Не бойтесь заводить новые состояния и символы (например, перечеркнутые исходные символы).

Да это я понимаю как сделать при конкретном k, не понятно как записать это для любого k (и в программе-эмуляторе и задать математически)

[3D Homer]

В программном эмуляторе я тоже не знаю. Математически можете сказать: для каждого символа $a$ заведем состояния $q_{a,1},\dots,q_{a,k}$ и добавим инструкции $(x,q_{a,i})\to(R,q_{a,i+1})$ (здесь $x$ — произвольный символ, а $R$ — инструкция передвинуть головку вправо). Или что-то в этом роде.

[whitefox]

3D Homer в сообщении #1029749 писал(а):

Возьмите для начала k = 3 и, начиная с правого края входного слова, скопируйте каждый символ на 3 клетки вправо.

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

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: не приведены попытки решения

serezha_ivanchenko

serezha_ivanchenko в сообщении #1029727 писал(а):

Как машине объяснить, что сдвинуть надо на k элементов, как я понимаю это произвольное количество?

Приведите попытки решения, укажите конкретные затруднения.
Наберите все формулы и термы $\TeX$ом. Текст заданий набирайте буковками с клавиатуры, картинки сносите.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

3D Homer в сообщении #1029749 писал(а):

k = 3

3D Homer, замечание за неоформление формул $\TeX$ом.