¿Las máquinas de Turing suponen algo infinito en algún momento?

En una pregunta anterior ¿ Qué es exactamente un algoritmo? , Pregunté si tener un "algoritmo" que devuelve el valor de una función basada en una matriz de valores calculados previamente era un algoritmo.

Una de las respuestas que me llamó la atención fue esta:

El ejemplo factorial se introduce en un modelo diferente de cómputo, llamado cómputo no uniforme. Una máquina de Turing es un ejemplo de un modelo uniforme de cómputo: tiene una descripción única y finita, y funciona para entradas de tamaño arbitrariamente grande. En otras palabras, existe una TM que resuelve el problema para todos los tamaños de entrada.

Ahora, podríamos considerar el cálculo de la siguiente manera: para cada tamaño de entrada, existe una TM (o algún otro dispositivo computacional) que resuelve el problema. Esta es una pregunta muy diferente. Tenga en cuenta que una única TM no puede almacenar el factorial de cada entero, ya que la TM tiene una descripción finita. Sin embargo, podemos hacer una TM (o un programa en C) que almacene los factoriales de todos los números por debajo de 1000. Luego, podemos hacer un programa que almacene los factoriales de todos los números entre 1000 y 10000. Y así sucesivamente.

¿No cada TM realmente asume alguna forma de lidiar con el infinito? Quiero decir, incluso un TM con una descripción finita que calcula el factorial de cualquier número N a través del algoritmo

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

contiene el supuesto de que una TM tiene el "hardware" para comparar números de tamaño arbitrario a través del comparador "<=", y también AGREGA para incrementar i hasta un número arbitrario, además , la capacidad de representar números de tamaño arbitrario.

¿Me estoy perdiendo de algo? ¿Por qué el enfoque que presenté en mi otra pregunta es menos factible con respecto al infinito que este?

<=<=$Q$$\Sigma$

<=$|Q|$$|\Sigma|$

Las máquinas de Turing realmente no "tratan con el infinito": tratan con cosas finitas ilimitadas, al menos en su definición estándar. La entrada es una cadena finita y, después de cualquier número finito de pasos, la máquina solo ha examinado o escrito en un número finito de celdas de cinta. No hay límite en el tamaño de la entrada o el número de pasos de cálculo, pero la entrada es finita y, después de cualquier número finito de pasos, solo se ha producido una cantidad finita de salida.

Creo que la distinción importante es que la descripción de la máquina de Turing es finita, como lo es la entrada a la máquina, mientras que la cinta que usa como memoria es infinita. La TM es una máquina en su mayoría finita, que utiliza una cinta finita. Considere que la cinta está compuesta de celdas, donde cada celda puede contener un solo valor. La entrada a la TM está escrita en la cinta.

La descripción de una TM es un conjunto finito de tuplas <current state, input, output, move, next state>.

En cada paso, lo que hay que hacer se encuentra haciendo coincidir el estado actual y la entrada. Por ejemplo, estamos en el estado 0, y leemos un 1, por lo que encontramos la tupla que comienza y <0, 1, ...>luego escribimos un nuevo valor en la celda actual, nos movemos hacia la izquierda o hacia la derecha (creo que la definición clásica también permite permanecer en la misma celda también), y luego cambiar a un nuevo estado.

Entonces, para su ejemplo, necesitaría una descripción infinitamente grande de la TM (un número infinito de <current state, input, output, move, next state>tuplas) o incluir la información de búsqueda en la entrada a la TM. Creo que la entrada a una TM se define como finita. Por lo tanto, eso probablemente no sea algo que pueda hacer con una máquina de Turing clásica.

El ejemplo de Fibonacci, por el contrario, se puede calcular en binario con un número finito de tuplas para describir la TM, y tiene una entrada finita.

En pocas palabras : Turing Machine puede hacer (infinitamente especificado) cálculos infinitos sobre (infinitamente especificado) datos infinitos y producir (infinitamente especificado) resultados infinitos. La idea básica es que esos infinitos se pueden definir como el límite de entidades finitas, definidas de una manera matemáticamente apropiada. Esta es la base de la semántica matemática de la computación. Si considera programas en lugar de máquinas de Turing, estos programas también pueden contener (infinitamente especificado) estructuras de datos infinitas. El caso de una función tabulada factcomo un posible algoritmo se analiza al final, como un programa o como un modelo TM, con una pista sobre la relación con la evaluación diferida de objetos infinitos.

Con muchos mas detalles

