Las computadoras reales tienen solo un número finito de estados, entonces, ¿cuál es la relevancia de las máquinas de Turing para las computadoras reales?

42

Las computadoras reales tienen memoria limitada y solo un número finito de estados. Por lo tanto, son esencialmente autómatas finitos. ¿Por qué los informáticos teóricos usan las máquinas de Turing (y otros modelos equivalentes) para estudiar computadoras? ¿Cuál es el punto de estudiar estos modelos mucho más fuertes con respecto a las computadoras reales? ¿Por qué el modelo de autómatas finitos no es suficiente?

Rahul
fuente
77
@Kaveh La gente suele decir que sí, las computadoras utilizadas en la práctica son FSM, pero las FSM son demasiado grandes y las propiedades estructurales interesantes se pierden en la vista FSM. Nunca he visto una explicación no manual. Por lo tanto, la pregunta es sobre el tema aquí.
Martin Berger
15
La verdadera pregunta es, ¿por qué estudiar las máquinas de Turing, cuando usamos el modelo RAM cuando analizamos algoritmos?
Yuval Filmus
39
Porque a veces es una mejor aproximación a que . 10000000000000000000000000000000 100000000000000000000000000000001000000000000000000000000000000010000000000000000000000000000000
Andrej Bauer
30
Recuerde, el problema no resuelto más famoso en la informática teórica de hoy es: ¿ puede un tipo de computadora imaginaria físicamente imposible resolver problemas tan rápido como una computadora imaginaria aún más físicamente imposible ? No confunda la informática teórica con la ingeniería informática práctica; Los detalles del mundo físico no son particularmente relevantes.
Eric Lippert
23
Los materiales reales están hechos de átomos y son de naturaleza discreta, entonces, ¿por qué estudiar integrales?
Peter Shor

Respuestas:

32

Hay dos enfoques al considerar esta pregunta: histórico que se refiere a cómo se descubrieron los conceptos y técnico que explica por qué ciertos conceptos fueron adoptados y otros abandonados o incluso olvidados.

Históricamente, la máquina de Turing es quizás el modelo más intuitivo de varios desarrollados que intentan responder al problema de Entscheidung . Esto está íntimamente relacionado con el gran esfuerzo en las primeras décadas del siglo XX para axiomatizar completamente las matemáticas. La esperanza era que una vez que haya demostrado que un pequeño conjunto de axiomas es correcto (lo que requeriría un esfuerzo considerable), podría usar un método sistemático para obtener una prueba de la declaración lógica que le interesaba. Incluso si alguien considerara autómatas finitos en este contexto, serían descartados rápidamente ya que no pueden calcular incluso funciones simples.

Técnicamente, la afirmación de que todas las computadoras son autómatas finitos es falsa. Un autómata finito tiene memoria constante que no puede modificarse dependiendo del tamaño de la entrada. No hay ninguna limitación, ya sea en matemáticas o en realidad, que impida proporcionar cinta adicional, discos duros, RAM u otras formas de memoria, una vez que se haya utilizado la memoria en la máquina. Creo que esto a menudo se empleó en los primeros días de la informática, cuando incluso los cálculos simples podían llenar la memoria, mientras que ahora para la mayoría de los problemas y con la infraestructura moderna que permite una administración de memoria mucho más eficiente, la mayoría de las veces no es un problema .


