Espacio delimitado máquina de Turing - aclaraciones sobre la complejidad computacional (libro: Arora-Barak) pregunta 4.1

Question

Tengo la siguiente pregunta de complejidad computacional - un enfoque moderno por Sanjeev Arora y Boaz Barak:

[Q 4.1]
Probar la existencia de un TM universal para espacio cálculo acotada (análogamente a la TM universales determinista del Teorema 1.9).

Es decir, demostrar que existe una máquina de Turing $ SU $ tal que para cada cadena $ \ alpha $ y $ x $ de entrada, si el TM $ M_ \ alpha $ - TM representado por $ \ alpha $ - - se detiene en $ x $ antes de usar $ células $ t de su cinta de trabajo, entonces $ sU (\ alpha, t, x) = M_ \ alpha (x) $ y, además, $ sU $ usos en la mayoría $ C \ cdot t $ células de la cinta de trabajo, donde $ C $ es una constante que depende sólo de $ M_ \ alpha $.

Después de comprobar teorema 1.9 y la TM universal de tiempo límite, veo que el constructo $ SU (\ alpha, t, x) $ significa que la máquina de Turing SU detiene después de $ $ pasos t. Sin embargo, si este es el caso, entonces significa que podemos crear un equivalente máquina de Turing a $ M_ \ alpha $ tal que la nueva máquina de Turing se detiene en $ $ pasos t donde $ t $ es el "espacio" que se utiliza en el original.

Sin embargo, esto parece un intercambio dudosa de espacio y tiempo. Si por el contrario, $ t $ realidad quería decir que la segunda máquina se detiene en $ espacio $ t, también, a continuación, la segunda parte no tiene sentido más porque dice $ SU $ utiliza células $ Ct $, que no $ es t $.

Así que mi pregunta es ¿Cómo interpretar esto? Es la primera interpretación realmente posible?

Answer 1

No entiendo lo que usted está tratando de decir que después de "-", pero aquí es lo que hay que hacer:

Esperamos que usted entiende la idea de turing codificación de la máquina: es decir, se puede asignar un identificador único (es decir, "etiqueta") $ \ alpha $ a cada máquina de Turing. Así que por $ M_ \ alpha $ nos referimos a la máquina de Turing etiquetado por $ \ alpha $. Así que hay que diseñar un solo máquina de Turing $ SU $ que tiene tres entradas $ \ alpha $, $ t $ y $ x $ ($ \ alpha $ es un sello de la máquina de Turing, $ t $ es un espacio obligado, y $ x $ es una cadena de entrada) y:

• Si $ \ alpha $ M_ usos más de $ T $ bits de espacio de trabajo de entrada de $ x $ Detiene antes, entonces no tenemos ninguna necesidad de $ SU $

• Si $ M_ \ alfa $ uses a lo sumo $ t $ trozos de espacio de trabajo de entrada de $ x $ tenemos dos requisitos para $ SU $:

  • $ SU $ usos en la mayoría de los $ Ct $ unidades de espacio de trabajo donde $ C $ es una función de $ \ alpha $ pero no $ t $ o $ x $
  • $ SU $ salidas $ M_ \ alpha (x) $

La idea es que para cualquier máquina y cualquier entrada, $ SU $ puede simular que la máquina durante el uso de sólo un poco más de espacio que la máquina original. Tenga en cuenta que $ t $ es un encuadernado por el espacio que $ M_ \ alfa $ uses, no el espacio que $ SU $ usos. $ SU $ no puede ser exactamente tan eficiente en espacio como la máquina original, porque la simulación requiere un poco por encima, pero el punto es que la sobrecarga es pequeño como $ C $ es fijado por cada $ \ alpha $, no importa cuán grande $ x $ es en tamaño.

Teorema 1.9. También tiene algo de sobrecarga: una máquina que se detiene en $ T $ pasos de tiempo se simula en $ TC \ log T $ pasos de tiempo donde $ C $ es de nuevo una constante independiente de $ T $ o de la cadena de entrada.