Con respecto a su pregunta final, una TM no computa en números arbitrarios, sino en la representación simbólica de estos números como cadenas largas de símbolos arbitrariamente (sin límites) que los representan. Modulación adecuada del módulo, es correcto que puedan comparar o hacer aritmética con dichos números a través de estas representaciones.

Pero la pregunta original es sobre el papel del infinito en las máquinas de Turing en general.

Una respuesta común a esta pregunta es que las máquinas de Turing nunca tratan con el infinito. Están definidos de manera finita, y lo que sea que calculen se calcula en tiempo finito en una parte finita de la cinta (por lo tanto, una cinta finita que es más grande sería suficiente). Lo que es cierto es que los requisitos de tiempo de espacio de la TM son ilimitados, lo que no es lo mismo que infinito.

Por lo tanto, cualquier respuesta que sea calculada por un TM podría ser calculada también por un autómata de estado finito (FSA), que es "hasta cierto punto" una forma de ver la tabulación. La dificultad es que algunos tamaños de entrada (casi siempre llega a eso, aunque solo sea para leer la entrada) excederán el tamaño del autómata. Pero entonces, podemos usar uno más grande. Entonces, si queremos considerar un tamaño de entrada ilimitado, necesitamos una secuencia infinita de FSA que pueda hacer el cálculo. En realidad, es posible que necesitemos una máquina de estado finito un poco más compleja que la FSA tradicional, ya que puede haber una salida para ser calculada (en lugar de una respuesta sí-no), pero un transductor de estado finito probablemente debería funcionar.

Entonces, si estamos viendo un problema que tiene un conjunto infinito de instancias, como calcular un MCD o simplemente usar aritmética en enteros de tamaño arbitrario, vemos que el infinito regresa por la puerta trasera, ya que este infinito conjunto de FSA.

$\pi$

Por otra parte, podemos reemplazar eso por una secuencia infinita de cálculos finitos con máquinas finitas. Pero estamos haciendo trampa.

Desde un punto de vista físico, eso es lo mejor que podemos hacer. Solo sabemos cómo construir máquinas finitas, al menos de acuerdo con el estado actual de la técnica en física, que no se espera que cambie demasiado en ese tema en el futuro cercano.

Pero, ¿cómo podemos manejar esos infinitos de una manera consistente y manejable desde un punto de vista matemático?

Cuando considera un conjunto infinito de FSA que puede cooperar para calcular un conjunto infinito de respuestas, no puede hacerlo arbitrariamente. Necesita algunas salvaguardas para asegurarse de que lo que está haciendo tiene sentido. Es bien sabido que puedes construir trivialmente cualquier conjunto con una unión infinita de conjuntos regulares, en realidad con una unión infinita de conjuntos singleton. Por lo tanto, considerar uniones infinitas arbitrarias de autómatas sin ninguna restricción no lo llevará a ninguna parte. Incluso considera en el mismo conjunto de autómatas que le dan respuestas inconsistentes.

Lo que realmente quieres es definir una noción de consistencia. Pero eso requiere algunas precauciones. Supongamos que está utilizando una secuencia infinita de autómatas para simular una TM que responde sí o no, o no se detiene. El problema es que una FSA siempre se detendrá con una respuesta, como sí o no. Pero si usa una FSA que en realidad no tiene el tamaño suficiente para la entrada elegida, ¿qué debería responder? Tanto sí como no están reservados para los casos en que la FSA realmente finalizó el cálculo de TM, y el uso de una de estas respuestas con un cálculo inacabado solo conduciría a la confusión. Lo que quieres es una respuesta que diga: "lo siento, soy demasiado pequeño y no puedo decirlo. Por favor, intenta con un chico más grande de la familia ". En otras palabras, desea una respuesta como desbordamiento o no sabe$\bot$

Por lo tanto, necesita autómatas que tengan 3 tipos de estados: aceptar, no aceptar e indefinido. Un estado indefinido puede verse como un estado que representa una parte faltante del autómata que obliga a detener el cálculo. Entonces, cuando la computación se detiene, dependiendo del estado en el que se detiene, obtienes la respuesta sí , no o indefinido .

Ahora, ves que lo que quieres son secuencias infinitas de autómatas que sean consistentes . Tanto yes como no son consistentes con undefined , pero yes no es consistente con no . Entonces dos autómatas son consistentes cuando dan respuestas consistentes en la misma entrada.

$\pi$$3.14\bot\bot\bot\bot...$$3.1415\bot\bot\bot\bot...$$\bot.\bot5159\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$\pi$

