¿Es una máquina de Turing un dispositivo real o un concepto imaginario?

Question

Cuando estoy estudiando sobre máquinas Turing y PDA, estaba pensando que el primer dispositivo informático es la máquina de Turing.

Por lo tanto, pensé que existe una máquina práctica llamada máquina de Turing y sus estados pueden ser representados por algunos dispositivos especiales (digamos como flip-flops) y puede aceptar entradas en cintas magnéticas.

Por lo tanto, he preguntado la duda How input string is represented in magnetic tapes?. Pero por la respuesta y por los detalles que figuran en mi libro, llegué a saber que la máquina de Turing es algo hipotético.

Mi pregunta es, ¿cómo se podría implementar una máquina de Turing en la práctica? Por ejemplo, cómo se usa para verificar errores de ortografía en nuestros procesadores actuales.

¿Las máquinas de Turing están desactualizadas? ¿O todavía se están utilizando?

Answer 1

Las máquinas Turing no se utilizan en la práctica por varias razones. Para empezar, es imposible construir uno, ya que necesitaría infinitos recursos para construir la cinta infinita. Además, las máquinas de Turing son inherentemente más lentas que otros modelos de computación debido a la naturaleza secuencial de su acceso a los datos. Las máquinas de Turing no pueden, por ejemplo, saltar al centro de una matriz sin recorrer primero todos los elementos de la matriz que quiere omitir. Además de eso, las máquinas de Turing son extremadamente difíciles de diseñar. Intenta escribir una máquina de Turing para ordenar una lista de enteros de 32 bits, por ejemplo. (En realidad, por favor no lo haga. ¡Es realmente difícil!)

Esto entonces plantea la pregunta ... ¿por qué estudiar máquinas de Turing en absoluto? Afortunadamente, hay un gran número de razones para hacer esto:

1. de razonar acerca de los límites de lo que podría ser calculado. Debido a que las máquinas de Turing son capaces de simular cualquier computadora en el planeta tierra (o, de acuerdo con la tesis Church-Turing, cualquier dispositivo de computación físicamente realizable), si podemos mostrar los límites de lo que pueden calcular las máquinas de Turing, podemos demostrar los límites de podría esperar lograrse en una computadora real.

2. Para formalizar la definición de un algoritmo. ¿Por qué la búsqueda binaria es un algoritmo mientras que la declaración "adivinar la respuesta" no es? Para responder a esta pregunta, debemos tener un modelo formal de lo que es una computadora y qué significa un algoritmo.Tener la máquina de Turing como modelo de computación nos permite definir rigurosamente lo que es un algoritmo. En realidad, nadie quiere traducir algoritmos al formato, pero la capacidad de hacerlo le da al campo de los algoritmos y la teoría de la computación una sólida base matemática.

3. Para formalizar las definiciones de los algoritmos deterministas y no deterministas. Probablemente la pregunta abierta más grande en ciencias de la computación en este momento es la pregunta de si P = NP. Esta pregunta solo tiene sentido si tiene una definición formal para P y NP, y éstas a su vez requieren definiciones de cómputo determinista y no determinista (aunque técnicamente podrían definirse usando lógica de segundo orden). Tener la máquina de Turing nos permite hablar sobre problemas importantes en NP, junto con darnos una manera de encontrar problemas NP-completos. Por ejemplo, la prueba de que SAT es NP-complete usa el hecho de que SAT puede usarse para codificar una máquina de Turing y su ejecución en una entrada.

Hope this helps!

Answer 2

Es un dispositivo conceptual que no es realizable (debido a la necesidad de cinta infinita). Algunas personas han construido realizaciones físicas de una máquina de Turing, pero no es una verdadera máquina de Turing debido a limitaciones físicas.

Aquí hay un video de uno: http://www.youtube.com/watch?v=E3keLeMwfHY

Answer 3

Es una máquina teórico, el siguiente párrafo de Wikipedia

máquina

A Turing es un dispositivo teórico que manipula símbolos en una tira de cinta de acuerdo con una tabla de reglas A pesar de su simplicidad, una máquina de Turing se puede adaptar para simular la lógica de cualquier algoritmo de computadora, y es particularmente útil para explicar las funciones de una CPU dentro de una computadora. cita en bloque

Esta máquina junto con otras máquinas como la máquina no determinista (no existe en real) son muy útiles en el cálculo y la complejidad de demostrar que un algoritmo es más duro que el otro o de un algoritmo no tiene solución .. .etc

Answer 4

Turing Machine no son exactamente máquinas físicas, sino que básicamente son máquinas conceptuales. El concepto de Turing es una hipótesis y esto es muy difícil de implementar en el mundo real ya que también necesitamos cintas infinitas para una solución pequeña y fácil.