Космическая машина Тьюринга - разъяснение по вычислительной сложности (Книга: Арора -Барак) Вопрос 4.1

Question

У меня есть следующий вопрос от Вычислительная сложность - современный подход Санджив Арора и Боаз Барак:

Q 4.1
Докажите существование универсального TM для распределенных в пространстве вычислениях (аналогично детерминированным универсальным TM теоремы 1.9).

То есть докажите, что существует машина Turing $ su $, что для каждой строки $ alpha $ и input $ x $, если tm $ m_ alpha $ - TM, представленная $ alpha $ - останавливается на $ x $ перед использованием ячеек $ t $ своей рабочей ленты, затем $ su ( alpha, t, x) = m_ alpha (x) $ и, кроме того, $ su $ использует максимум $ c cdot t $ ячейки Его рабочая лента, где $ c $ является постоянной в зависимости только от $ m_ alpha $.

После проверки теоремы 1.9 и универсального TM со временем я вижу, что конструкция $ su ( alpha, t, x) $ означает, что машина Тьюринга останавливается после шагов $ t $. Однако, если это так, то это означает, что мы можем создать машину Тьюринга, эквивалентный $ m_ alpha $, так что новая машина Тьюринга останавливается в шагах $ t $, где $ t $ - «пространство», используемое в оригинале.

Однако это кажется сомнительным обменом пространства и времени. Если, с другой стороны, $ t $ фактически означала, что вторая машина также останавливается в пространстве $ t $, то вторая часть больше не имеет смысла, потому что она говорит, что $ su $ использует ячейки $ ct $, что не является $ T $.

Итак, мой вопрос: как мне это интерпретировать? Возможно ли первая интерпретация?

Answer 1

Я не понимаю, что вы пытаетесь сказать после «-», но вот что вам нужно сделать:

Надеюсь, вы поймете идею кодирования машины Тьюринга: т.е. вы можете назначить уникальный идентификатор (то есть «метка») $ alpha $ на каждой машине Тьюринга. Так что под $ m_ alpha $ мы имеем в виду машину Тьюринга, помеченную $ alpha $. Итак, вам нужно спроектировать не замужем Turing Machine $ su $, который берет три входа $ alpha $, $ t $ и $ x $ ($ alpha $ - это метка машины Turing, $ t $ - это пространство, а $ x $ - это входная строка) и и :

• Если $ m_ alpha $ использует более чем $ t $ bits of Workspace на входе $ x $ до остановки, тогда у нас нет требований для $ su $

• Если $ m_ alpha $ использует больше всего $ t $ bits of Workspace при входе $ x $, у нас есть два требования для $ su $:

  • $ Su $ использует большую часть $ ct $ единицы рабочей области, где $ c $ является функцией $ alpha $, но не $ t $ или $ x $
  • $ Su $ выходы $ m_ alpha (x) $

Идея состоит в том, что для любого машины и любого входа, $ su $ может моделировать эту машину, используя лишь немного больше места, чем исходная машина. Обратите внимание, что $ t $ является связанным в пространстве, которое использует $ m_ alpha $, а не пространство, которое использует $ su $. $ Su $ не может быть точно таким же эффективным пространством, как исходная машина, потому что моделирование требует некоторых накладных расходов, но дело в том, что накладные расходы невелики, так как $ c $ зафиксирована на каждую $ alpha $, независимо от того, насколько большой $ x $ в размер.

Теорема 1.9. Также имеет некоторые накладные расходы: машина, которая останавливается в $ T $ Time Steps, смоделирована в $ ct log t $ steps, где $ c $ снова является некоторой постоянной независимой от $ t $ или в входной строке.