EDITAR: consideré los dos puntos planteados en los comentarios, pero elegí no incluirlos por brevedad y por el tiempo que tenía disponible para escribir la respuesta. Este es mi razonamiento de por qué creo que estos puntos no disminuyen la efectividad de las máquinas de Turing para simular computadoras modernas, especialmente en comparación con los autómatas finitos:

  • Permítanme abordar primero el problema físico de un límite en la memoria del universo. En primer lugar, no sabemos realmente si el universo es finito o no. Además, el concepto del universo observable que es, por definición, finito, también es irrelevante para un usuario que puede viajar a cualquier punto del universo observable para usar la memoria. La razón es que el universo observable se refiere a lo que podemos observar desde un punto específico, es decir, la Tierra, y sería diferente si el observador pudiera viajar a una ubicación diferente en el universo. Por lo tanto, cualquier argumentación sobre el universo observable se convierte en la cuestión de la finitud del universo. Pero supongamos que a través de algún avance adquirimos conocimiento de que el universo es realmente finito. Aunque esto tendría un gran impacto en asuntos científicos, Dudo que tenga algún impacto en el uso de las computadoras. En pocas palabras, podría ser que, en principio, las computadoras son de hecho autómatas finitos y no máquinas de Turing. Pero para la gran mayoría de los cálculos y con toda probabilidad todos los cálculos en los que los humanos están interesados, las máquinas de Turing y la teoría asociada nos ofrecen una mejor comprensión. En un crudo ejemplo, aunque sabemos que la física newtoniana está esencialmente equivocada, dudo que los ingenieros mecánicos usen principalmente la física cuántica para diseñar automóviles o maquinaria de fábrica; Los casos de esquina donde esto se necesita se pueden tratar a nivel individual. Pero para la gran mayoría de los cálculos y con toda probabilidad todos los cálculos en los que los humanos están interesados, las máquinas de Turing y la teoría asociada nos ofrecen una mejor comprensión. En un crudo ejemplo, aunque sabemos que la física newtoniana está esencialmente equivocada, dudo que los ingenieros mecánicos usen principalmente la física cuántica para diseñar automóviles o maquinaria de fábrica; Los casos de esquina donde esto es necesario se pueden tratar a nivel individual. Pero para la gran mayoría de los cálculos y con toda probabilidad todos los cálculos en los que los humanos están interesados, las máquinas de Turing y la teoría asociada nos ofrecen una mejor comprensión. En un crudo ejemplo, aunque sabemos que la física newtoniana está esencialmente equivocada, dudo que los ingenieros mecánicos usen principalmente la física cuántica para diseñar automóviles o maquinaria de fábrica; Los casos de esquina donde esto es necesario se pueden tratar a nivel individual.

  • Cualquier restricción técnica como los buses y el direccionamiento son simplemente limitaciones técnicas del hardware existente y pueden superarse físicamente. La razón por la que esto no es cierto para las computadoras actuales es porque el direccionamiento de 64 bits nos permitió mover el límite superior en el espacio de direcciones a pocas alturas si alguna aplicación puede lograrlo. Además, la implementación de un sistema de direccionamiento "extensible" podría tener un impacto en la gran mayoría de los cálculos que no lo necesitarán y, por lo tanto, es ineficiente. Nada le impide organizar un sistema de direccionamiento jerárquico, por ejemplo, para dos niveles, la primera dirección podría referirse a cualquiera de los bancos de memoria y luego cada banco tiene 2 64264264diferentes direcciones Esencialmente, la creación de redes es una excelente manera de hacer esto, cada máquina solo se preocupa por su memoria local, pero pueden calcular juntas.

chazisop
fuente
44
La segunda parte de esta respuesta es incorrecta. Las computadoras son autómatas de estado finito, incluso si compraste toda la RAM y otro hardware que pudieras. La cantidad de RAM que puede conectar a una computadora está limitada por el ancho de su bus de direcciones, y lo mismo se aplica a los discos y otros periféricos.
Emil Jeřábek apoya a Monica el
12
@ EmilJeřábek no es cierto. Las interfaces seriales no tienen un bus de direcciones, y la cantidad de datos a los que puedo acceder en Internet no está limitada por ninguna propiedad de mi computadora.
Deja de dañar a Mónica el
55
@OrangeDog pero el universo seguiría siendo poner un límite a la cantidad de datos pueden ser almacenados en el universo observable
monstruo de trinquete
99
@ratchetfreak como lo demuestra la máquina de Turing, solo necesitas acceso local: el "final" actual de la cinta no tiene por qué estar dentro del universo observable;)
Deja de dañar a Monica el
66
Al mencionar la historia, vale la pena citar la revisión de Church del artículo de Turing, en el sentido de que las máquinas de Turing tienen "la ventaja de hacer que la identificación sea efectiva ... evidente de inmediato". Es decir, para las personas que intentaban convencerse de que habían capturado todo lo que podía computarse, la definición de Turing era convincente.
Jim Hefferon el
44

Para completar las otras respuestas: creo que Turing Machine es una mejor abstracción de lo que hacen las computadoras que los autómatas finitos. De hecho, la principal diferencia entre los dos modelos es que con autómatas finitos, esperamos tratar datos que son más grandes que el espacio de estado, y Turing Machine es un modelo al revés (espacio de estado >> datos) al hacer el estado espacio infinito Este infinito puede ser percibido como una abstracción de "muy grande frente al tamaño de los datos". Al escribir un programa de computadora, intenta ahorrar espacio para la eficiencia, pero generalmente asume que no estará limitado por la cantidad total de espacio en la computadora. Esa es parte de la razón por la cual las máquinas de Turing son una mejor abstracción de las computadoras que los autómatas finitos.

