¿Qué es una máquina de Turing?

En primer lugar, ¿qué es un lenguaje de reconocimiento de máquina de Turing? No es que ingresar un archivo en la máquina de Turing se llame máquina de Turing para reconocer el idioma. Todos sabemos que una máquina de Turing es una máquina computacional que ingresa una cadena, que puede ingresar al estado de aceptación, rechazar el estado o no detenerse nunca. Sea M una máquina de Turing que acepta una cadena S si entra en estado de aceptación y se apaga después de ejecutar M en una cadena de entrada S. El conjunto de todas las cadenas aceptadas por M se denomina lenguaje reconocido por M, o lenguaje M para abreviar, denotado como L(M). Si se ingresa una cadena en L en M, M se cerrará y entrará en el estado de aceptación. ¿Qué sucede si la cadena en L no es una entrada para M? Solo hay dos casos: M se detiene y entra en estado de rechazo, o M no se detiene. Los problemas resueltos por las máquinas de Turing son todos problemas computacionales, es decir, utilizando lo conocido para encontrar problemas desconocidos. ¿Qué crees que es posible en matemáticas que pueda hacer esto? es una función, simplemente y=f(x). Las máquinas de Turing son exactamente equivalentes a funciones computables. Ahora, usemos este ejemplo para ilustrar cómo la solución y=f(x) es equivalente al lenguaje reconocido por la máquina de Turing: lenguaje L={|y=f(x)}, si la máquina de Turing La máquina reconoce este lenguaje, debe calcular f(x), y si y es igual a f(x), deja de entrar en el estado de aceptación. Mira, en realidad identificar el lenguaje L y calcular f(x) son lo mismo. Para el problema de clasificación b=sort(a), resolver este problema es equivalente a que una máquina de Turing reconozca el lenguaje: L={|y=sort(x) donde x es una matriz e y es una matriz} .

Referencias: /Documentos científicos y técnicos/Máquinas de Turing/Lenguajes reconocibles de Turing.htm