¿Existe una analogía física con la máquina de Turing?

Recientemente en mi clase de CS me presentaron a la máquina de Turing.

Después de la clase, pasé más de 2 horas tratando de averiguar cuál es la relación entre una cinta y una máquina.

No conocía por completo la existencia de cintas de computadora o cómo interactuaban las cintas y las máquinas hasta hoy. Todavía no puedo ver por qué una máquina leería cintas, pero un escáner es quizás una concepción más cercana a la máquina de Turing, donde el papel se considera una cinta y todo lo que entra dentro de un escáner es lo que haría una máquina de Turing.

Pero, en cualquier caso, ¿no es la idea de una máquina de Turing bastante arcaica? Tenemos tantos dispositivos físicos (en lugar de hipotéticos) en nuestra oficina o sala de estar que parecen hacer lo que hace la máquina de Turing.

¿Puede alguien proporcionar un mejor ejemplo basado en la realidad para capturar las funcionalidades esenciales de esta concepción hipotética?

Las máquinas de Turing son uno de los modelos de cálculo "originales" completos de Turing, junto con el cálculo y las funciones recursivas definidas recursivamente. Hoy en día, en muchas áreas de la informática teórica, se usa un modelo diferente, la máquina RAM, que está mucho más cerca de las computadoras reales. Dado que ambos modelos son equivalentes a p (se simulan entre sí con una explosión polinómica como máximo), desde el punto de vista de preguntas como P vs. NP, ambos modelos son equivalentes.$\lambda$

AFAIK the Turing Machine está inspirada en la idea de un humano con un bolígrafo y papel. El ser humano tiene un cierto estado en el cerebro, mira el papel como la máquina mira la cinta y escribe algo en el papel o se mueve para mirar a un lugar diferente, tal como lo hace la máquina.

TM es arcaico como la aritmética de números naturales de Peano. TM es inútil para el cálculo práctico y, por supuesto, no está destinado a ser utilizado para eso. Es solo una manera simple de axiomatizar la computación para que podamos razonar acerca de lo que es computable y lo que no lo es, así como la aritmética de Peano es útil para definir desde el principio principios qué son los números naturales y cuáles son sus propiedades, pero sería ridículo trate de hacer aritmética manipulando números de Peano a mano de acuerdo con las definiciones teóricas.

Solo piense lo difícil que sería probar diferentes teoremas de la teoría de la complejidad y la computabilidad (por ejemplo, demostrar que el Problema de detención es indecidible), si tuviera que probarlos utilizando la semántica del lenguaje de programación C ++ en lugar de la Máquina de Turing. Sus pruebas serían ridículas o imposibles, tan ridículas como probar la asociatividad de la multiplicación de números naturales utilizando el método de la escuela primaria aplicado a los enteros decimales como su definición de lo que es la multiplicación.

Muchos modelos de computación completa de Turing muy diferentes son físicamente realizables (hasta considerar el infinito como sin límites). Por lo tanto, ese no es el punto para elegir un modelo.

La respuesta de @jkff es apropiada al señalar que la Máquina de Turing está destinada a ser un dispositivo teórico con el propósito matemático de estudiar la computabilidad y la demostrabilidad (que surge en el contexto del problema Entscheidungsproblem de Hilbert ). Pero no es del todo exacto en las razones para elegir un formalismo simple.

En principio, probar que el problema de detención no es mucho más difícil con modelos más avanzados. De hecho, nuestras "pruebas" a menudo son solo la construcción de una solución. No profundizamos en los argumentos reales (muy tediosos) de que estas construcciones son correctas. Pero cualquiera que escriba un intérprete para un lenguaje completo de Turing hace tanto como cualquier construcción una máquina universal. Bueno, C puede ser un poco complejo, y podríamos querer simplificarlo un poco para tal propósito.

La importancia de tener un modelo simple reside mucho más en el uso que se puede hacer del modelo, que en el establecimiento de sus propiedades (como el Problema de detención, para tomar el ejemplo dado por @jkff).

Por lo general, los grandes teoremas son a menudo teoremas que se pueden expresar de manera muy simple y son aplicables a una amplia gama de problemas. Pero no son necesariamente teoremas fáciles de probar.

En el caso de TM, la importancia de la simplicidad se debe a que muchos resultados se establecen al reducir el problema de detención u otros problemas de TM a problemas que nos interesan (como la ambigüedad de los lenguajes libres de contexto), estableciendo así limitaciones inherentes para resolver estos problemas.