Denis
fuente
14
Esta es mi humilde opinión la respuesta correcta. Las razones son puramente pragmáticas, las máquinas de Turing funcionan mejor que los autómatas finitos para explicar qué hacen las computadoras en las escalas involucradas.
Emil Jeřábek apoya a Monica el
3
Estoy de acuerdo con esto, excepto la oración "generalmente asume que no estará limitado por la cantidad total de espacio en la computadora". Por el contrario, casi cualquier programa no trivial está limitado por el espacio disponible y los programadores hacen todo lo posible para tratarlo (por ejemplo, recolección de basura para la reutilización automática de memoria), pero (1) no hay nada que podamos hacer al respecto, y (2) nos restringimos a entradas lo suficientemente pequeñas. Es digno de mención que los TM nos dan un manejo natural del tamaño del problema, y ​​que los algoritmos tienden a cerrarse hacia abajo con esta noción natural del tamaño del problema.
Martin Berger
2
@MartinBerger Re "casi cualquier programa no trivial está limitado por el espacio disponible y los programadores hacen todo lo posible para ocuparse de él (por ejemplo, recolección de basura para la reutilización automática de memoria)": afirmo que los programas escritos para sistemas con recolección de basura consideran ese sistema, incluido el gc , como la máquina contra la que programan. El recolector de basura no es parte del programa; es parte de un esfuerzo por proporcionar precisamente lo que Denis dijo: una máquina para programar contra la cual tiene recursos de memoria virtualmente ilimitados.
Peter - Restablece a Mónica el
2
@ PeterA.Schneider, no estoy de acuerdo. La razón de usar el GC proporcionado por el lenguaje en tiempo de ejecución es uno de los aspectos económicos del desarrollo de software: el mecanismo de administración de memoria específico del programa es más eficiente que el GC y la mayoría de los programadores lo preferirían si pudieran hacerlo de manera segura y económica. Pero no pueden, así que prefiera jugar con seguridad y usar el GC ambiental cuyo costo se amortiza en una gran cantidad de programas. En ese sentido, el uso de GC hará un gran esfuerzo para lidiar con la memoria de finitud.
Martin Berger
2
Las máquinas de Turing no son abstracciones de lo que hacen las computadoras, son abstracciones de lo que hace la informática, y las computadoras se construyeron después de eso. Las computadoras hacen la mayoría de sus cálculos utilizando una cantidad fija de memoria de trabajo interna, pero las máquinas de Turing no fueron inventadas para razonar sobre el cálculo con una cantidad limitada de memoria de trabajo.
reinierpost
10

Andrej Bauer dio una razón importante en los comentarios:

1000000000000000000000000000000010000000000000000000000000000000

Permítanme completar las otras respuestas por algunos puntos, que probablemente eran demasiado obvios para mencionar:

  • Si su objetivo es estudiar computadoras reales, entonces los autómatas finitos y las máquinas de Turing a menudo serán modelos demasiado simples para las preguntas relevantes. Las computadoras reales tienen múltiples núcleos de procesamiento con una jerarquía de caché (o algún otro esquema de administración inteligente), acceso a una cantidad decente de memoria rápida, acceso a una gran cantidad de memoria externa lenta (discos duros) y pueden comunicarse con otras computadoras similares en un velocidad aproximadamente comparable a la velocidad de acceso a la memoria externa lenta.
  • Si ahora se pregunta por qué necesita todos esos detalles, resulta que su objetivo real es el estudio de instancias de problemas y qué tan eficientemente puede resolverlos. Si está hablando de computadoras reales, esto también puede significar que realice experimentos con instancias de problemas reales en diferentes tipos de arquitecturas informáticas (reales).
  • El modelo de computadoras reales descrito anteriormente todavía está idealizado, porque ignora los diversos modos de falla de las computadoras reales. Debido a que la falla de apagado puede ser más frecuente que la falla del disco duro (y los discos duros pueden tener copias de seguridad de todos modos), ciertos dominios problemáticos como la operación confiable de la base de datos pueden necesitar tener eso en cuenta.
  • Π10
Thomas Klimpel
fuente
8

Un formalismo es útil o no, basado en lo que la gente quiere usar el formalismo para modelar y comprender.