No desarrollaré más estos aspectos teóricos, lo cual es un poco incómodo cuando estoy basado en máquinas de Turing. El punto es que estos conceptos llevan a la idea de que los dominios de cómputo (ya sean datos o máquinas), forman estructuras matemáticas como redes, en las que el objeto infinito puede definirse adecuadamente como los límites de secuencias infinitamente crecientes (es decir, mejor y mejor definidas) objetos finitos Definir las secuencias infinitas requiere más aparatos y una noción de continuidad. De esto se trata fundamentalmente la teoría de la semántica de Dana Scott, y ofrece una visión algo diferente de los conceptos de computabilidad.

Entonces, las máquinas de Turing u otros dispositivos formales que pueden hacer "cómputo infinito" pueden definirse como límites de secuencias de aproximaciones finitas de las máquinas, que están cada vez mejor definidas. Lo mismo es cierto para cualquier dato con el que las máquinas calculan, ya sea entrada o salida.

El documento más simple que he leído sobre esto es un conjunto de apuntes escritos a mano por Dana Scott, a menudo referidos como apuntes de Amsterdam. Pero no pude encontrarlo en la web. Cualquier puntero a una copia (incluso incompleto, ya que tengo parte de ella) sería bienvenido. Pero puede ver otras publicaciones tempranas de Scott, como Outline of a Mathematical Theory of Computation .

Volver al ejemplo inicial de la pregunta.

Estos conceptos de aproximación se aplican tanto a los datos como a los programas. La funciónfact se define de forma recursiva, lo que significa que es el punto menos fijo de un funcional que se puede utilizar para calcular una secuencia de aproximación finita convergente fact. Esta secuencia de funciones finitas más y más definidas converge a una entidad infinita que es lo que llama la función fact.

fact$\bot$ ( indefinida ) cuando la tabla no está lo suficientemente definida (lo suficientemente grande). El algoritmo de búsqueda de tablas también debe definirse mediante una secuencia de aproximaciones, ya que se calcula con una tabla infinita.

Es cierto que, si considera el modelo elemental de computación TM, tal matriz infinita no puede expresarse en ese formalismo. No significa que no tenga sentido. Una máquina de Turing podría tener una segunda cinta que se supone que debe inicializarse con los valores tabulados de algunas funciones como fact. No cambia el poder computacional de la TM, siempre que esa función sea computable, es decir, siempre que la tabla pueda inicializarse con un cálculo infinito de otra TM que pueda calcular todos los pares de argumento-valor para la función relevante.

Pero en la práctica, no puedes completar un cálculo infinito. Por lo tanto, la forma correcta de hacerlo es calcular la tabla de manera perezosa, es decir, llenar entradas solo cuando sea necesario. Eso es precisamente lo que se hace con la memorización, que es la respuesta que le di, con diferentes justificaciones, para su pregunta anterior.

La esencia de esta respuesta es que las máquinas de Turing pueden imitar cualquier cosa que podamos programar, y hacemos cálculos de programa en, con y de objetos infinitos.

Esta es una segunda respuesta que se centra más en la pregunta específica formulada que en el marco teórico general que justifica la respuesta, y sería definitivamente necesaria para responder al título más general de la pregunta. Es totalmente compatible con mis respuestas anteriores a las preguntas del OP, tanto ¿Qué es exactamente un algoritmo? y las máquinas de Turing sí asumen algo infinito en algún momento? , respuestas en las que desarrollé más el contexto teórico. Esto puede verse como una respuesta a ambas preguntas.

Las máquinas de Turing tienen la capacidad de lidiar con el infinito , al igual que todos los modelos computacionales completos de Turing, aunque solo con infinito infinito. Nuestro problema es que podemos observar solo una parte de este infinito, pero tenemos que considerarlo en su totalidad ya que la parte que podemos observar es ilimitada.

El otro problema es que solo podemos tratar con entidades finitamente especificadas. En realidad, toda la estructura de la ciencia, tal como la conocemos, se derrumba si consideramos entidades que no están especificadas de forma finita, ya que resulta imposible verificar la consistencia de las definiciones, incluso saber cuáles son las definiciones, ya que solo podemos acceder a una parte de ellas en Un tiempo finito.

Posiblemente, existe otro problema fundamental que es algo similar al hecho de que el cierre bajo una unión infinita define cualquier conjunto que desee, a menos que pueda restringir adecuadamente lo que está permitido en dicha unión. Pero no estoy seguro de entender completamente este problema.

Como dije, las máquinas de Turing tienen la capacidad de lidiar con el infinito . Estoy contradiciendo otras respuestas bien votadas de algunos usuarios de alta reputación, que deberían saber de qué hablan sobre un tema tan elemental.

