Turging Machine, которая может вспомнить

Question

Специальный автомат Turing определяется так же, как стандартная машина Turing, только в том, что каждый шаг выполнен в соответствии с содержанием ленты, начиная с левого края к положению головки в ленте. (Функция перехода в этом случае принадлежит Q x γ * -> Q x γ x {l, r})

Что из следующего верно:

a. На каждом языке L есть Turging Machine, которая решает L если и только в том случае, если есть специальная машина Turging, которая решает L.

б. Каждый язык L имеет Turging Machine, которая решает L в многочленом времени, если и только в том случае, если есть специальный механизм, который решает L в полиноме (многочлена входной длины).

c. A, B ответы верны.

d. A, B ответы неверны.

И мой вопрос: Правильный ответ D, и я не могу понять, почему.

Ответ: Каждый язык может быть определен специальной машиной для Turing в линейном времени ввода (o (n), когда n представляет собой входную длину). Функция перехода направляется вправо, пока нет пустого пространства, и как только вы видите пробельные выключатели для получения или отклонения в соответствии с словом, написанным на ленте.

Мой вопрос: Как я могу решить, следует ли отвергать или принимать слово? В других вычислительных моделях, таких как PDA, DFA, мы определили функцию перехода аналогично, и к модели не добавляли питание. Почему может показаться, что питание добавляется в вычислительную модель в результате изменения функции перехода, когда речь идет о Turgines Machines?

спасибо.

Answer 1

Учитывая любой язык $ l $ есть специальный механизм Turging $ T $ , который решает $ l $ в полиноме.

Turging Machine имеет 3 состояния: начальные состояния $ q_0 $ , принимающее состояние $ q_a $ И состояние отклонения $ q_r $ . Пусть $ \ Gamma $ Будьте ленты Alphabet (включая пустой символ $ \ varepsilon $ ), и пусть $ \ alpha x $ обозначает содержимое ленты, начиная с левого края к положению головки в ленте, где $ \ Альфа \ in \ gamma ^ * $ и $ x \ in \ gamma $ . Как обычно, я собираюсь предположить, что вход написан начиная с начала ленты и что головка изначально расположена в начале ленты. Функция перехода $ \ delta $ определяется следующим образом:

.
• $ \ delta (q_0, \ alpha x)= (q_0, x, r) $ Если $ x \ neq \ varepsilon $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ Если $ x=varepsilon $ и $ \ alpha \ in l $
• $ \ delta (q_0, \ alpha x)= (q_a, x, r) $ Если $ x=varepsilon $ и $ \ alpha \ not \ in \ in l $

Поскольку для регулярных трюмов есть неразрешенные языки, это немедленно подразумевает, что A и B являются ложными.

Ответы D и C неясны. Они говорят о «Оба ответа», но вам дают 4 $ $ Возможные ответы.