¿Diferencia entre una máquina de turing y una máquina de estados finitos?

27

Estoy haciendo una presentación sobre las máquinas Turing y quería dar algunos antecedentes sobre los FSM antes de presentar las máquinas Turing. El problema es que realmente no sé qué es MUY diferente el uno del otro.

Esto es lo que sé que es diferente:

FSM tiene estados secuenciales dependiendo de la condición correspondiente cumplida, mientras que las máquinas Turing operan en una "Cinta" infinita con un cabezal que lee y escribe.

Hay más margen de error en los FSM ya que podemos caer fácilmente en un estado sin fin, mientras que no es tanto para las máquinas Turing ya que podemos retroceder y cambiar las cosas.

Pero aparte de eso, no conozco muchas más diferencias que hacen que las máquinas de Turing sean mejores que las de FSM.

¿Podrías ayudarme?

terminology turing-machines finite-automata machine-models Julio García
fuente
2
¡No es difícil buscar en Google "FSM vs. Turing Machine"! Esa es la parte divertida de hacer tu propia investigación. La principal diferencia es que una máquina de Turing tiene una "memoria" infinita, pero una FSM no.
Dai
Ok, hice trampa un poco allí>.> ;; Gotcha! ¡Gracias!
Julio García
3
El argumento sobre "error" no es correcto. Prueba wikipedia y libros de cursos. Vea cuáles son sus diferencias básicas, el propósito de usar cada una (por ejemplo, cuando no podemos elegir un FSM sobre TM) y su relación.
Parham
@MahmoudAlimohamadi, lo que quiero decir es que hay una mayor posibilidad de que un fsm aterrice en un estado sin fin.
Julio García
@Dai: Es más correcto decir que una máquina de Turing puede usar una cantidad arbitrariamente grande de memoria. La cantidad utilizada nunca es infinita.
reinierpost

Respuestas:

24

La principal distinción entre cómo funcionan los DFA (Deterministic Finite Automaton) y los TM es en términos de cómo usan la memoria.

Intuitivamente, los DFA no tienen memoria "scratch" en absoluto; la configuración de un DFA se explica completamente por el estado en el que se encuentra actualmente y su progreso actual en la lectura de la entrada.

Intuitivamente, los TM tienen una memoria "scratch" en forma de cinta; La configuración de una TM consiste tanto en su estado actual como en el contenido actual de la cinta, que la TM puede cambiar a medida que se ejecuta.

Un DFA puede considerarse como un TM que no cambia ningún símbolo de cinta ni mueve la cabeza hacia la izquierda. Estas restricciones hacen imposible reconocer ciertos idiomas que pueden ser aceptados por TM.

Tenga en cuenta que uso el término "DFA" en lugar de "FSM", ya que, técnicamente, consideraría que una TM es una máquina de estados finitos, ya que las TM por definición tienen un número finito de estados. La diferencia entre DFA y TM está en el número de configuraciones, que es igual al número de estados para un DFA, pero es infinitamente grande para un TM.

Patrick87
fuente
Ah, lo tengo. Una pregunta con respecto a la parte "sin memoria": vi un ejemplo de máquina expendedora que sumaba las monedas distribuidas. ¿Cómo saben cuánto dinero hay si no tiene memoria?
Julio García
@JulioGarcia Es difícil de decir sin saber exactamente lo que viste. Hay máquinas Moore y Mealy que pueden generar símbolos en las transiciones. La actividad de una máquina expendedora podría modelarse mejor mediante uno de esos mecanismos. Un DFA de vainilla solo acepta y rechaza cadenas ... una máquina expendedora debe "aceptar" cualquier "cadena" de monedas. Dependiendo de cómo modele los efectos secundarios adicionales de dar un cambio, el tipo de memoria de memoria virtual necesaria puede ser el acceso aleatorio infinito o ninguno.
Patrick87
Sin ver su ejemplo, no puedo estar completamente seguro, pero tengo dos conjeturas. Una es que no sabe cuánto dinero hay: simplemente supone que hay suficiente. No querría construir una máquina expendedora real de esa manera, pero sigue siendo un ejemplo útil del concepto. La otra posibilidad es que no es realmente un FSA "puro": está conectado a un sensor que puede obtener estos datos desde "fuera" de la máquina de alguna manera. La máquina no sabe ni le importa de dónde provienen los datos, y no puede almacenar nada en el sensor (por lo que no es realmente "memoria"), pero aún puede actuar según lo que ve allí.
The Spooniest
16

Las máquinas de Turing describen una clase de idiomas mucho más amplia, la clase de lenguajes recursivamente enumerables. Las máquinas de estados finitos describen la clase de lenguajes regulares.

Las máquinas de estados finitos no tienen "memoria", está limitada por sus estados.

Una máquina de estado finito es una máquina de Turing restringida donde la cabeza solo puede realizar operaciones de "lectura" y siempre se mueve de izquierda a derecha.

Tome este lenguaje como ejemplo:

L={unayosiyoEl | yo> =0 0}

Debido a que las máquinas de estados finitos son limitadas en el sentido de que no tienen memoria, no se puede construir un FSM que acepte L.

Para resumir:

Las máquinas de estados finitos describen una pequeña clase de lenguajes donde no se necesita memoria.

Las máquinas de Turing son la descripción matemática de una computadora y aceptan una clase de lenguajes mucho más amplia que los FSM.

Las máquinas de Turing tienen más poder computacional que FSM. Hay tareas que ningún FSM puede hacer, pero que Turing Machines puede hacer.

mrjasmin
fuente
3

Tenía la misma duda y vi dos videos muy esclarecedores y una explicación sobre Quora de la siguiente manera:

Una máquina de estados finitos es solo un conjunto de estados y transiciones. La única memoria que tiene es en qué estado está. Por lo tanto, el número de estados de memoria es ... finito.

Una máquina de Turing es una máquina de estados finitos más una memoria de cinta. Cada transición puede ir acompañada de una operación en la cinta (mover, leer, escribir).

He entendido que una máquina de Turing usa / tiene una máquina de estado finito como parte de su procedimiento operativo, además de agregarle memoria editable.

¡Mire también esos dos videos, están iluminando!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

usuario5193682
fuente
2

Hasta donde yo entiendo las diferencias entre (modelo estándar) Turing y (modelo estándar) Mealy Machines:

  • Las máquinas Turing leen y escriben en la misma cinta frente a las máquinas Mealy leen en una cinta de entrada y escriben en otra cinta de salida
  • Las máquinas de Turing pueden cambiar la "dirección de la cinta" (proceder hacia la izquierda o hacia la derecha [o detener]) frente a las máquinas Mealy solo pueden avanzar hacia la derecha (es por eso que no hay una dirección establecida {L, R, H} en la función de transición de la máquina Mealy [es implícitamente {R}, lo que significa que no hay otra opción])
  • Las máquinas de Turing pueden detenerse en cualquier celda de cinta frente a las máquinas Mealy leen la entrada completa y luego dejan de aceptarla o rechazarla
Michael Klaube
fuente
-3

Una máquina de Turing puede almacenar, como parte de la cinta, cosas que desea recordar.

richard mullins
fuente
55
No está claro qué quiere decir con "eso", pero tanto las máquinas de Turing como los FSM pueden hacer esto, por lo que no hay diferencia.
David Richerby
@DavidRicherby Pero un FSM solo puede almacenar una cantidad predeterminada, mientras que las máquinas de Turing pueden almacenar todo lo que quieran. Esa es la diferencia fundamental.
Gilles 'SO- deja de ser malvado'
1
@Gilles estuvo de acuerdo, pero eso no es lo que dice la respuesta.
David Richerby