El problema es que Turing eligió un modelo de computación muy elemental para lograr su propósito teórico. Cuanto más simple, mejor. Para los modelos de computación más avanzados / sofisticados es más o menos lo que el lenguaje de máquina es para la programación: algo muy oscuro en el que no se puede reconocer ninguno de los conceptos que tienen sentido en la programación de alto nivel. El hecho es que, al igual que el lenguaje de máquina, TM puede imitar mucho más de lo que puede expresar directamente.

$23{rd}$ Pero todavía se implementaría a menudo como un cálculo infinito que se detiene artificialmente cuando se alcanza la respuesta correcta.

En realidad, todos los usuarios que afirman que todo es finito pero ilimitado en una TM son muy cuidadosos y agregan que consideran las Máquinas Turing en su definición estándar . El problema es que la definición estándar es solo un dispositivo para simplificar la teoría, pero es prácticamente irrelevante cuando se trata de comprender las estructuras computacionales.

En realidad, lo único que importa en la computación es que todo debe especificarse finitamente de manera computable, no que sea finito .

Asumimos que una máquina de turing debe ser un objeto finito. Pero eso no es verdad. Puede definir un modelo de máquina de Turing utilizando una segunda cinta que es de solo lectura y contiene una función tabulada para todos los valores enteros, sin ningún límite. Eso es infinito Pero no le proporciona potencia informática adicional siempre que el contenido de esa cinta se especifique de manera computacional (la computabilidad implica que se especifica de manera finita). La cinta adicional bien podría ser reemplazada por una máquina TM integrada en la otra, y proporcionaría las respuestas, en lugar de buscarlas en la cinta adicional. Desde un nivel superior, la diferencia no es visible.

Desde el punto de vista de la realización práctica, podríamos tener una fact máquina de cómputo de los factores factoriales y tabularlos en la cinta adicional, mientras que otra TM usaría el factorial tabulado de la cinta adicional, solo esperando la primera TM cada vez que falte la tabulación. entrada. Pero la segunda máquina supone que el contenido de la cinta es, en última instancia, infinito. La máquina de tabulación ni siquiera tiene que trabajar todo el tiempo, sino que debe reanudar el cálculo siempre que se soliciten datos de la tabla y no se encuentren allí.

Volviendo a la pregunta, la principal diferencia entre los enteros ilimitados y la tabla infinita es solo que los enteros son finitos, ilimitados pero completamente calculados en tiempo finito. La tabla infinita se calcula indefinidamente, finita pero sigue creciendo todo el tiempo hasta el infinito. Eso no es un problema, pero es una diferencia. Los objetos infinitos son accesibles solo a través de aproximaciones finitas, ... pero son infinitos. Los números irracionales computables son, en este sentido, objetos infinitos, al menos para su representación como números binarios.

Todos los algoritmos se definen en el contexto de alguna teoría matemática. Y una búsqueda de tabla junto con una tabla infinita es un algoritmo. Pero es un algoritmo en una teoría matemática que tiene un conjunto infinitamente definido de axiomas que especifican ampliamente (en lugar de intensivamente) los valores de una función que axiomatiza para cada argumento entero. (vea mi respuesta a su pregunta anterior ). Entonces siempre es legítimo hacerlo, ya que siempre se pueden agregar afirmaciones demostrablemente verdaderas a los axiomas de una teoría.

Las declaraciones de Usul, tal como se reproducen en su pregunta actual, son incorrectas en mi opinión (aunque todo es también una cuestión de definición). Su conclusión en su respuesta , que no se reprodujo, es que el uso de una tabla infinita no puede considerarse un algoritmo porque solo puede implementarse mediante un modelo de computación no uniforme, mediante una colección de máquinas diferentes, y por lo tanto utiliza " no tiene una descripción finita que se pueda implementar para resolver el problema" completo "para cualquier tamaño de entrada$\pi$

La forma en que se calculan tales entidades infinitas en la práctica es mediante una evaluación perezosa , calculando cualquier parte que se necesite en cualquier momento y reanudando el cálculo para parte del resto cada vez que se necesite más. Eso es exactamente lo que se propone anteriormente con la factmáquina que calcula perezosamente el factorial para ser almacenado en una tabla, siempre que se necesiten más datos de la tabla.

En cierto modo, eso parece vindicar la afirmación (en la respuesta de DanielV ) de que el espacio de código debe ser finito, ya que la evaluación diferida se basará realmente en algún código finito. Pero la computabilidad es un juego generalizado de codificación, por lo que, entre otras cosas, distinguir el código de los datos siempre está a la vista del espectador. De hecho, muchos lenguajes de programación modernos no hacen mucha diferencia entre la especificación de valores intensional y extensional , y la Semántica Denotacional realmente no distingue "2 + 2" de "4". La semántica es realmente de lo que estamos hablando cuando hacemos una pregunta como " ¿Qué es X ? ".

