Відношення часів роботи машин Тьюринга з різними наборами символів

У розділі Обчислювальна складність Арора та Барака, в пункті 1.5 сказано, що якщо функція $ f $ обчислюється за часом $ T (n) $ за допомогою машини Тьюринга з алфавітом $ \ Gamma $, то вона може бути обчислена в більша частина $ 4 \ log | \ Gamma | T (n) $ за допомогою машини Тьюринга з набором символів $ \ (0,1, \ rhd, \ Box \) $, де $ \ rhd $ - це спеціальний символ, який використовується для позначте початок кожної стрічки і $ \ Box $ - порожній символ.

Мені здається, що ми можемо скоротити зв'язність до $ 3 \ log | \ Gamma | T (n) $. Чи я прямо в цьому?

Мені здається, що вищесказане можна досягти, використовуючи той самий пристрій, який обговорюється в книзі: ми представляємо кожен алфавіт оригінальної машини Тьюринга послідовністю $ k = \ log | \ Gamma | $ біт. Давайте далі вирішимо представляти порожній символ оригінального машини послідовністю $ k $ $ \ Box $ s (це не згадується в книзі). Наша нова машина має проміжні стани, де він читає $ k $ біти, щоб ідентифікувати символ, який був прочитаний з касети оригінальної машини, а потім рухає кроки $ k $ назад у кожній стрічці, записуючи подання нового символу, який би написані на стрічках оригінальної машини, потім переміщує кроки $ k $ ліворуч або праворуч на кожну стрічку, щоб розмістити голову на початку символу, який був би прочитаний поруч із оригінальним машиною. Таким чином, загалом, всього лише кроки $ 3k $, необхідні для імітації кожного кроку оригінальної машини.

Щоб взяти приклад, припустимо, $ | \ Gamma | = 16 $, і ми імітуємо крок оригінального комп'ютера, який потребував читати символ, представлений abcd , перезаписавши його за допомогою ABCD а потім рухати головою вправо. Це можна виконати наступним чином:

Ми починаємо з

efgh|abcd|pqrs
     ^

У 4 кроках прочитайте всі біти abcd . На 4-му кроці ми знаємо достатньо, щоб вирішити, що ми повинні замінити d на D . Ми робимо це і повертаємося на один крок

efgh|abcD|pqrs
       ^

In 3 more steps we have replaced abc by ABC and positioned the head at B

efgh|ABCD|pqrs
      ^

Ще через 3 кроки ми перемістили голову до p

efgh|ABCD|pqrs
          ^

Якщо оригінальна машина хотіла перемістити вліво, а не правильно, ми могли б позиціонувати голову в h після написання A , а потім перемістили б до e ще 3 кроки. Отже, насправді нам потрібні лише $ 3k-2 $ кроки.

2
Я думаю, що ваш доказ є в порядку. Але, ви також можете зробити краще: немає необхідності завжди стрибати на лівий символ імітованої клітини. Дійсно, ми також можемо відслідковувати, якщо ми вводимо симулював символ зліва або справа і читаємо його зліва направо або справа наліво. Отже, якщо ліворуч буде введено імітовану комірку, то для переходу з читання-запису-права потрібен етап $ 3k-2 $, але перехід зліва на читання-записі вимагає кроків від $ 2k-1 $ (і наступна комірка буде прочитана з справа наліво)
додано Автор Marzio De Biasi, джерело

Відповідей немає

0