¿Se ha completado Javascript Turing?

Sí, creo que JavaScript está completo, según las definiciones más razonables.

(Técnicamente hablando, ninguna implementación real de JavaScript (o de cualquier lenguaje) en hardware real puede ser Turing Complete, porque no tiene memoria infinita. Pero aún podemos discutir si JavaScript, en resumen, es Turing Complete).

De todos modos, JavaScript es un lenguaje imperativo bastante sencillo, puede simular la clásica máquina de Turing de cinta, SKI y brainfuck en JavaScript.

setTimeout no tiene nada que ver con eso. setTimeout realmente no tiene sentido en el contexto de Turing-Completeness, pero puedes ignorarlo. Para que Turing Complete, JavaScript debe ser capaz de simular una máquina de Turing, no al revés.

Para ser realmente pedante al respecto, en el mejor de los casos, se podría decir que la existencia de funciones de efectos secundarios como setTimeout hace que la cuestión de la integridad de Turing en JavaScript no sea una pregunta bien definida. Por supuesto, según la misma lógica, casi ningún lenguaje de programación del mundo real es Turing Complete, que realmente solo sus definiciones no le permiten establecer distinciones significativas entre los lenguajes de programación en el espíritu de Turing Completeness. Y si encuentra una forma razonable de definir bien la pregunta, la respuesta será “sí” para JavaScript.

Para responder a su pregunta: sí, JavaScript está Turing completo.