De hecho, aunque es muy intuitivo (que probablemente sea la razón principal de su popularidad), el modelo TM a menudo no es lo suficientemente simple como para usarlo en tales pruebas. Esa es una razón de la importancia de algunos otros modelos, incluso más simples, como el problema de correspondencia posterior , menos intuitivo de analizar, pero más fácil de usar. Pero esto se debe a que estos modelos computacionales a menudo se usan para probar resultados negativos (que se remontan al problema original de Entscheidungs).

Sin embargo, cuando queremos demostrar resultados positivos, como la existencia de un algoritmo para resolver un problema dado, el TM es un dispositivo demasiado simplista. Es mucho más fácil considerar modelos de modo avanzado como la computadora RAM , o una computadora de memoria asociativa , o uno de muchos otros modelos, o incluso simplemente uno de los muchos lenguajes de programación.

Luego, el modelo TM viene solo como un punto de referencia, en particular para el análisis de complejidad, dada la complejidad de reducir estos modelos al modelo TM (generalmente polinomial). La simplicidad del modelo TM otorga mucha credibilidad a las medidas de complejidad (en oposición, para tomar un ejemplo extremo, a las reducciones de cálculo Lambda).

En otras palabras, el modelo TM es a menudo demasiado simplista para diseñar y estudiar algoritmos (resultados positivos), y a menudo demasiado complejo para estudiar la computabilidad (resultados negativos).

Pero parece estar en el lugar correcto para servir como un enlace central para conectarlo todo, con la gran ventaja de ser bastante intuitivo.

Con respecto a las analogías físicas, no hay razón para elegir un modelo sobre otro. Muchos modelos de computación completa de Turing son físicamente realizables (hasta límites ilimitados para el infinito de memoria), ya que no hay razón para considerar una computadora junto con su software como menos física que una computadora "desnuda". Después de todo, el software tiene una representación física, que es parte de la computadora programada. Entonces, dado que todos los modelos de computación son equivalentes desde ese punto de vista, también podríamos elegir uno que sea conveniente para la organización del conocimiento.

Imagine un recién llegado a la geometría preguntando:

¿Hay una analogía física con el triángulo?

¿No es la idea de un triángulo bastante arcaica? Tenemos tantas formas físicas (en lugar de hipotéticas) en nuestra oficina o sala de estar que parecen hacer lo que hace el triángulo.

¿Qué responderías?

Se podría decir que estas preguntas revelan dos conceptos erróneos fundamentales sobre los triángulos:

1. "Los triángulos son puramente hipotéticos". ¡Incorrecto! Si bien son entidades matemáticas, ideales platónicos e hipotéticos en ese sentido, los triángulos son reales : en realidad podemos construirlos en el mundo real. De acuerdo, lo que construimos nunca será un triángulo perfecto, pero nuestra teoría matemática sobre ellos se aplica al mundo real, las leyes que podemos derivar se aplican a las formas en el mundo real, la teoría se puede usar como base para diseñar, construyendo y midiendo formas en el mundo real; Esta es la razón por la cual la teoría se desarrolló en primer lugar.
2. "Los triángulos son inútiles porque no describen las formas que normalmente usamos".¡Incorrecto! Describir las formas reales que encuentras en el mundo real no es su propósito. Si toda su oficina o sala de estar no contiene un solo triángulo, eso no significa que el concepto de triángulo no sea realista o esté desactualizado y es mejor reemplazarlo por otra cosa. Su objetivo principal es como una construcción elemental a partir de la cual se pueden construir todas las formas más complejas en principio, y para lo cual podemos derivar leyes que se aplican a las formas en general. Razonar sobre triángulos nos permite razonar sobre formas en general. Su sala de estar está sujeta a las mismas leyes que hemos derivado para los triángulos, y nuestro conocimiento de estas leyes se utilizó, directa o indirectamente, para construirla. La sala de estar probablemente no tenga un solo triángulo, y mucho menos uno perfecto, pero no nos importa encontrar triángulos allí; podemos. sin embargo, construya una descripción de las formas allí aproximándolas con triángulos, y esto, la triangulación, es algo popular y útil. Entonces, los triángulos son bloques de construcción que nos ayudan a pensar sobre las formas en general.

Lo mismo es cierto para las máquinas de Turing.

Ha pasado tanto tiempo desde que me presentaron la geometría, que realmente no puedo recordar si algún recién llegado realmente tiene estas ideas falsas sobre los triángulos. Pero cuando se trata de máquinas Turing, me encuentro con estas ideas falsas todo el tiempo . Tan a menudo, de hecho, que parece haber algo fundamentalmente incorrecto en cómo se les suele enseñar. ¡Quizás un enfoque de mostrar y contar está en orden!

Entonces, en aras de la integridad:

