Машина Тьюринга, принимающая слова «1», выстраиваемая в квадрат

Question

Я пытаюсь выяснить следующее задание и могу использовать вашу помощь, потому что я застрял. Я не стремлюсь к прямому ответу (но я не против, если кто-то способен спроектировать всю машину). Меня больше интересует утверждение / опровержение моих мыслей и указание в правильных направлениях.

Задание:

Построение машины Тьюринга, принимающей словав формате 1^k, where k=n^2 n is integer. В основном это принимает те слова, где вы можете расположить их в квадрат. Например, первые три приемлемых слова будут:

1Δ; 1111Δ; 111111111Δ;

, которые можно упорядочить в квадраты, подобные этому:

1

11
11

111
111
111

Мои мысли:

Если я получаю «1» только один раз, это должно быть принято.

Tape: 1Δ; k=1, n=1 and k=n^2

Так что я предполагаю, что после одного «1» я нахожусь в состоянии «СТОП» (давайте назовем это состояние A ), если на ленте нет другого символа.

Следующим приемлемым словом является следующий квадрат, который мы можем записать в формуле следующим образом:

(n+1)^2  That equals: n^2 + 2*n + 1

Разница между двумя последовательными квадратами составляет (2*n + 1)

Итак, если мое предположение верно, если я в состоянии A Мне нужно как-то проверить, получаю ли я(2*n + 1) раз «1» на ленте, и если это вернет меня в состояние A , оно будет правильно принято. Все остальное должно быть отклонено.

Проблема, с которой я сталкиваюсь, заключается в том, что я не знаю, как считать (2*n + 1) раз «1» на ленте.

Также я должен найти решение, используя только одну ленту. Подсказка заключается в том, что он должен заканчиваться в форме 111#111111111Δ, где сумма единиц в левой части равна " k ", а в правой части равна " n ". К сожалению, этот намек совсем не помог мне. Я бы сказал, что мне стало хуже.

Answer 1

Итак, если вы хотите, чтобы одноканальный магнитофон работал, и вы не заботитесь об эффективности, подумайте о следующем:

1. скопируйте ввод в конец ленты,отделенный от исходного ввода разделителем
2. запись числа k (от 1 и выше) в одинарный на конце ленты, отделенный от копии вторым разделителем
3. разделение копиисчетчиком k путем итеративного вычитания k из копии и маркировки одного из k вычеркнутых символов копии специальным символом
4. при условии, что при делении на шаге 3 осталось 0 остатков, снова разделите на то же самоеКстати, но только с учетом специально отмеченных символов
5. при условии, что при делении на шаге 4 оставалось 0 остатка, посмотрите, было ли частное 1. Если да, то вы нашли input = k ^ 2 и можете остановить прием. в противном случае вы можете прервать ввод, если k> input.

Пример ввода 1111:

   1111
-> 1111A1111       // copy input
-> 1111A1111B1     // add counter
-> 1111A3333B1     // divide by 1 by bouncing back and forth, marking every 1th
-> 1111A5555B1     // repeat
-> 1111A1111B11    // don't have one 5, so copy input and increment counter
-> 1111A3232B11    // divide by 2 by bouncing back and forth, marking every 2nd
-> 1111A5242B11    // divide by 2 again considering only 3s from last step
-> accept          // halt-accept since one 5 remaining means input = k^2

Ваш путь тоже работает. Вы можете отслеживать текущее n (или k) и итеративно вычеркивать 2n + 1 из 1 в вашей копии на каждом этапе. Что-то вроде:

   1111
-> 1111A1111    // copy input
-> 1111A1111B   // begin counter at 0
-> 1111A2111B   // cross off 1 in the copy
-> 1111A2111B1  // increment counter
-> 1111A2222B1  // cross off 3 in the copy
-> accept       // all symbols crossed off

Если вы получаете настоящую механику «подпрыгивания», чтобы вычеркнуть, вычесть, разделить и т. Д., То идея состоит в том, что вы меняете символ, который пересекаетек одному, который вы определили как означающий, что он был помечен для этой цели;измените состояние, чтобы вы знали, что нужно пометить дальше;пометьте это;затем вернитесь к первому неотмеченному символу (если есть), с которого вы начали.