Диаграмма состояний для машины Тьюринга для вычисления следующей строки в лексикографическом порядке - PullRequest
Новая
       41

Диаграмма состояний для машины Тьюринга для вычисления следующей строки в лексикографическом порядке

2 голосов
/ 01 апреля 2019

Как будет выглядеть диаграмма состояний для машины Тьюринга, которая вычисляет следующую строку в лексикографическом порядке по алфавиту Σ = {1, 2, 3}?Размер строки равен 4, т. Е. --- 1, --- 2, --- 3, --11, --12 и т. Д.Вычисления без удачи.Также попытался найти его в Интернете, опять же без удачи.

Заранее спасибо!

1 Ответ

0 голосов
/ 01 апреля 2019

Если я правильно понял, вы хотите, чтобы ТМ взял в качестве входных данных строку длиной {1, 2, 3} длиной до четырех, и перезаписал это число строкой в ​​том же алфавите, который будет следующим в лексикографическомпорядок.Вот стратегия для этой проблемы.

  1. переместитесь вправо три раза, поэтому мы смотрим на четвертый символ на ленте.
  2. , если это поле пустое, наш ввод искажен имы умрем.в противном случае, если символ равен 1, напишите 2 и остановите-примите;если 1, напишите 2 и остановите-примите;если 3, напишите 1 и переместитесь влево в состоянии «carry2»
  3. , если это поле пусто, 1 или 2, запишите 1, 2 или 3 соответственно и нажмите «halt-accept».если 3, напишите 1 и переместитесь влево в состоянии «carry3»
  4. , если это поле пусто, 1 или 2, запишите 1, 2 или 3 соответственно и нажмите «halt-accept».если 3, напишите 1 и переместитесь влево в состоянии «carry4»
  5. , если это поле пусто, 1 или 2, запишите 1, 2 или 3 соответственно и нажмите «halt-accept».если 3, то вводом было число 3333, и нет лексикографически более крупной 4-значной строки над {1, 2, 3}… так что либо произойдет сбой, либо будет перенесено и записано --- 1 на ленту.1014 * Обратите внимание, что это не подтверждает, что содержимое ленты является нормальным ... поскольку мы используем пробелы для кодирования "пропущенных" старших разрядов, мы можем просто разумно предположить, что после позиции 4 на ленте нет ничего (определяя, что делает наша TM тщательночтобы не было намека на то, что мы что-то сделали после этого).Кроме того, мы не проводим санитарную обработку передней части, поэтому неправильное смешивание символов и пробелов может быть проблемой ... поэтому мы могли бы сначала выполнить несколько шагов для проверки ввода или просто потребовать, чтобы вход был правильно сформирован, когда мы его получим.
...