Esta vista de la finitud del código, también vista como estática, es otra razón por la cual una tabla infinita (considerada como parte del código) no se ve en igualdad de condiciones con enteros ilimitados utilizados como datos. Pero esa es otra ilusión que no sobrevive a la práctica de programación conocida en metaprogramación , lenguajes reflexivos y el uso de la evalfunción. En esos idiomas, el programa en ejecución puede extender el código sin límites, siempre que la computadora esté en ejecución. De hecho, uno podría considerar máquinas de Turing que modifiquen sus propias reglas de transición, aumentando su número sin límite. Eso está bastante cerca de la forma en que funcionan las máquinas Universal Turing.

Al diseñar marcos teóricos, siempre existe una tensión entre la simplicidad y la visibilidad o la expresividad. La simplicidad hace que el análisis del marco a menudo sea más simple, especialmente cuando se trata de probar propiedades específicas o reducirlo a otros marcos. Pero a menudo es inconveniente para expresar conceptos de alto nivel que luego deben codificarse. No programamos con máquinas de Turing, sino con lenguajes de alto nivel que son mucho más expresivos y llamativos, y que al mismo tiempo pueden borrar algunas barreras, como la distinción entre código y datos, en función de la equivalencia semántica. Las máquinas de Turing parecen simples, pero pueden ir mucho más allá de su definición elemental.

La respuesta corta: no . Las máquinas de Turing no asumen nada infinito en ningún momento.

Esta es una razón por la cual son válidos como modelo para el cálculo. No tiene sentido describir la computación como algo realizado por un dispositivo infinito.

Sin embargo, su funcionamiento puede ser infinito: puede que no finalice. Esta es otra razón por la cual son válidos como modelo para el cálculo. Los dispositivos que solo pueden realizar operaciones que tienen la garantía de terminar siempre no pueden expresar todos los cálculos posibles.

Es más: la operación requiere memoria ilimitada : aunque la cantidad real de memoria en uso siempre es finita, puede crecer arbitrariamente. Por lo tanto, no puede suministrar toda la memoria que cualquier operación necesitará por adelantado. Los dispositivos que solo pueden realizar operaciones que se garantiza que nunca usarán más de una cierta cantidad fija de memoria no pueden expresar todos los cálculos posibles.

"pensar fuera de la caja" y generalizar sobre esta pregunta que llega a un corazón de la abstracción de las máquinas de Turing, y llegar a un ángulo diferente que aún no ha sido respondido: sí, las máquinas de Turing tienen algunos aspectos intrínsecos de "asumir infinitos" simplemente ya que el concepto es intrínseco a las matemáticas. Las TM son una abstracción de máquinas físicas. Los conceptos físicos del tiempo y el espacio se usan a propósito en la teoría TM pero como abstracciones, pero también con aspectos de sus contrapartes reales.

En resumen, la TM puede funcionar para siempre en teoría , también conocido como el problema de detención . la cinta es infinita, pero solo se puede escribir una cantidad finita en un momento dado. Una TM que se ejecuta para siempre básicamente supone que el tiempo y el espacio son ilimitados, es decir, "infinitos". de hecho, existe una jerarquía / "continuo" de Tiempo y Espacio correspondiente que es infinita.

pero no es posible la realización física de este concepto abstracto, suponiendo que el universo físico esté limitado (espacio, tiempo, materia, el último de los cuales es algo análogo a los "símbolos" o "tinta" en la máquina de Turing). de forma algo similar / análoga, en física a veces el universo se considera ilimitado / infinito, pero solo como una abstracción. Para cambiar esto, también es por eso que el "modelado" de una computadora moderna como una máquina de Turing es en sí mismo una abstracción, porque la computadora solo puede tener memoria finita, etc.

Otra comparación útil es la recta numérica en matemáticas. la recta numérica es infinita, pero denota números finitos. cada número en la recta numérica representa una cantidad finita, pero hay un número infinito de estas cantidades finitas. La cinta de máquina de Turing tiene una gran similitud con el concepto de línea numérica de las matemáticas. Turing podría haberlo definido fácilmente como solo infinito en una dirección, pero lo definió como infinito en ambas direcciones, al igual que la recta numérica matemática, con posiciones negativas "izquierda" en la cinta y posiciones positivas "derecha".