Каждый рекурсивный язык распознается смертной машиной Тьюринга?

Мы говорим, что машина Тьюринга смертна, если останавливается для каждой начальной конфигурации (в частности, содержимое ленты и начальное состояние могут быть произвольными). Каждый рекурсивный язык распознается смертной машиной Тьюринга? (т. е. если есть ТМ, принимающий , существует также смертный ТМ, принимающий ) $M$ $M$ $L$ $L$

computability Марчин Котовски
источник

Можете ли вы дать ссылку на Смертельные машины Тьюринга? Спасибо :)

Tayfun Pay

Как получается, что начальное состояние может быть произвольным? Разве смертная машина Тьюринга не является просто ТМ, который останавливается на каждом входе?

Филипп Уайт

@Marcin: вас интересуют машины, которые останавливаются во всех конфигурациях, включая бесконечные, или только те, которые останавливаются во всех конечных конфигурациях?

Джошуа Грохов

Я думаю, что он имеет в виду конечные стартовые конфигурации. Правильно?

Филипп Уайт

@Philip: просто представьте машину в произвольном состоянии и конфигурации, а затем запустите вычисление вперед с этой точки, следуя обычным правилам.

Джошуа Грохов

Ответы:

Вот два результата, приведенные в книге Чарльза Э. Хьюза «Неразрешимость конечной сходимости для операторов конкатенации, вставки и ограниченного шаффла» :

Теорема 3 : Класс смертных машин Тьюринга - это в точности класс машин Тьюринга с постоянным временем работы.

й для всех начальных конфигураций , останавливается не более чем шагов $ConstT = \{ M \mid \exists s$ $C$ $M$ $s$ $\}$

Поэтому я думаю , что мы можем получить следующее: учитывая смертный машин Тьюринга , пусть соответствующий постоянное время ТМ и его время работы. Язык, распознаваемый по алфавиту , точно: $M$ $M', s$ $M$ $\Sigma = \{0,1\}$

{x y ∣ | x | \leq s \land M^{'} accepts x in no more than s steps, y \in {0, 1}^{*}}

$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$

Таким образом, класс языков, распознаваемых смертными машинами Тьюринга, является подходящим подмножеством класса обычных языков. Например, вы можете использовать чтобы обмануть каждое постоянное время TM. $L = \{(0|1)^*1^*\}$

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

Теорема 4 : множество смертных машин Тьюринга рекурсивно перечислимо.

Марцио де Биаси
источник

Я думаю, что есть. Мы должны сделать для каждого L M, который принимает его таким образом, что все его ходы записываются на ленту, и после каждого «основного шага» он проверяет, были ли все его шаги до этой точки действительно действительными. Ниже я даю набросок о том, как сделать такую машину (которая может содержать некоторые незначительные ошибки, но основная идея должна быть в порядке).

Обозначим машину, которая принимает L через T. Теперь мы опишем M. Сначала мы копируем x на отдельную ленту памяти. Затем, когда бы T ни делал ход, мы записываем его на эту ленту памяти после x. После этого мы копируем все содержимое лент T в некоторые дополнительные рабочие ленты и проверяем, действительно ли из начальной конфигурации T достигнет своего текущего состояния после шагов, записанных на ленте памяти. Если нет, мы останавливаемся. Если да, мы продолжим.

domotorp
источник

во время написания своего ответа я читаю ваш ... который говорит обратное :-) ... возможно, я неправильно истолковываю, какую строку принимает смертная машина Тьюринга?

Марцио Де Биаси

@MarzioDeBiasi: понятие смертного, рассмотренное в этой статье, требует остановки машины за конечное число шагов, даже если она запускается с бесконечным количеством произвольных данных на ее ленте. Но я думаю, что конструкция Domotorp в большинстве случаев работает для конечных конфигураций. Например, в конфигурации с входом бесконечной длины, M у domotorp попадает в бесконечную последовательность копирования ввода бесконечной длины на отдельную ленту памяти ...

Джошуа Грохоу,

Да, разница в том, что я предположил, что каждый контент на ленте конечен, и мы знаем, где границы. В противном случае смертные ТМ просто постоянны, как вы пишете.

domotorp