Una máquina de Turing (inglés: máquina de Turing), también conocida como máquina de Turing determinista, es una máquina lógica matemática que abstrae el comportamiento informático humano. Fue propuesta por el matemático británico Alan Turing en 1936.
Cada máquina de Turing toma una cadena de su alfabeto y calcula alguna función fija parcialmente computable. Desde fuera se comporta como un ordenador con un programa fijo. No obstante, podemos codificar la lista de acciones de cualquier máquina de Turing en una cadena. Por lo tanto, podemos construir una máquina de Turing que espera que una cadena que describa la lista de acciones sea seguida por una cadena que describa la entrada en la cinta y, por lo tanto, calcule el esfuerzo computacional para codificar la máquina de Turing.
La importancia práctica de la máquina de Turing
1. Demuestra la teoría general de la computación, afirma la posibilidad de implementación de una computadora y, al mismo tiempo, brinda la arquitectura principal que debería tener la computadora. tener.
2. El modelo de máquina de Turing introduce conceptos como lectura y escritura, algoritmos y lenguajes de programación, lo que rompe en gran medida los conceptos de diseño anteriores de las máquinas informáticas.
3. La teoría del modelo de la máquina de Turing es la teoría central de la disciplina informática, porque la potencia informática definitiva de una computadora es la potencia informática de una máquina de Turing general, y muchos problemas se pueden transformar en este simple. modelo de la máquina de Turing para su consideración.