La máquina de Turing es un formalismo útil para comprender los programas . Vale la pena entender los programas; La mayor parte del cómputo real es realizado por programas, en lugar de por máquinas especiales. El formalismo de la máquina de Turing nos permite modelar preocupaciones importantes del mundo real, como la complejidad del tiempo y el espacio. Es mucho menos natural tratar de estudiar estas nociones utilizando autómatas de estado finito.

Las máquinas de Turing no son muy útiles cuando se trata de estudiar la complejidad de calcular funciones finitas (por ejemplo, funciones cuyo dominio consiste en entradas de longitud como máximo 10 millones). La complejidad del circuito es mucho mejor para describir la complejidad de las funciones finitas ... pero las máquinas de Turing a su vez han sido muy útiles para comprender la complejidad del circuito.

Los autómatas finitos también han sido útiles para comprender la complejidad del circuito; Todos estos modelos tienen su lugar en el arsenal matemático.

Rechazo el argumento que dice que los autómatas de estado finito son un mejor modelo de realidad simplemente porque las computadoras del mundo real tienen solo un número finito de estados internos. El estudio de autómatas de estado finito trata de manera crucial las entradas que provienen del conjunto infinito de cadenas, mientras que las computadoras del mundo real manejan entradas de solo una longitud máxima fija (a menos que creas que vivimos en un universo infinito, ya sea en términos de espacio o tiempo).

Un modelo debe juzgarse en términos de su utilidad para comprender los aspectos de la realidad que nos interesan. O (alternativamente) en términos de su utilidad para comprender un universo matemático que las personas encuentran lo suficientemente convincente, incluso si ese universo matemático no tiene una manifestación física obvia.

Las máquinas de Turing, las máquinas de estado finito y los circuitos (y otros modelos además) han demostrado su utilidad.

Eric Allender
fuente
6

Las computadoras reales no son FSA. Una computadora real es una computadora universal, en el sentido de que podemos describir una computadora para que una computadora emule y la computadora la emulará. Para muchos ejemplos, busque "máquina virtual".

Es posible construir una máquina universal de Turing: una TM que recibe una descripción de otra TM y luego emula el funcionamiento de esa TM en una entrada suministrada.

n22n

Como punto de partida en la literatura, puedo recomendar " Sobre la existencia de autómatas universales finitos o pushdown ", que estudia la inexistencia de autómatas universales. También puede mirar sus referencias (y así sucesivamente).

Eric Towers
fuente
3
Este es un enfoque útil para comprender intuitivamente diferentes niveles de "poder computacional". Sin embargo, OP parece pensar que las computadoras reales son FSM porque el número de estados es limitado, por ejemplo, debido a la RAM finita. Según su argumento, esto significa que las computadoras reales se parecen más a los FSM que a las máquinas de Turing porque no puedo duplicar libremente el número de estados en una máquina simulada; No tengo una cinta infinita como almacenamiento.
amon
1
Las máquinas de Turing tampoco necesitan tener una cinta infinita. Las computadoras pueden usar una cantidad arbitrariamente grande de almacenamiento externo en sus cálculos (y se vuelve particularmente fácil con los proveedores de nube que tenemos hoy), por lo que son fundamentalmente como Turing Machines en lugar de FSM.
reinierpost
1
Si suponemos que una computadora tiene una cantidad fija de memoria, se quedará sin memoria al simular una computadora con más memoria, por lo que con esa suposición no es realmente universal.
Kaveh
3

Lo que hace que la máquina Turing sea especial es que, si bien es muy, muy simple, puede ejecutar todos los (clases de) algoritmos que podamos imaginar. No hay una máquina conocida que sea más poderosa (ya que puede ejecutar algoritmos que la máquina Turing no es capaz de hacer).

Siendo mecánicamente simple, es fácil mostrar si, o en qué grado, otras máquinas son equivalentes a una máquina de Turing. Esto a su vez hace que sea relativamente fácil mostrar si una computadora (o lenguaje de computadora) es verdaderamente universal (c / f "Turing-complete").

AnoE
fuente
La pregunta es sobre la relación del modelo de máquina de Turing con las computadoras reales. Si suponemos que una computadora tiene una cantidad fija de memoria, no es realmente universal.
Kaveh
1

¿Por qué el modelo de autómatas finitos no es suficiente?

