¿Por qué la gente estudia las máquinas de Turing cuando todas las computadoras reales son autómatas de estado finito?

Creo que la pregunta es afirmar algo que no es cierto según su definición de autómata de estado finito. Me acercaré a mi respuesta como alguien a quien se le ocurren algoritmos.

Hay un par de aspectos de por qué usamos modelos de computación basados ​​en la Máquina de Turing:

-Diseñamos algoritmos que no dependen de la máquina. Si bien la TM es bastante simple, puede formar modelos de computación que se derivan de ella como el modelo de RAM que permite un análisis sorprendentemente simple que es asombrosamente preciso cuando analizamos estos algoritmos con respecto al tamaño de entrada. Los programas que escribimos utilizan lenguajes de programación que suelen ser Turing-complete.

-No hay un modelo de cálculo que podamos usar que pueda resolver más problemas que la máquina de Turing. Se han hecho muchos intentos, pero en la actualidad los únicos son aquellos sobre los que todavía tenemos que probar algo o utilizar cosas que no podemos calcular en el sentido convencional (por ejemplo, números reales). Las máquinas de Turing permiten a los informáticos / matemáticos estudiar lo que podemos y no podemos hacer a través de la computación tal como lo conocemos.

Finalmente, se deriva de los fundamentos matemáticos de la informática. En última instancia, estudiamos la computación desde un punto de vista matemático fundamentalmente para hacer nuestra ciencia (a menos que esté haciendo algo con una noción diferente de computación). Los modelos de cómputo nos permiten analizar algoritmos y decir (probar) cosas sobre lo que podemos y no podemos resolver. Las máquinas de Turing nos permiten hacer esto y los modelos que se derivan de este modelo son extremadamente valiosos y precisos en la práctica. No implementamos nuestro hardware como Turing Machines, pero el extremo algorítmico de este se deriva de modelos que se reducen a Turing Machines. Diseñamos algoritmos con respecto a problemas, que normalmente tienen infinitos casos (en la práctica esto está limitado por un gran conjunto de números), pero cosas como los algoritmos son matemáticos (computacionales). ¿Cómo puedes saber que tu algoritmo funciona? Demostramos esto matemáticamente. Los modelos de computación nos permiten analizar estos algoritmos de forma independiente de la máquina.

¡Espero que esto ayude!

La afirmación “todas las computadoras son de estado finito” es cuestionable.

Me gusta pensar que mi computadora tiene potencialmente una cinta infinita; si me quedo sin memoria, simplemente puedo obtener más o extenderla de alguna otra manera, como usar otra computadora / servidor externo.

Eso, por supuesto, no tiene nada que decir sobre la utilidad de los TM.
La importancia de las máquinas de Turing se deriva del hecho de que existen máquinas de Turing universales. Debido a eso, puede usar el razonamiento diagonal para probar que el problema de Halting no es computable. Es decir, no hay una máquina de Turing que pueda resolverla.

Las máquinas de Turing pueden haber servido de inspiración para la arquitectura de von Neumann (me refiero a almacenar programas como números), pero hoy en día se utilizan principalmente para formalizar teoremas de posibilidad / imposibilidad y no tienen ninguna aplicación práctica en particular (ya que son demasiado abstractas para realmente implementan en hardware, y para la programación real, carecen de herramientas de abstracción comunes en los lenguajes modernos).

La emocionante historia de cómo los autómatas finitos se convirtieron en una rama de la informática ilustra su amplia gama de aplicaciones. Las primeras personas que consideraron el concepto de una máquina de estado finito incluyeron un equipo de biólogos, psicólogos, matemáticos, ingenieros y algunos de los primeros informáticos. Todos compartían un interés común: modelar el proceso de pensamiento humano, ya sea en el cerebro o en una computadora. Warren McCulloch y Walter Pitts, dos neurofisiólogos, fueron los primeros en presentar una descripción de autómatas finitos en 1943. Su artículo, titulado “Un cálculo lógico inmanente en la actividad nerviosa”, hizo importantes contribuciones al estudio de la teoría de redes neuronales, teoría de Autómatas, la teoría de la computación y la cibernética. Más tarde, dos científicos informáticos, GH Mealy y EF Moore, generalizaron la teoría a máquinas mucho más poderosas en papeles separados, publicados en 1955-56. Las máquinas de estado finito, la máquina Mealy y la máquina Moore, se nombran en reconocimiento a su trabajo. Mientras que la máquina Mealy determina sus salidas a través del estado actual y la entrada, la salida de la máquina Moore se basa únicamente en el estado actual.