1. "Las máquinas de Turing son puramente hipotéticas". ¡Incorrecto! Si bien son entidades matemáticas, ideales platónicos e hipotéticos en ese sentido, las máquinas de Turing son reales : en realidad podemos construirlas en el mundo real. De acuerdo, lo que construimos nunca será una Máquina de Turing perfecta, pero nuestra teoría matemática sobre ellos se aplica al mundo real, las leyes que podemos derivar se aplican a los dispositivos de computación en el mundo real, la teoría puede usarse como base para diseño, construcción y medición de dispositivos de computación en el mundo real; Esta es la razón por la cual la teoría se desarrolló en primer lugar.
2. "Las máquinas de Turing son inútiles porque no describen los dispositivos informáticos que normalmente utilizamos".¡Incorrecto! Describir los dispositivos de computación reales que encuentras en el mundo real no es su propósito. Si todo su back office o estudio de entretenimiento en el hogar no contiene una sola máquina de Turing, eso no significa que el concepto de máquina de Turing no sea realista o esté desactualizado y es mejor reemplazarlo por otra cosa. Su propósito principal es como una construcción elemental a partir de la cual todos los dispositivos de computación más complejos pueden construirse en principio, y para lo cual podemos derivar leyes que se aplican a las formas en general. El razonamiento sobre las máquinas de Turing nos permite razonar sobre los dispositivos de computación en general. El hardware y el software de su computadora están sujetos a las mismas leyes que hemos derivado para Turing Machines, y nuestro conocimiento de estas leyes se utilizó, directa o indirectamente, para construirlas, aunque probablemente no lo hagan ' No tengo una sola máquina de Turing. Son las leyes las que nos interesan.

La analogía física que Turing parece haber tenido en mente es una computadora que resuelve problemas con lápiz, papel y borrador. Debes entender que en 1936, una "computadora" era una persona empleada para calcular. Por supuesto, en 1936 la mayoría de las computadoras habrían estado usando máquinas sumadoras, pero Turing no las menciona ya que no son esenciales. Esto es lo que dice, con respecto a la cinta, al tratar de justificar que "los números 'computables' [es decir, los que una máquina de Turing podría calcular] incluyen todos los números que naturalmente serían considerados como computables"

La computación normalmente se realiza escribiendo ciertos símbolos en papel. Podemos suponer que este documento se divide en cuadrados como el libro de aritmética de un niño. En aritmética elemental a veces se usa el carácter bidimensional del papel. Pero tal uso es siempre evitable, y creo que se acordará que el carácter bidimensional del papel no es esencial para el cálculo. Asumo entonces que el cálculo se realiza en papel unidimensional, es decir, en una cinta dividida en cuadrados.

Aunque la computadora ya no es un oficio, la última vez que lo revisé, a los niños todavía se les enseñaba a ejecutar algoritmos usando lápiz y papel como medio de almacenamiento. Entonces, aunque esta analogía puede parecer anticuada o incluso arcaica, aún no es obsoleta.

Para obtener más información, consulte los números computables con una aplicación al problema entscheidungs , especialmente las secciones 1 y 9.

@jkff tiene la idea de the Turing Machine is modeled on the idea of a human with a pen and paperque no es del todo correcto. Pero hay muchas situaciones en las que puede considerarse correcto.

Piensa en el humano como una máquina de Turing bajo cierta proyección de los estados. En otras palabras, si ves a un humano solo durante sus horas de trabajo, entonces durante sus horas de trabajo realiza ciertas tareas. Estas tareas son las tareas básicas para el trabajo.

Si no le importa su vida personal, lo que hace en casa, en su habitación, etc. Entonces puede considerar que esto proyecta su función de transición en una nueva función de transición en la que se ignoran los estados no relacionados con el trabajo. En otras palabras, puede omitir todos los estados y tareas que no tienen nada que ver con su preocupación y perspectiva.

En este modelo, la máquina de Turing sigue el modelo de un humano con un bolígrafo, papel que realiza una tarea fija (es decir, vista en una perspectiva fija). La cinta es lo que escribe en el papel (ignorando todos los papeles o escribiendo en un papel que no escribe para la tarea)

Ahora, si tienes en cuenta otras tareas que él hace, entonces lo que tienes es que tienes una unión de muchas máquinas de Turing en un humano. Pero entonces, ¿qué pasa si cambia de trabajo y hace una tarea diferente? Luego, su estado cerebral cambia a una máquina de Turing diferente cuando se ve bajo una perspectiva diferente en un marco de tiempo diferente.

Si quieres una buena respuesta a tu pregunta, entonces creo que Yuval Filmus la respondió bien. Usa el modelo RAM. Quedarse con eso.