Una máquina de Turing tiene una cantidad infinita de memoria, que no es posible en la vida real. ¿Por qué sigue siendo un buen modelo?

El modelo estándar de Turing Machine es una generalización simple. Considere una máquina de Turing restringida con una cinta de 3 bits de longitud. Esta máquina de Turing solo puede aceptar / rechazar algún subconjunto de todo el espacio del lenguaje L = {e, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111} donde ‘ e ‘observa la cadena vacía. Cualquier lenguaje que esta máquina de Turing reconozca como un subconjunto de L puede ser aceptado / rechazado trivialmente por un DFA (autómatas finitos discretos) con un conjunto de estados de tamaño igual al tamaño de | L | con cada estado marcado manualmente aceptar / rechazar. Esto es un fuerte argumento para su pregunta, ¿por qué usar el modelo de máquina de Turing si todas las máquinas reales se pueden modelar con una construcción de autómatas mucho más simple en forma de DFA?

| L | en el ejemplo anterior es 15. Si aumentamos el tamaño de la cinta de nuestra máquina Turing a la longitud 4, entonces necesitaremos aumentar el tamaño del DFA que modela L del tamaño 15 al tamaño 31. Si aumentamos a la longitud 10, entonces necesitamos ahora un DFA con (2 ^ 11) -1 estados dentro de nuestro DFA comparable. Tenga en cuenta que este DFA debe tener cada estado marcado aceptar / rechazar a mano. Un sistema informático moderno podría tener 32 GB de memoria. Esto significa que un sistema moderno podría tener una cinta de 274877906944 bits. ¡Esto significa que dicho sistema puede ser modelado por un DFA con solo (2 ^ 274877906945) -1 bits! Podríamos comenzar a dibujar este DFA hoy, y alrededor del tiempo en que el universo habrá terminado varias veces, habremos completado la construcción de un modelo de DFA que puede aceptar y rechazar trivialmente los mismos estados que una computadora moderna.

Claramente, necesitamos un modelo más fuerte para representar lo que se puede calcular. Al igual que los físicos e ingenieros eléctricos a menudo simplifican las placas conductoras de un condensador al modelarlas con un plano de carga infinito (sin mayor propósito que la conveniencia matemática), los campos de la informática y la matemática deben tratar su modelo como funcionalmente infinito para mejorar la trazabilidad del cálculo humano y la conclusión. Al final del día, la máquina de Turing es un modelo útil para demostrar los límites superiores de la computabilidad conocida. Cuando el impacto de la memoria restringida se convierte en la variable que uno desea comprender mejor, un modelo más matizado y relevante, como alguna forma de máquina de Turing restringida, puede ser más adecuado.

Cuando pensamos en una computadora en lo que respecta a lo que puede computar, siempre imaginamos (tal vez de manera poco realista pero perfectamente intuitiva) que podemos agregar más memoria si la necesitamos. Por lo tanto, una computadora en nuestra imaginación es muy parecida a una máquina de Turing, que necesita ser definida tanto por una cinta infinita, como por una cinta sin límites … donde podemos agregar más cinta cuando sea necesario.

Ahora, en realidad, cada computadora es simplemente una máquina de estados finitos de algún tamaño fijo, pero no pensamos en ellos de esa manera. Tan pronto como podamos hacer que nuestra computadora sea más grande, lo hacemos. Y, no limitamos nuestro sentido de la capacidad de computación de la máquina por su memoria.

Decimos que una computadora puede ordenar números, encontrar rutas más cortas, compilar programas o decidir si una fórmula es satisfactoria. Escribimos algoritmos para hacer estas cosas. Sin embargo, en realidad, ninguna computadora puede ordenar más que un número fijo de números, ni encontrar una ruta más corta en un gráfico que sea mayor que el número de átomos en el universo, ni decidir si una fórmula similar es satisfactoria, ni compilar Un programa más grande que su memoria. Las computadoras solo pueden resolver un número finito de instancias de cualquier problema. Cosas bastante aburridas … pero “imaginamos” y definimos que, dado que pueden resolver estos problemas en principio en general SI tienen más memoria, pueden “calcular” estas cosas.

Las máquinas de Turing modelan con precisión si las computadoras pueden “calcular”.

Si exigiéramos que cada máquina de Turing tuviera una cinta de cierta longitud finita, no podríamos proporcionarle a la máquina cadenas de entrada más allá de cierta longitud.

En particular, esto tendría serias repercusiones en la noción de universalidad. La máquina de Turing es un modelo universal de cómputo en el sentido de que es programable; existe una máquina de Turing universal que, dada cualquier descripción de una máquina de Turing y una cadena de entrada [matemáticas] \ langle M, w \ rangle [/ matemáticas ] simula cómo se comportaría [math] M [/ math] cuando se le da [math] w [/ math] como entrada.

Obviamente, este requisito natural de un modelo de cómputo no es posible de satisfacer si se requiriera que las máquinas de Turing tuvieran capacidad de almacenamiento finita.

Un buen modelo es precisamente esto: un modelo. Conserva la esencia de lo que está modelando y elimina detalles irrelevantes para que podamos centrarnos en lo que más importa.

Los objetos físicos no son infinitamente divisibles, pero calculamos su centro de masa utilizando integrales de una variable real. Es mucho más fácil que trabajar con átomos individuales, y funciona perfectamente. Entonces es un buen modelo. Lo mismo con la cinta infinita de las máquinas de Turing.

