¿Puede la entrada a una máquina Turing ser de longitud infinita?

Considerando solo el alfabeto , las cadenas que se pueden dar como entrada a las máquinas de Turing son del conjunto Σ ∗ . Pero, ¿tiene sentido que la entrada sea una cadena binaria infinita? Por ejemplo, si una máquina de Turing acepta todas las cadenas que comienzan con un 0, ¿una cadena binaria de ceros infinitos también pertenece al lenguaje aceptado por la máquina de Turing?$\Sigma = \{0,1\}$$\Sigma^{*}$

No hay ningún problema en ejecutar una máquina Turing en una cinta inicializada con una cadena infinita, aunque esto generalmente no se considera. Sin embargo, todavía necesitamos que la máquina termine en un tiempo finito. También hay nociones de cálculo de tiempo infinito, que pueden ser apropiadas aquí.

Esa es una de las características de las máquinas de Turing Tipo 2 . Se usan, entre otras cosas, para analizar la computabilidad de las funciones entre números reales. Aún más interesante, se utilizan para analizar la computabilidad de los operadores como la integración.

Dato curioso: la integración numérica exacta es computable.

Para responder a la pregunta "¿tiene sentido", esto incluso puede ser útil si considera las máquinas de Turing que funcionan en tiempo limitado.

Específicamente, esta es una forma muy útil de pensar máquinas Turing sin prefijos . Estas son máquinas cuyo conjunto de entradas de detención está libre de prefijos; es decir, ninguna entrada que haga que la máquina se detenga es el prefijo de otra. Estos son equivalentes en potencia a las máquinas Turing normales, pero solo si permitimos que la máquina Turing decida sus propias entradas de detención: es decir. el usuario no tiene idea de qué entradas detendrá la máquina (y esta es una propiedad indecidible).

Una forma de ver esto es como una máquina Turing normal con una cinta de entrada infinita unidireccional con un cabezal de cinta que no puede retroceder. El usuario llena la cinta con bits y ejecuta la máquina. Esta es, por definición, una máquina de Turing sin prefijos. Si la máquina se detiene, debe haber leído solo un número finito de bits, y ningún prefijo de esa parte de la cinta puede ser un programa, o la máquina se habría detenido allí.

Esta es una buena manera de hablar sobre distribuciones de probabilidad computables: el usuario llena la cinta con bits aleatorios (la fuente de aleatoriedad de la máquina), y la máquina escupe una cadena de bits aleatoria. El conjunto de todas esas máquinas de Turing corresponde al conjunto de distribuciones computables (específicamente las semimensiones semicomputables más bajas).

La ventaja de la entrada infinita es que no tenemos que especificar qué hace la máquina si le damos el prefijo de un programa de detención, es decir. la máquina intenta leer más allá del final de la entrada que le hemos dado.

Incluso si no tiene una cinta de este tipo, puede emplear otra máquina de Turing para producirla.

Una máquina Turing tiene acceso a la cinta de datos vacía, pero infinita (o algunas fuentes dicen que "la máquina solo tiene una pequeña fábrica de cintas incorporada"). Por lo tanto, puede inicializarlo con algún patrón de datos programable, y luego la cinta podría consumirse como entrada de otra máquina Turing.

Por supuesto, si su contenido es tal que ningún algoritmo podría definirse cómo producirlo, dicho contenido no puede ser creado por la máquina Turing.

Hay algunos casos en que la entrada infinita se puede considerar y reducir a la acción de una máquina de Turing "estándar". Por ejemplo, considere un patrón finito que se repite infinitamente especificado en la entrada. Se puede crear una máquina Turing que haga un seguimiento de cuánto de este patrón infinito ha sido modificado por las acciones actuales del cabezal de la cinta utilizando una cantidad finita de almacenamiento de memoria / cinta. En otras palabras, "simula de manera equivalente" un patrón de tamaño infinito en la cinta.

Otro caso en el que se ha considerado la "entrada infinita" es el análisis de la equivalencia / integridad de Turing de los autómatas celulares. En una prueba compleja, Cook introdujo un concepto ahora conocido por algunos como "equivalencia débil de Turing" al convertir operaciones de regla CA 110 en operaciones de máquina de Turing que comienzan en una cinta inicial infinitamente especificada pero con patrones (de repetición) de tamaño finito.

En lenguajes formales, una cadena es, por definición, una secuencia finita de símbolos. Una máquina clásica de Turing tiene una cinta infinita con una cadena de entrada finita. Como tal, aunque no hay límite en cuanto a la duración de la entrada, no puede ser infinita.

Dicho esto, hay muchas máquinas alternativas que funcionan de manera similar a una TM pero con secuencias de entrada infinitas.

Si tiene sentido tener una entrada de longitud infinita depende del propósito. Estrictamente dentro del contexto de Turing Machines, no tiene sentido (ya que no es posible), pero en el contexto de Turing-like Machines, tiene sentido y tiene muchas aplicaciones.