Obligatorio emulación de la máquina de Turing límite inferior

¿Hay alguna prueba de que la emulación de una máquina de Turing en una máquina de Turing ajena no se puede hacer en menos de donde es el número de pasos que usa la máquina de Turing ? ¿O es solo un límite superior? $\mathcal{O}\left(m\log m\right)$ $m$

En el artículo de Paul Vitányi sobre máquinas Turing inconscientes relativizadas, Vitányi afirma

"Ellos [ Pippenger y Fischer, 1979 ] demostraron que este resultado no puede mejorarse en general, ya que existe un lenguaje L que es reconocido por una máquina de Turing en tiempo real 1 cinta , y cualquier máquina de Turing inconsciente reconoce debe use al menos un orden pasos ". $M$ $M'$ $L$ $O(n \log n)$

Esto debería indicar $O(m \log m)$ como un límite absoluto. Sin embargo, no encuentro ninguna prueba de esto en

Pippenger, Nicholas; Fischer, Michael J. , Relaciones entre medidas de complejidad , J. Assoc. Comput Mach. 26, 361-381 (1979). ZBL0405.68041 .

¿Algunas ideas? Además, ¿cuál es la complejidad espacial de esta emulación? Que yo sepa, la conversión a una máquina universal de Turing solo duplica la longitud de la cinta. ¿Puedo suponer que la complejidad del espacio es $\mathcal{O}\left(l\right)$ con $l$ la complejidad del espacio de la máquina Turing original?

cc.complexity-theory turing-machines Willem Van Onsem
fuente

Haga coincidir los paréntesis y defina qué es T. Creo que todavía está abierto, pero no soy un experto.

Tsuyoshi Ito

¿Qué es una máquina turing ajena?

Suresh Venkat

Una máquina de Turing obvia es una máquina de Turing donde el movimiento de los cabezales solo depende de la longitud de la entrada y no de la entrada en sí. Por ejemplo, búsqueda lineal (si la cabeza sigue moviéndose hasta que haya llegado al final de la entrada)

Willem Van Onsem

Respuestas:

Como se mencionó anteriormente, no se sabe en general si hay una simulación ajena más rápida.

Pero se conocen límites inferiores interesantes para este problema, en condiciones más restringidas. Por ejemplo, ¿qué sucede si desea una simulación ajena que conserve no solo el tiempo sino también el uso del espacio ? Beame y Machmouchi han demostrado recientemente un intercambio inferior de espacio-tiempo interesante para este problema: o el espacio debe aumentar en un factor de , o el tiempo debe aumentar en un factor de . $t$ $s$ $n^{1-o(1)}$ $\Omega(\log n \cdot \log \log n)$

El documento está aquí: http://eccc.hpi-web.de/report/2010/104/

Ryan Williams
fuente

Solo un comentario extendido: creo que sigue siendo un problema abierto; vea el blog de Lipton y Regan para algunas buenas discusiones sobre cómo mejorar el resultado del teorema de Fischer-Pippenger .

Por ejemplo, vea las publicaciones: Máquinas de Turing inconscientes y un "Crock" o Límites de circuitos para computaciones de máquinas de Turing (ambos con fecha de 2009).

En la segunda publicación, muestran que es posible un mejor límite de circuito ( ) utilizando una función booleana parcial que se aproxima la función original en entradas. $O(n \log {\log n})$ $g:2^n \to \{0,1,*\}$ $f$ $2^{n-o(n)}$

Marzio De Biasi
fuente

He leído el teorema de Fischer-Pippenger y es una prueba. Sin embargo, nunca en la prueba hay un componente que diga que no existe un método más rápido. Me preguntaba si existe una prueba que diga que este es el mínimo garantizado. Si miras la prueba, emulan el TM en un UTM y luego realizan un pequeño truco para que no se dé cuenta. Sin embargo, se puede argumentar que el primer paso solo es necesario para saber cómo se comportará la máquina.

Willem Van Onsem

@CommuSoft Nadie sugiere que la prueba sea otra cosa que una prueba de límite superior. Las publicaciones de blog sugieren que mejorar Fischer-Pippenger es un problema abierto.

Sasho Nikolov

@CommuSoft: Es un problema abierto ... tal vez exista un método más rápido o alguien demostrará que es el mejor posible.

Marzio De Biasi

Bueno, estoy leyendo un artículo publicado por Paul Vitányi llamado "Olvido relativizado" que parece afirmar que el tiempo es al menos O (m log m). Sin embargo, todavía no estoy muy seguro si usa el teorema de Fischer-Pippenger para probar esto.

Willem Van Onsem