Ahora para agregar algunos detalles: hay otra respuesta detallada que afirma lo contrario, sin embargo, esa respuesta contiene argumentos defectuosos. No voy a volver a visitar todos los defectos, pero el problema comienza con una mala interpretación del documento de Turing, On Computable Numbers (el documento se puede encontrar aquí: https://www.cs.virginia.edu/~rob …).

La otra respuesta afirma que la definición de Turing en el documento es diferente de las “interpretaciones de segunda y tercera mano”. Dice específicamente:

Turing dice que “la máquina nunca escribe más que un número finito de símbolos”, validando esta afirmación con ejemplos, como una salida de cinta después de cada configuración m, que calcula 010110111 …

Esto reduce a las afirmaciones del mito de que se necesita una cinta infinita para calcular un número; se necesita una cinta infinita solo cuando tiene un número inconfundible.

Eso muestra un profundo malentendido de lo que significa computable y no computable. El autor implica aquí que los números no computables son todos los números que requieren que se produzca una máquina con cinta infinita, y los números computables son aquellos números que requieren solo cinta finita.

Según esta definición defectuosa, [math] \ pi [/ math] sería un número no computable, porque, como todos sabemos, tiene infinitos dígitos en su expansión decimal. Pero esto no es lo que Turing quiere decir con no computabilidad. Incluso menciona explícitamente [math] \ pi [/ math] como un ejemplo de un número computable en la primera página.

Y es computable, hay algoritmos para calcular dígitos de [math] \ pi [/ math], y se han calculado billones de dígitos de [math] \ pi [/ math]. Cuando construimos computadoras más rápidas con más memoria, podremos calcular más y más dígitos. Por supuesto, en un tiempo finito determinado solo podemos obtener una parte finita de toda la salida, pero podemos obtener, en principio, una parte arbitrariamente grande de la salida, lo que se traduce en obtener el número con una precisión arbitrariamente alta. Nunca obtenemos la salida completa, porque esa es la naturaleza del infinito: no hay un último dígito de [math] \ pi [/ math].

Turing define los números no computables como aquellos números que no pueden ser producidos por ninguna máquina descrita en el documento. (Tal máquina se llama máquina de Turing hoy, aunque, obviamente, Turing no usó este nombre cuando lo describió por primera vez).

Entonces, ¿cómo son los números no computables? Aquí se pueden encontrar algunos ejemplos: ¿Hay ejemplos de números reales no computables? Los números en estos ejemplos se construyen utilizando el problema de detención de varias maneras, lo que los hace no computables. Eso no es sorprendente, ya que el problema de detención es el problema indecidible más conocido, precisamente el tipo de problemas que ninguna máquina de Turing no puede resolver.

También estoy disputando esto:

Turing nunca consideró el caso de procesos infinitos, sino solo de procesos computables, que deben ser finitos (“sin círculo”, en palabras de Turing) para tener éxito.

La lectura cuidadosa del artículo de Turing revela que esto está equivocado en dos aspectos. No voy a citar a Turing por completo: puede leer el documento original usted mismo, las definiciones son fáciles de entender, pero me concentraré en las cosas relevantes.

Turing define máquinas que producen series infinitas de dígitos binarios: ceros y unos (también producen símbolos de diferente tipo, pero eso no es importante). Lo importante es que Turing nunca dice que estas máquinas deben terminar. Corren indefinidamente. Entonces, contrario a lo que dice la respuesta defectuosa, el artículo original de Turing trata exclusivamente de procesos infinitos. No le interesan los procesos finitos en absoluto.

Luego, Turing clasifica las máquinas en dos categorías distintas: circulares y sin círculo . La máquina circular es una máquina que nunca escribe más de un número finito de dígitos. Después de escribir el último dígito que produce, ingresa una especie de bucle que hace que deje de producir más dígitos binarios. De aquí proviene el término “circular”. Además, las máquinas circulares no son interesantes para el punto que Turing está haciendo, y no las analiza más a fondo.

La otra categoría de máquinas sin círculo funciona de manera diferente: estas máquinas producen un número infinito de dígitos binarios. No tienen círculos porque, a diferencia de los circulares, siempre producen un siguiente dígito, nunca entran en un bucle infinito que les impediría producir otro. Puede llevar mucho tiempo, pero si esperamos lo suficiente (y tenemos una cinta lo suficientemente larga), aparecerá el siguiente dígito. Entonces, de nuevo, el artículo dice exactamente lo contrario: las máquinas sin círculo no solo funcionan indefinidamente, sino que también producen una salida infinita.

Luego, Turing postula que los números computables son aquellos números que pueden ser producidos por máquinas sin círculo. Específicamente, si tomamos la salida de la máquina y colocamos un punto decimal al frente, obtenemos una representación binaria de un número entre 0 y 1, y este número es computable. (Todos los números computables se pueden obtener al sumar un número entero a un número obtenido de la máquina). Todos los demás números (y hay infinitos, incluso muchos) son no computables. Luego, Turing demuestra algunas de sus afirmaciones, y esa es la parte en la que el trabajo se vuelve realmente difícil.

(Nota: originalmente publiqué un texto similar como un comentario debajo de la respuesta que estoy discutiendo aquí, donde pertenecería naturalmente, pero ahora se ha ido y no puedo agregar ningún comentario nuevo en ese hilo).

Editar: he eliminado el nombre del autor de la respuesta que disputo. No es relevante para los puntos que quiero hacer.

Nota: Soy la “persona realmente confiable” mencionada en los detalles de la pregunta, por lo que la responsabilidad recae en mí para justificar mi insistencia en que JavaScript no está completo en Turing.

La definición popular e informal de “integridad de Turing” no se alinea con las observaciones de Alan Turing en “On Computable Numbers”. Pero, hasta ahora, cada respuesta solo ha abordado por qué JavaScript es Turing completo bajo la definición informal.

Comencemos con las definiciones de Turing, no las proporcionadas en interpretaciones de segunda y tercera mano, pero primero, primero debemos definir qué es una máquina de Turing.

En “En números computables, con aplicaciones al problema Entscheidungsproblem”, 1936 (en adelante denominado OCN), Turing define una cinta de TM, declarando que es finita en cualquier momento dado.

Turing dice que “la máquina nunca escribe más que un número finito de símbolos”, validando esta afirmación con ejemplos, como una salida de cinta después de cada configuración m, que calcula 010110111 …

Esto reduce a las afirmaciones del mito de que se necesita una cinta infinita para calcular un número; se necesita una cinta infinita solo cuando tiene un número inconfundible.

Sin embargo, la definición es recursiva, lo que significa que un lenguaje completo de Turing debe ser capaz de manejar todas las formas de recursión sin desbordamientos de pila teóricos.

A través de la reorganización, es posible que toda recursión sea recursiva de cola. Para el lenguaje específico, solo necesitamos determinar si la recursión de cola es una opción para un número arbitrario de recursiones. JavaScript no admite la optimización de recursión de cola, por lo que sin una pila infinita, esta alternativa no está disponible.

Entonces, ¿la traducción de idiomas requiere una TM? La respuesta es no. Todas las gramáticas sin contexto, es decir, los lenguajes de programación, pueden analizarse y traducirse a otro lenguaje sin contexto con solo un autómata push-down (PDA), también conocido como “máquinas de pila”.

Debido al teorema de k-stack, que confirma que un PDA con k stack es igual a un TM con k-1 cintas, un PDA no es una máquina de Turing. Una prueba informal muestra lo que sucede cuando hacemos dos POP seguidos de un PDA apilado 1: no tenemos lugar para almacenar el resultado del primer POP mientras trabajamos en los resultados del segundo POP.

Esto es equivalente a dos movimientos a la izquierda en la cinta de una máquina de Turing, lo que es teóricamente posible. Para lograr esto sin perder datos en la “memoria”, necesitamos EMPUJAR el primer POP en una segunda pila.

Para igualar una cinta, necesitamos al menos 2 pilas, pero es bien sabido que las cintas adicionales no compran nada. No son diferentes al bus de direcciones en una máquina von Neumann.

Esto significa que un PDA por sí solo no puede igualar una TM con una unidad de cinta que funcione completamente; es equivalente a una máquina Turing rota que siempre borra la parte de la cinta que está más de una posición a su derecha. Entonces, aunque una respuesta afirma que la capacidad de JavaScript para compilar Java lo hace completo para Turing, la completa integridad de Turing es imposible con JavaScript.

En cuanto a su otra evidencia de la integridad de Turing, cada ejemplo (simulador de TM) que mencionó tiene un error crítico que no es reparable en JavaScript debido a las definiciones en OCN.

Veamos los requisitos específicos y cómo falla cada uno. Turing especifica que la cinta, en teoría, comienza vacía. Sin embargo, en el ejemplo, ¡Una máquina de turing en 79! bytes de javascript falla en cualquier cinta vacía (ver más abajo).

/usr/home/mneal/foo.js:9

con (/ * q = * / a [d] [b [e | = 0] || “B”]) {// empuja la declaración del programa actual, también conocida como “q”, al principio del alcance actual

^
TypeError: undefined no tiene propiedades
en tm (/usr/home/aryeh/foo.js:9:24)
en Objeto. (/usr/home/aryeh/foo.js:33:25)
en Module._compile (module.js: 434: 26)
en Object.Module._extensions..js (module.js: 452: 10)
en Module.load (module.js: 355: 32)
en Function.Module._load (module.js: 310: 12)
en Function.Module.runMain (module.js: 475: 10)
al inicio (node.js: 118: 18)
en node.js: 952: 3

El ejemplo en JavaScript Turing Machines está codificado, por lo que si cambia los datos de la cinta, no se obtienen resultados diferentes. Esto no es una simulación. Los otros ejemplos que Tim enumera solo se vinculan a uno de los ejemplos anteriores, aunque los ejemplos en los detalles de la pregunta tienen problemas similares.

Uno de los requisitos finales de Turing establece que la máquina debe HALTAR. En sí mismos, setTimeout y setInterval no son problemas, excepto por el hecho de que pueden usarse para dar vida al código en puntos arbitrarios. Vea las largas discusiones en hilos de comentarios sobre otras respuestas para obtener detalles específicos.

Lo anterior, junto con la falta de una instrucción HALT específica, como la salida de C (), hace imposible una HALT completa arbitraria, lo que hace imposible una decisión final sobre el problema de detención incluso para algoritmos cuya capacidad de parada sería de otro modo decidible.

Turing nunca consideró el caso de procesos infinitos, sino solo de procesos computables, que deben ser finitos (“sin círculo”, en palabras de Turing) para tener éxito.

Entonces, la cuestión de la integridad de Turing se limita a los algoritmos definidos por Knuth y CLRS. Por lo tanto, los procesos infinitos están más allá del alcance de la pregunta de si un lenguaje es Turing completo.

En un proceso infinito como un bucle de controlador, la cuestión de la integridad de Turing solo se puede responder en términos de iteraciones individuales del bucle de controlador, no del bucle en su conjunto. Sin embargo, debido a cómo funcionan setTimeout y setInterval, en JavaScript, la separación limpia entre iteraciones es imposible.

El OP de la pregunta original confundió mis comentarios sobre ese tema. No quise indicar que setTimeout y setInterval, en sí mismos, son las razones subyacentes por las cuales JavaScript no está completo en Turing.

Más bien, el problema está en los detalles de cómo funcionan setTimeout y setInterval en JavaScript, específicamente que es imposible hacer una separación limpia entre las iteraciones del bucle infinito de nivel superior incorporado del intérprete de JavaScript.

Javascript está Turing completo, al igual que casi todos los lenguajes de programación que la mayoría de la gente ha escuchado. El problema con Quora (y por qué me fui, a excepción de la publicación anónima ocasionalmente), es que las personas que son realmente ignorantes sobre un tema (y no hay ofensa intencionada en eso, ni deberían ser tomadas) pueden jugar el sistema para ser percibido como “realmente de buena reputación”.

Un lenguaje está completo en Turing si cualquier función que pueda ser calculada por una máquina de Turing también puede ser calculada por un algoritmo expresable en ese idioma. Esto es cierto para Javascript, y si uno quisiera afirmar lo contrario, simplemente podría describir la función matemática que una máquina de Turing puede calcular, pero que no puede ser calculada por un algoritmo expresable en Javascript.

setTimeout es un arenque rojo. Uno no necesita usarlo. Su presencia en el lenguaje es completamente irrelevante para la pregunta.

Javascript está completo en Turing.

No estoy seguro de a qué se refiere la persona a la que se refiere al decir que setTimeout hace que Javascript no sea Turing completo, pero simplemente agregar funcionalidad a un lenguaje Turing completo no puede hacer que deje de ser Turing completo.

Un lenguaje es completo de Turing si puede calcular cualquier cosa que pueda hacer una máquina de Turing. Si Javascript menos setTimeout es Turing-complete, entonces Javascript con setTimeout incluido también es Turing-complete, porque simplemente podría decidir no usar setTimeout.

Javascript es definitivamente Turing completo. Si desea una prueba breve, simplemente ignore las máquinas de Turing y muestre cómo implementar funciones recursivas [math] \ mu [/ math] usando Javascript.