Como respuesta del usuario de Quora a ¿Por qué las personas estudian las máquinas de Turing cuando todas las computadoras reales son autómatas de estado finito? implica, al considerar una computadora como FSM, usted codifica la memoria como estados. Eso es válido, pero no es productivo. Para razonar acerca de un sistema, elija la abstracción más productiva y, como respuesta del Usuario de Quora, a ¿Por qué las personas estudian las máquinas de Turing cuando todas las computadoras reales son autómatas de estado finito? Señala, ese es el lugar donde se dice que una computadora tiene una cinta infinita.

Porque “personas” en su pregunta, de hecho, significa “matemáticos” y matemáticos no son ingenieros.

Claramente, cualquier computadora real que pueda construirse es un autómata de estado finito. Incluso cuando pudiéramos usar cada átomo en el universo para construir una computadora, seguiría siendo un autómata de estado finito.

Pero una máquina de Turing es “más potente” y el “caso genérico”, por lo que es más interesante para los matemáticos.

Afortunadamente hay más y más “personas” con un punto de vista más práctico. La idea de que los lenguajes de programación completos de Turing deben considerarse dañinos se hace más común actualmente.

El hecho de que, en el caso general, no se pueda probar que un programa en una lengua completa de Turing sea formalmente correcto, contradice la necesidad de programas seguros (probablemente). Sin embargo, los programas están diseñados para ejecutarse en computadoras físicas (que son “solo” máquinas de estados finitos) al final. Eso es una locura. Todos los “poderes” primordiales de expresión que un lenguaje completo de Turing le da son inútiles para el caso general porque no hay una “máquina de Turing real” que pueda ejecutar todos los programas posibles. Pero hereda el problema de detención con todas sus implicaciones cuando usa un lenguaje completo de Turing. También siempre habrá programas válidos en cualquier lenguaje completo de Turing que definitivamente “explotará” en algún hardware pero se ejecutará en otro; amablemente nunca se puede saber de antemano.

Dado que esta es una mala situación, hay investigaciones actuales para mejorarla mediante el uso de un modelo de “sub-turing” para la computación (que de todos modos coincide con la realidad del hardware físico mucho más cerca).

La palabra clave aquí es: “lenguaje total”.

Los ejemplos prácticos incluyen “idris” (Un lenguaje con tipos dependientes) o “agda” (The Agda Wiki – Agda) para el tipo de “idiomas funcionales totales” o “crema” (Crema) para el enfoque imperativo.

Las máquinas Ihmo Turing seguirán siendo un dominio interesante para los estudios en el campo de la informática teórica, pero la relevancia práctica disminuirá dramáticamente en el futuro.

Al igual que muchas otras abstracciones matemáticas fascinantes (y valiosas), ¡son “demasiado poderosas” para ser aplicadas al mundo físico! Como una simple demostración de lo que quiero decir: ¿Alguna vez has visto a alguien (a excepción de Chuck Norris de maldición ;-)) contar hasta Aleph-nada?

Tres razones:

1. Considerar computadoras enteras como FSM no es muy productivo. Si una máquina tiene 8 gigabytes de RAM, tiene 64 mil millones de bits de información, por lo que el número de estados posibles es 2 ^ 64,000,000,000. Eso es demasiado para analizar uno por uno.

2. Uno de los usos teóricos clave de los TM es determinar qué tipo de programas son posibles en teoría, sin limitaciones de almacenamiento. El resultado clave de los TM no funciona para las FSM, ya que siempre se puede resolver el problema de la detención de las FSM.

3. Que alguna tarea de programación es imposible en un FSM puede ser porque no tiene suficiente memoria. Las máquinas de Turing eliminan este desorden, facilitando mucho el análisis.