Lenguaje Turing completo - Masterhacks Blog

Lenguaje Turing completo

Cuando se trabaja con teoría de computadores, de lenguajes de programación y de otros sistemas lógicos, es común toparse con el término Turing completo, que es el que tiene un poder computacional equivalente a la máquina de Turing universal. Esto quiere decir que el sistema y la máquina universal de Turing pueden emularse entre sí.

Aunque físicamente es imposible que estas máquina existan, debido a que requieren un almacenamiento ilimitado y probabilidad de cero falla, la completitud de Turing es atribuida a máquinas físicas o lenguajes de programación que podrían ser universales si contaran con almacenamiento infinito y totalmente fiables.

La primera de esas máquinas apareció en 1941, tratándose de la Z3, de Konrad Zuse, y era controlada por programas. Su universalidad se demostró mucho tiempo después, por Raúl Rojas, en 1998.

Hablar de Turing completo es significativo, ya que cada diseño verosímil de un dispositivo de computación, por más avanzado que sea, pueden ser emuladas por una máquina universal de Turing. De este modo, una máquina que pueda actuar como una universal de Turing, puede hacer cualquier cálculo que cualquier otra computadora sea capaz de hacer.

También existe la hipótesis de que el Universo es Turing completo, más detallado en las implicaciones filosóficas en la Tesis de Church-Turing y en Física digital.

Un ejemplo de Turing completo son las expresiones regulares que tienen algunos lenguajes como Perl, otro podría ser el lenguaje de macros de Excel.

Hablando de teoría de computabilidad, existe un resultado que concluye que es imposible saber si un programa escrito en un lenguaje Turing completo se continuará ejecutando indefinidamente o se detendrá en un periodo finito de tiempo. Un método para prevenir que suceda lo primero, es hacer que los programas se detengan luego de un tiempo determinado, sin embargo, esos sistemas ya no serían Turing completos.

El cálculo lambda sin tipo es Turing completo, pero muchos cálculos lambda con tipo, incluyendo el Sistema F no lo son.

Gracias por apoyar el libre conocimiento con tu donación!
Bitcoin: bc1q4sw9260twfcxatj8mjp7358cyvrf8whzlelyhj
Ethereum: 0xFb93D2a3c9d1A0b83EE629c2dE1725BCa192e581
Litecoin: LbFduJmHvQXcpCnwfUT7aJ4DYoWSL3iQw8
Dogecoin: D7QQVqNR5rk215A4zd2gyzV9P2bLQtZHFV
Transferencia bancaria en México:
Cuenta CLABE: 646180224401848086 Nombre: Masterhacks LATAM Banco: STP

Unete a nuestros grupos:
WhatsApp: https://chat.whatsapp.com/C8fqiz3aDDc58VRRd1vdrb
Telegram: https://t.me/masterhacks_net
Canal de WhatsApp https://whatsapp.com/channel/0029VaBBLCn5vKAH9NOWCl3K