¿Por qué utilizamos máquinas Turing de cinta única para la complejidad del tiempo?

Como saben, hay muchas anomolias para las máquinas de Turing de cinta única cuando el tiempo es : simulación de TM de cinta múltiple, simulación de alfabeto de cinta más grande con solo , capacidad de construcción de tiempo, teorema de la falta de rigidez del tiempo, ... $o(n^2)$ $\{0,1,b\}$

También resulta como , y límites inferiores de tiempo muy específicos del modelo para problemas simples (que no se traducen incluso en límites inferiores superlineales en dos cintas TM). $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$ $O(n^2)$

Para la complejidad del espacio, utilizamos un modelo en el que tenemos una cinta de entrada de solo lectura separada, que es más natural y robusta.

Un modelo TM con múltiples cintas (o al menos 2 cintas de trabajo) sería mucho más robusto y no conducirá a anomalías como las que mencioné anteriormente. Una vez le pregunté a un prominente teórico de la complejidad que ha demostrado resultados de simulación en los primeros años de la teoría de la complejidad si conoce alguna mejora en uno de estos viejos resultados y la respuesta fue que no piensa que "las preguntas sobre el modelo de una cinta son que importante".

Si cambiamos el modelo estándar para la complejidad del tiempo a dos TM de cinta, los resultados razonables en la teoría de la complejidad no cambiarán y evitaremos estas anomalías causadas por un modelo en particular. Entonces mi pregunta es:

¿Hay alguna razón por la cual la complejidad del tiempo todavía se define en términos de TM de cinta única? (aparte de razones históricas)

cc.complexity-theory turing-machines Kaveh
fuente

Nunca he visto la complejidad del tiempo definida por TM de una sola cinta.

$\:$ Solo he visto las robustas clases de complejidad temporal definidas por TM de cinta única.

$\;\;$

@Ricky, quise decir que la complejidad temporal de un problema se define en términos de la complejidad temporal de las TM de una sola cinta que pueden resolverlo.

Kaveh

y quiero decir que nunca he visto eso hecho.

$\:$ Siempre he visto, como mínimo, acceso aleatorio.

$\;\;$

pero, ¿es esa realmente la definición habitual? lo que he visto en los libros de texto es: 1) definir una máquina de Turing de cinta única (porque es más simple); 2) mostrar cómo extenderse a otras variantes, en particular, acceso múltiple y aleatorio; 3) demuestre que todos estos pueden simularse entre sí con una desaceleración polinómica como máximo; 4) olvídate rápidamente del modelo en su mayor parte, al menos hasta que necesitemos cosas más sutiles como máquinas oracle y reducciones de espacio de registro; así que, como @RickyDemer, desafiaría la afirmación de que esta es realmente la definición habitual.

Sasho Nikolov

No tengo una respuesta para esto, pero solo quiero señalarle este trabajo por Yamakami ( springerlink.com/content/u844854721p83870 ). Este documento discute sobre lo que sucede cuando agrega consejos a una máquina pequeña (es decir, TM de una cinta de tiempo lineal). Prueba varias separaciones de clases, pero lo hace utilizando estas TM de una cinta. Estas separaciones no funcionarían si tuviera otro tipo de TM. Creo que este es un buen ejemplo en el que puedes probar cosas geniales con una cinta y probablemente no con un modelo diferente. La moraleja es "una cinta importa cuando se trata de cosas sutiles".

Marcos Villagra

Respuestas:

Las otras respuestas se ven muy bien. Me gustaría compartir un comentario que Russell Impagliazzo hizo hace años en una conferencia, que me ha quedado grabada desde entonces.

Creo que Turing puede haber preferido una sola cinta TM debido a la plausibilidad física.

Señalé a Russell a este hilo hace días, pero, dado que no está aquí, me gustaría conocer su comentario y haré todo lo posible para interpretarlo.

Para una única TM de cinta, suponiendo una cinta de longitud infinita (quédese conmigo), puede construir una TM que solo necesita una cantidad limitada de energía por iteración. Imagine la cinta como una varilla larga, y la cabeza, que contiene toda la lógica TM, simplemente se mueve a lo largo de esta varilla. (Lo considero como un pequeño y lindo artilugio con engranajes, utilizando una tecnología muy primitiva. La barra puede tener muescas para ayudarlo, y el contenido de la cinta puede ser un bloque deslizado ortogonalmente al eje de la barra).

Por otro lado, ¿cómo haces esto para un -tape TM? Si tienes $k$ $k$ de los artilugios anteriores, deben comunicar su estado de lectura a las otras cabezas potencialmente extremadamente distantes, lo que requiere cantidades ilimitadas de energía (digamos que usa cables, que necesariamente pierden calor), y además no es instantáneo, lo que complica el mecanismo. Si, en cambio, mantuviste las cabezas juntas y moviste las cintas debajo de ellas, estarías usando suficiente energía para mover cintas de longitud infinita ... No veo cómo obtener energía limitada en ninguno de los casos. Trucos como incrementos de cinta de contracción (para obtener una longitud finita) suponen un universo infinitamente divisible y violan cosas como la constante de Planck y el principio holográfico. Incluso ignorando estos, los mecanismos en la cabeza deben ser arbitrariamente precisos, lo que nuevamente causa problemas de energía y es prodigiosamente complicado.