Además, las máquinas de Turing se utilizan a menudo para comprender los límites de la computación. Si algo no se puede hacer con una TM, en cualquier cantidad de tiempo, entonces ciertamente no se puede hacer con una computadora física con memoria finita. Esto lo convierte en un modelo increíblemente poderoso, cuando nos propusimos probar que ciertas cosas son absolutamente no computables.

Por otro lado, si se puede hacer algo con una TM, es posible que aún no sea factible con una computadora práctica; esto es ciertamente cierto, y en ese sentido, las TM no son un buen modelo, porque ignoran una restricción. Claro, por supuesto que sí. Todos lo sabemos y recordamos esto. Pero es muy útil saber que algo es, al menos, computable en teoría. Podemos preocuparnos por los detalles más adelante.

Por la misma razón, el sistema métrico permite una longitud arbitraria, pero sigue siendo útil. Es un método de descripción precisa que nos permite parametrizar un conjunto particular de abstracciones de manera significativa. Poner límites en una máquina de Turing eliminaría su generalidad y la haría inmediatamente menos útil.

Su pregunta es no sequitur. ¿Por qué el hecho de que ninguna máquina real tenga memoria infinita significa que la abstracción de Turing Machine no es un buen modelo? Dado que una cinta infinita puede contener la memoria de cualquier computadora, la abstracción de la máquina de Turing abarca todas las máquinas reales, lo cual es una característica buena, incluso necesaria, de una abstracción de la computación.

Además del hecho de que la objeción implícita en la pregunta es una pista falsa, hay razones positivas por las que la abstracción de la máquina de Turing es un buen modelo de cálculo. En particular, es isomorfo a otras dos abstracciones, el cálculo lambda de Church y el modelo computacional de Post. La tesis de Church-Turing afirma que cualquier función computable puede ser calculada por alguna máquina de Turing.

Análogamente, las líneas en papel en realidad consisten en una secuencia irregular de manchas. ¿Por qué entonces son útiles los conceptos geométricos como las líneas? Bueno, imagina intentar crear una geometría generalizada útil basada en secuencias irregulares de puntos. Claramente, la abstracción geométrica captura las características conceptuales que queremos, y su simplicidad hace posible construir teoremas y un marco matemático completo de verdades sobre geometría abstracta, verdades que se aplican con cierto grado de precisión a objetos reales. Lo mismo es cierto de la informática.

Una máquina de Turing es una máquina automática para ejecutar un algoritmo específico con datos como entrada, salida y con el algoritmo también representado como datos. En el caso de una máquina de Turing universal, los datos de entrada incluyen la definición (datos) de otra máquina de Turing. El concepto teórico de una máquina de Turing permite una cantidad infinita de memoria para almacenar estos datos, sin embargo, en la práctica, la mayoría de los algoritmos pueden ser útiles con menos memoria. Con toda probabilidad, un algoritmo que necesita una cantidad infinita de memoria también necesitaría una cantidad infinita de tiempo, volviéndose doblemente poco práctico. Por lo tanto, para todos los algoritmos útiles, la máquina de Turing correspondiente solo usa una cantidad limitada de memoria. Puede haber sido más útil especificar que no hay un límite superior fijo para la cantidad de memoria que una máquina de Turing puede emplear en la ejecución de su algoritmo.

1. ¿Cuánto debería tener en su lugar? 30MB? ¿Eso no es suficiente? Hubiera sido suficiente hace unas décadas.
2. Una máquina de Turing puede ser modelada por las matemáticas, es decir, el cálculo lambda, y en matemáticas, si algo es desconocido, le asignamos una variable. En [matemática] y = 2x [/ matemática], [matemática] x [/ matemática] podría ser, presumiblemente, en cualquier lugar entre ([matemática] – \ infty [/ matemática], [matemática] \ infty [/ matemática]), pero no es [math] – \ infty [/ math] o [math] \ infty [/ math]. [math] x [/ math] es finito al igual que la memoria es finita, pero se supone que es infinito de la misma manera; Las variables, hasta que se miden, son desconocidas.
3. Es un modelo, entonces, ¿por qué no se supone que es infinito? Si alguna vez necesitas más que memoria infinita, probablemente te equivocaste. También se supone que el modelo no tiene errores, está alimentado, es infinitamente rápido, etc. ¿Por qué? Porque es conveniente.

Una máquina de Turing (TM) no tiene una cantidad infinita de memoria, en el sentido de que en algún momento de su cálculo se almacena un número infinito de bits en sus cintas (memoria). En cualquier paso de cálculo de cualquier TM, hay un número finito de bits en sus cintas (memoria); esto incluye incluso el caso de un cálculo que nunca termina.

Por supuesto, podemos decir que una TM no tiene un tamaño de memoria fijo, en el sentido de que puede usar tanta cinta (memoria) como sea necesario en un cálculo. El análogo a las computadoras comerciales sería el siguiente: permita que se interrumpa un programa que solicita más memoria de la disponible, hasta que se agregue más memoria a la computadora, y luego reanude el programa en la misma computadora con la memoria agregada.

En cualquier caso, como lo señalaron otros, los TM se consideran modelos abstractos que nos permiten razonar sobre los límites de la computación.