Эквивалентность между ТМ и изменением TM

Question

Пусть изменяющийся Tm - Tm, который не может писать тот же символ, который читается. Формальный: $ m ^ *= (q, \ sigma, \ gamma, \ delta, q_ {Принять}, q_ {rej}) $ , $ \ delta (q, a)= (q ^ *, a ^ *, c), a \ neq a ^ * $ с $ Q, q ^ * \ \ q, a, a ^ * \ in \ gamma, c \ in \ {r, l} $ . Теперь мне нужно доказать, что изменяющийся TM эквивалентен нормальному тм.

Мое предположение было созданию мульти-ленты TM, которая способна имитировать изменяющийся Tm (и, следовательно, TM - эквивалентное для изменяющегося тм, поскольку каждая мультиката TM имеет эквивалентную одну ленту TM), но мне неспособноГотово (напишите это формально и неформально вниз).

Answer 1

Это еще один простой способ доказать, что изменяющийся TM может имитировать TM. Преимущество этого решения по сравнению с предыдущим является то, что он работает без какой-либо дополнительной утомительной работы независимо от того, допускается ли движение «пребывание».

Пусть $ t $ БУДЕТ TM с лентом алфавита $ \ Gamma $ . Создайте изменение TM $ t '$ с тем же пространством состояния и алфавит ленты $ \ Gamma' $ С $ 2 | \ Gamma | $ символы: для каждого символа $ a \ in \ gamma $ добавить Spaness Class="Math-container"> $ a $ и новый символ $ a '$ на $ \ Gamma '$ .

Для каждого перехода $ (q, a) \ to (q ', b, m) $ $ t $ Добавьте следующие переходы на $ t '$ (обратите внимание, что у вас может быть $ A= B $ < / span>):

.
• $ (q, a) \ to (q ', b', m) $
• $ (q, a ') \ to (q', b, m) $

Другими словами, вы относитесь к двум символам $ a $ и $ a '$ , как будто они были идентичны. Всякий раз, когда вы читаете «регулярный» символ (то есть, один из $ \ GAMMA $ ) Вы напишите символ «Prime». Всякий раз, когда вы читаете «Prime» символ (то есть, один из $ \ Gamma '\ setminus \ Gamma $ ) Вы напишите «регулярный» символ.

Answer 2

Понятно, что TM может симулировать изменение TM, поэтому вам нужно только показать общение. Позвольте мне позволить использовать движение «пребывание» на смене Turging Machine. Это легко (но утомительно), чтобы удалить это предположение и сохранение того, что он делает следующий аргумент более интуитивным.

Вы можете сделать следующее: начать с Tm $ t $ t $ t $ t $ t $ с набором состояний $ Q $ И лента алфавит $ \ Gamma $ . Затем создайте изменение TM $ t '$ с состояниями $ q'= Q \ Cup (q \ Times \ Gamma \ Times \ {l, r \}) $ и лента алфавит $ \ gamma '=gamma \ cup \ {\ gamma \} $ .

Интуитивно, состояние $ q \ in q $ $ t '$ представляет собой состояние $ Q $ OF $ T $ , а состояние $ (Q, A , м) \ q q \ times \ gamma \ times \ {l, r \} $ $ t '$ представляет собой тот факт, что мы планируем Написать $ A $ На текущей ленточной ячейке, затем переход к состоянию $ Q $ и переместится в Направление, указанное в $ m $ (обратите внимание, что это состояние, не переход, мы просто отслеживаем наши планы на будущее). < / P >.

Заменить каждый переход $ (q, a) \ to (q ', b, m) $ $ t $ со следующими переходами в $ t '$ :

.
• $ (q, a) \ to (((q ', b, m), \ gamma, s) $ , а также
• $ ((q ', b, m), \ gamma) \ to (q', b, m) $

Интуитивно, это заменяет запись символа $ B $ На ленте с двумя операциями: 1) мы пишем $ \ gamma $ без перемещения головы, а 2) перезаписываем $ \ gamma $ с $ b $ , переместите голову в предполагаемом направлении $ m $ и переход к соответствующему состоянию $ Q '$ $ t $ .

---

Это утомительный симулатон ТМ с изменением TM, если «движение пребывания» не допускается. Определите $ \ gamma '=gamma \ cup \ {\ gamma_1, \ gamma_2 \} $ и $ q'= q \ Cup (q \ times \ gamma \ times \ {l, r \} \ times \ gamma ') $ . Замените каждый переход $ (q, a) \ to (q ', b, m) $ $ T $ С следующими переходами в $ t '$ :

.
• $ (q, a) \ to (((q ', b, m, \ gamma_1), \ gamma_1, r) $ ,
• $ ((q ', b, m, \ gamma_1), x) \ to ((q', b, m, x), \ gamma_2, l) $ < / span> $ \ Quad \ forall x \ in \ gamma $ ,
• $ ((q ', b, m, x), \ gamma_1) \ to ((q', b, m, x), \ gamma_2, r) $ < / span> $ \ Quad \ forall x \ in \ gamma $ ,
• $ ((q ', b, m, x), \ gamma_2) \ to (((q', b, m, \ gamma_1), x, l) $ < / span> $ \ Quad \ forall x \ in \ gamma $ ,
• $ ((q ', b, m, \ gamma_1), \ gamma_2) \ to (q', b, m) $

Что мы делаем следующее: 1) мы пишем $ \ gamma_1 $ и двигаться вправо, 2) Мы храним текущую лентую символ $ x $ , заменить его с помощью $ \ gamma_2 $ , и переместить влево, 3) мы заменяем символ ленты $ \ gamma_1 $ с $ \ Gamma_2 $ и двигаться вправо, 4) мы запишем символ хранимого типа $ x $ вместо $ \ gamma_2 $ и переместить влево, 5) мы наконец написать $ b $ , перемещение в соответствии с $ m $ и переход к состоянию $ Q '$ .