Por supuesto, el primer esquema tiene problemas: la construcción de la cinta infinita con infinitas muescas, infinitos soles para alimentar los colectores solares en el cabezal móvil, un suministro infinito de suministros de limpieza y mantenimiento, etc. Tal vez algún avance importante en la mecánica cuántica. puede permitir que los cabezales -tape se comuniquen bien, pero ahora mira lo complicado que es nuestro artilugio. En cualquier caso, creo que el comentario de Russell es muy, muy interesante. $k$

matus
fuente

Pensé que Turing estaba tratando de abstraer el concepto de "computación" y no abstraer un modelo para un dispositivo físico. en ese caso, una máquina de Turing de una sola cinta captura limpiamente la intuición filosófica de que el cómputo implica el acceso local a una memoria grande (infinita)

Sasho Nikolov

Esperaba razones teóricas (no la posibilidad de realización de los modelos) pero esta respuesta me parece muy interesante, así que la estoy aceptando. Gracias de nuevo.

Kaveh

Al mantener las cabezas de la cinta en su lugar, parece que podemos hacer que la energía total sea loglineal o, con suerte, no peor que cuasilineal a tiempo al diseñar una forma de construcción Hennie-Stearns. Me imagino que las cintas se enrollan en bucles cada vez más grandes a medida que se extienden en cualquier dirección ... O de manera más imaginativa, en carretes de cintas, 100 cintas en un carrete, 100 carretes en un estante, 100 estantes en un almacén, y así sucesivamente en. Por supuesto, para la energía limitada por iteración necesitaríamos energía total lineal en el tiempo. Pero cuasilineal es mejor que el ingenuo cuadrático, así que pensé en mencionarlo.

Dan Brumleve

$f(n)$

Hay una clara razón pedagógica por la que Sipser hace esto, a saber, el curso fluye naturalmente de esa manera porque:

Debe introducir la máquina de cinta única antes que la máquina de cintas múltiples, de lo contrario, aumenta la curva de aprendizaje.
$\cdot$ $\cdot$
Idealmente, debe comparar la máquina de cintas múltiples con la máquina de cinta única en el momento en que introduce la máquina de cintas múltiples, de lo contrario, la ignorancia prolongada conducirá a una confusión adicional.
Puede omitir la introducción de las clases TIME análogas para máquinas de cintas múltiples, simplificando así la notación en general.

No hay razón para discutir sobre la limpieza conceptual cuando la pedagogía dicta claramente el camino más fácil, y cada estudiante de informática debe tomar este curso elemental, incluidos todos aquellos que aún no entienden las pruebas.

Jeff Burdges
fuente

No, IIRC, mi primer encuentro con TMs fue Hopcroft y la primera edición de Ullman. Pero la razón por la que hago esta pregunta en realidad está relacionada con el buen libro de texto de Sipser, enseñé teoría de la complejidad basada en Sipser y sentí que sería más simple y más limpio (sin pérdida de material esencial) para mí y los estudiantes si se basara en un cintas TM. Se evitarían todos estos pequeños detalles técnicos sobre el acceso restringido de TM de cinta única y podría cubrir material más interesante en el tiempo limitado que tenía. Sipser está relajado sobre el uso de la tesis de Church-Turing,

Kaveh

así que pensé que estar relajado sobre esta parte también podría estar bien. En la parte del teorema de la jerarquía de tiempo, menciona que el factor de registro adicional no es necesario si tuviéramos múltiples cintas y sería bastante ajustado. Esto me hizo preguntar si hay alguna razón no histórica para usar TMs de una sola cinta por complejidad de tiempo. No es peor que usar una cinta de solo lectura separada para la complejidad del espacio (y de nuevo eso se debe principalmente a que una sola cinta TM no captura la intuición sobre las clases de complejidad del espacio pequeño muy bien).

Kaveh

No veo cómo uno tendría sentido de los límites de espacio sub-lineales sin una cinta de entrada separada.

$\;$

Sí, supongo que SPACE se hace de manera diferente, en parte porque estarás haciendo límites sublineales, lo que probablemente no harás para TIME. Yo abogaría por suscribir TIME o hacer lo que Sipser hace por SPACE si desea hacerlo de esta manera, ciertamente me gustaría hablar sobre TIME o TIME_1 o lo que sea antes de las máquinas de cintas múltiples.

Jeff Burdges

Curiosamente, Sipser dice simplemente "máquina de Turing" cuando define el ESPACIO (f (n)) pero luego cambia la definición cuando discute las funciones sublineales f, asignando un ejercicio sobre la equivalencia para el superliner f. He enseñado este material de Sipser antes. No lo había pensado demasiado en ese momento, pero ahora estoy contento.

Jeff Burdges

La máquina original de Turing se describió con una sola cinta:

www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

Entonces, como usted dice en su pregunta, esto es principalmente por razones históricas. Además, siempre existe la tendencia a preguntar cuál es el modelo más simple que puede hacer algo ...

Además, dado que este tema generalmente se enseña de manera muy formal, es técnicamente más fácil describir una sola máquina de cinta que un mecanizado de dos cintas.

Ver también:

http://www.cs.utah.edu/~draperg/cartoons/2005/turing.html

Sariel Har-Peled
fuente