Si bien otras respuestas ya han mencionado muchos aspectos relevantes, creo que la mayor ventaja de las máquinas Turing sobre los autómatas finitos es la separación de datos y programas . Esto le permite analizar un programa bastante finito y hacer declaraciones sobre cómo ese programa manejaría diferentes entradas, sin restringir el tamaño de la entrada.

Si bien es teóricamente posible describir una computadora real y algo así como una máquina de Turing con cinta finita como una máquina de estado, eso no es realmente factible: el número de estados es exponencial en la cantidad de memoria que tiene su máquina y el finito general el formalismo de autómatas de estado requiere que haga una lista explícita de las transiciones entre estos estados. Entonces, para un autómata de estado finito general de ese tamaño, es bastante inviable hacer deducciones basadas en una enumeración completa de todas las transiciones de estado.

Por supuesto, en una computadora real, las transiciones de estados no pueden ocurrir arbitrariamente. No hay un comando para intercambiar un tercio de los bits en la memoria en un solo paso del cálculo. Por lo tanto, podría intentar obtener una especificación más compacta para las transiciones de estado. Algo así como la especificación del conjunto de instrucciones de su arquitectura. Por supuesto, las arquitecturas informáticas reales son complicadas en aras del rendimiento, por lo que podría simplificar esto aún más, a un conjunto de instrucciones muy simple, que solo realiza pasos muy pequeños con entradas y salidas muy limitadas. Al final, es posible que su arquitectura se parezca a algo así como un intérprete de máquina de Turing: usando algunos bits de código de programa y un bit de entrada, genere un bit de salida y se mueva en su código de programa.

Una alternativa sería utilizar los estados de un autómata de estado finito solo para representar los datos que procesa el programa, mientras codifica el programa en las transiciones de estado. Eso implicaría el mismo problema de cómo enumerar todos los estados, y una representación compacta podría estar nuevamente cerca de lo que hace una máquina de Turing.

¿Cuál es el punto de estudiar estos modelos mucho más fuertes con respecto a las computadoras reales?

En general, diría que una máquina Turing de cinta finita probablemente sería un mejor modelo para las computadoras reales. Pero para muchas preguntas científicas, la distinción entre una cinta finita pero grande e infinita es irrelevante, por lo que solo reclamar una cinta infinita facilita las cosas. Para otras preguntas, la cantidad de cinta utilizada está en el centro de la pregunta, pero el modelo le permite hablar fácilmente sobre la cantidad de uso de la cinta sin la molestia de especificar qué sucede si el cálculo se queda sin cinta.

MvG
fuente
1

La mayoría de los problemas requieren máquinas de Turing de tamaño finito

Si bien suponer que la cinta no limitada es una simplificación útil, la mayoría de los problemas / algoritmos requieren una cantidad limitada de cinta, y los límites de la memoria requerida (posiblemente según el tamaño de la entrada) pueden analizarse y a menudo demostrarse.

Esto a menudo también se generaliza a otros tipos de computadoras (para las cuales el análisis o la prueba encuadernados pueden ser mucho más desordenados que en una máquina Turing), y permite estimar la cantidad de almacenamiento temporal requerido para un problema en particular. ¿Se puede hacer en una cantidad fija? ¿del espacio? Proporcional a la entrada? ¿Requiere cantidades exponenciales de espacio a medida que crecen las entradas?

Pedro es
fuente
1

Una característica importante de las máquinas de Turing que los autómatas finitos no comparten es que pueden escalar la cantidad de memoria necesaria para resolver el problema con el tamaño del problema .

nn2

El punto: muchos problemas tienen soluciones naturales que usan más memoria cuanto mayor es el problema. Por lo tanto, es natural describir estas soluciones con representaciones que pueden usar memoria infinita, no porque cualquier instancia use cantidades infinitas, sino porque hay una instancia que usa cada cantidad. Puede hacerlo con máquinas de turing, pero también con secuencias de autómatas finitos.

josinalvo
fuente
En una nota relacionada, si una máquina Turing con N estados se inicia con una cinta que tiene un número finito de C caracteres no en blanco antes y después de la posición inicial, habrá algún número T (N, C) tal que cualquier máquina lo que terminará podría ser emulado por una máquina, una máquina cuya cinta estaba limitada a caracteres T (N, C).
supercat
-2

Las computadoras reales tienen memoria limitada y solo un número finito de estados. Por lo tanto, son esencialmente autómatas finitos.

Las máquinas de Turing son derivados de autómatas finitos. Las máquinas de Turing son prácticamente arquitectura von Nuemann.

Jesse Enjaian
fuente