JavaScript es Turing completo: explicación

JavaScript es Turing completo: explicación

Si comienza a aprender programación funcional en JavaScript, probablemente escuche acerca del cálculo lambda, la máquina de Turing, Turing completo y de alguna manera “JavaScript es Turing completo”.

Pero nadie parece explicar, en términos simples, lo que realmente significa. ¿Cuál es la relación entre la “máquina” de Turing y el “lenguaje” JavaScript? Además, la mayoría de la gente usa jerga para explicar la jerga así:

En la teoría de la computabilidad, se dice que un sistema de reglas de manipulación de datos (como el conjunto de instrucciones de una computadora, un lenguaje de programación o un autómata celular) es Turing completo o computacionalmente universal si se puede usar para simular cualquier máquina de Turing de una sola cinta. . El concepto lleva el nombre del matemático inglés Alan Turing. Un ejemplo clásico es el cálculo lambda.

Así que este es mi intento de explicar estos conceptos de forma sencilla.

Máquinas de Turing

En el pasado, la gente quería saber cómo crear una máquina que pudiera hacer todos los cálculos que estaban haciendo a mano. Querían saber cómo construir una máquina así y cómo podría funcionar.

Alan Turing ideó una máquina hipotética que podría tomar cualquier programa de cualquier complejidad y ejecutarlo. Podría implementarse usando una cinta simple, un cabezal que se mueve hacia la izquierda y hacia la derecha, podría almacenar datos leyendo, escribiendo y borrando el contenido de celdas cuadradas. Con suficiente cinta y tiempo, podría calcular cualquier programa.

En otras palabras, explicó cómo alguien puede construir una computadora. Y llamó a la computadora una "máquina de Turing"

Trivia: En los días de Alan Turing, la palabra "Computadora" significaba la persona que computa manualmente los programas (no las máquinas) :)

Tan poderoso pero tan simple

Las máquinas de Turing pronto se hicieron muy populares y, finalmente, se convirtieron en un estándar porque, si bien proporcionaban un mecanismo poderoso para calcular cualquier cosa, también eran fáciles de entender. Como se describe en el video a continuación, las máquinas de Turing usan una cinta para realizar un seguimiento de los estados y ejecutar cálculos.

Máquinas de Turing de cinta “simple” Vs “múltiple”

Otra jerga que escuchará acerca de las máquinas de Turing es el concepto de cinta "única".

La versión inicial de la máquina de Turing tenía una sola cinta larga. Más tarde, a la gente se le ocurrió el concepto de máquinas de Turing de cinta “múltiples” que usaban de dos a cinco cintas. Las máquinas de Turing de varias cintas no eran más potentes que las de una sola cinta, pero ayudaron a simplificar los programas.

Por lo tanto, no es necesario decir explícitamente una cinta "única".

Turing completo

Si una máquina física (como una computadora) o una máquina virtual, que es un software (como JavaVM) puede tomar cualquier programa y ejecutarlo como una máquina de Turing, entonces esa máquina se llama “Turing Complete”. PD: Es una especie de certificación.

Ejemplos: máquina Turing completa Vs Turing incompleta

Una calculadora es un buen ejemplo de una máquina incompleta de Turing porque solo puede realizar un pequeño subconjunto predefinido de cálculos.

Sin embargo, una computadora doméstica (Mac o PC) es una máquina completa de Turing porque puede hacer cualquier cálculo que una máquina de Turing pueda hacer si le damos suficiente memoria y tiempo.

"JavaScript es Turing completo"

Si lo piensa bien, una máquina de Turing es solo un concepto; significa que cualquier " cosa " (física o virtual) que toma cualquier programa y lo ejecuta es esencialmente una máquina de Turing. Y si esa "cosa" puede ejecutar todos los programas que una "Máquina de Turing" puede ejecutar, entonces se llama "Turing Completo".

Ahora bien, si piensa en cualquier lenguaje de programación moderno, también toman programas (escritos por nosotros) como entrada y los ejecutan. Además, cualquier programa que se pueda escribir teóricamente para ejecutarse en una máquina de Turing también se puede escribir en JavaScript. Por lo tanto, JavaScript es Turing completo.

¡Eso es!

??? Si le gusta esta publicación, 1. ❤❤❤ a continuación en Medium y 2. por favor compártala en Twitter. ¿Puede retuitear la siguiente tarjeta ???

Mis otras publicaciones

ÚLTIMO: Programación funcional en JS - Con ejemplos prácticos (Parte 1)

Programación funcional

  1. JavaScript es Turing completo: explicación
  2. Programación funcional en JS: con ejemplos prácticos (Parte 1)

ES6

  1. 5 partes "malas" de JavaScript que se corrigen en ES6
  2. ¿Es la "clase" en ES6 la nueva parte "mala"?

WebPack

  1. Webpack: las partes confusas
  2. Reemplazo de Webpack y Hot Module [HMR] (bajo el capó)
  3. HMR y React-Hot-Loader de Webpack: el manual que falta

Draft.js

  1. Por qué Draft.js y por qué debería contribuir
  2. Cómo Draft.js representa datos de texto enriquecido

Reaccionar y Redux:

  1. Guía paso a paso para crear aplicaciones React Redux
  2. Una guía para crear una aplicación CRUD de React Redux ( aplicación de 3 páginas)
  3. Uso de Middlewares en aplicaciones React Redux
  4. Adición de una validación de formulario sólida para reaccionar aplicaciones Redux
  5. Protección de aplicaciones React Redux con tokens JWT
  6. Manejo de correos electrónicos transaccionales en aplicaciones React Redux
  7. La anatomía de una aplicación React Redux

Fuerza de ventas

  1. Desarrollo de aplicaciones React Redux en Visualforce de Salesforce

¡Gracias por leer!