En realidad no lo son.
Se pueden usar para probar ciertas cosas sobre algoritmos e idiomas, pero también hay cosas que se pueden hacer en computadoras modernas que no se pueden hacer en máquinas de Turing.
Tome esta simple declaración de JavaScript:
- Si g (x) es una función unidireccional débil, ¿es f (x) = x (exclusivo o) g (x) una función unidireccional? Si es así, ¿puede ser fuerte?
- ¿Cuántas matemáticas se requieren para la informática?
- Si el punto (3, -4) divide la línea entre el eje x y el eje y en la relación 2: 3, ¿cuál será la ecuación lineal?
- Cómo probar [matemáticas] p (a \ cup b \ cup c) \ leq p (a) + p (b) + p (c) [/ math]
- Dada una matriz que consta de solo 0s y 1s, ¿cómo puedo encontrar la submatriz más grande que contenga solo 1s?
setTimeout (() => console.log (“hi2”), 4000)
console.log (“hi1”)
Este código imprimirá “hi1” en un registro, espere cuatro segundos y luego imprima “hi2”. Esto implica una secuencia de salida y un reloj.
Puede definir una sección de la cinta para que sea una secuencia de salida, pero a menos que haga trampa y agregue un proceso externo que modifique una ubicación de cinta en tiempo real (o haga trampa y defina instrucciones y la cinta busca tomar cantidades conocidas de tiempo real) No puedes conseguir un reloj.
También en JavaScript, podría haber puesto en cola una docena de consultas web asincrónicas y hacer que devolvieran los resultados de forma asincrónica. Nuevamente, si la memoria asigna el hardware de la red a la “memoria” de la cinta, puede engañarlo. Muchas computadoras reales usan mapeo de memoria para lograr esto, por lo que solo rompe un poco la abstracción.
Pero aquí es donde las cosas realmente se rompen: código de interrupción. Una máquina de Turing no tiene una forma de interrumpir la ejecución de una tarea para manejar asincrónicamente otra. Sin embargo, todas las CPU modernas lo hacen. Esto también permite que las CPU modernas utilicen subprocesos múltiples preventivos, algo que una máquina Turing simplemente no puede hacer.
El ejercicio mental de una máquina de Turing se trata de equivalencia algorítmica. Se han demostrado muchas cosas sobre las máquinas de Turing, y cuando se demuestra que un lenguaje es Turing completo, eso prueba que el lenguaje puede lograr todo lo que una máquina de Turing puede lograr.
Pero los lenguajes modernos (y procesadores) pueden hacer más .
