Product Design, Manufacturing & Innovation Resources
Hogar » Completitud de Turing

Completitud de Turing

1936
  • Alan Turing
Laboratorio de informática que muestra la completitud de Turing en lenguajes de programación.

(Imagen generada únicamente con fines ilustrativos)

Un sistema de reglas de manipulación de datos, como por ejemplo: lenguaje de programaciónUn lenguaje es Turing completo si puede simular cualquier máquina de Turing de una sola cinta. Esto significa que es computacionalmente universal y puede utilizarse para resolver cualquier problema computable, siempre que disponga de suficiente tiempo y memoria. La mayoría de los lenguajes de programación de propósito general son Turing completos, lo que constituye la base teórica de su gran capacidad expresiva.

La completitud de Turing es un concepto de la teoría de la computabilidad que define la potencia de un sistema computacional. Se origina en el artículo de Alan Turing de 1936, donde describía un dispositivo teórico conocido como la máquina de Turing. Esta máquina consta de una cinta infinitamente larga, un cabezal que puede leer, escribir y moverse a lo largo de la cinta, y un conjunto de estados y reglas de transición. A pesar de su simplicidad, una máquina de Turing puede realizar cualquier cálculo que pueda describirse algorítmicamente. Un lenguaje de programación o cualquier otro sistema formal se considera "Turing completo" si tiene la capacidad de simular una máquina de Turing universal. Esto implica que el lenguaje puede calcular cualquier cosa que sea computable.

Los requisitos fundamentales para que un sistema sea Turing completo son la ramificación condicional (por ejemplo, sentencias if-then-else) y la capacidad de ejecutar bucles de forma indefinida o recursiva (por ejemplo, bucles while y for). Estas estructuras permiten al sistema tomar decisiones y repetir operaciones, lo cual es suficiente para modelar el comportamiento de las transiciones de estado y la manipulación de cintas de una máquina de Turing. La tesis de Church-Turing, un principio fundamental en informática, postula que cualquier función que se considere naturalmente "computable" puede ser computada por una máquina de Turing. Por lo tanto, un lenguaje Turing completo es, en teoría, capaz de expresar cualquier algoritmo.

Sin embargo, este poder teórico conlleva una consecuencia significativa: el problema de la detención. Turing demostró la imposibilidad de crear un algoritmo general que pueda determinar, para todas las entradas posibles, si un programa dado terminará de ejecutarse o continuará indefinidamente. Esta indecidibilidad es una propiedad inherente a todos los sistemas Turing-completos. Por esta razón, algunos lenguajes específicos de dominio están diseñados intencionalmente para no ser Turing-completos. Por ejemplo, SQL y HTML estándar no son Turing-completos, lo que garantiza que sus scripts o definiciones terminarán y evita que entren en bucles infinitos accidentales, una propiedad deseable para consultas a bases de datos y la representación de documentos.

UNESCO Nomenclature: 1202
- Informática

Tipo

Sistema abstracto

Ruptura

Incremental

Uso

Uso generalizado

Precursores

  • Kurt Gödel’s work on incompleteness theorems
  • El desarrollo del cálculo lambda por Alonzo Church
  • El programa de David Hilbert para formalizar las matemáticas
  • El concepto de algoritmo se remonta a la antigüedad

Aplicaciones

  • lenguajes de programación de propósito general (Python, C++, Java)
  • Sistemas de hojas de cálculo con capacidades de macros (por ejemplo, Excel con VBA)
  • Circuitos de redstone de Minecraft
  • cellular automata like conway’s game of life
  • Algunas extensiones SQL avanzadas con expresiones de tabla comunes recursivas
  • El subsistema de metaprogramación de plantillas de C++
  • CSS3 con ciertas combinaciones de HTML

Patentes:

NA

Ideas para posibles innovaciones

Debido al bloqueo del tráfico generado por bots, que actualmente supera los 40.000 al día, este contenido está reservado para los miembros de la comunidad.
> Iniciar sesión < o > Registrarse < (100% gratis) para acceder a esto, al igual que a todo el demás contenido y herramientas restringidos.

Relacionado con: completitud de Turing, máquina de Turing, teoría de la computabilidad, Alan Turing, tesis de Church-Turing, computación universal, algoritmo, lenguaje formal, decidibilidad, problema de la parada.

Contexto histórico

Completitud de Turing

1925
1928
1930
1936
1940
1943
1950
1924
1925
1930
1931
1939
1940
1950
1950

(Si la fecha es desconocida o no es relevante, por ejemplo "mecánica de fluidos", se proporciona una estimación redondeada de su aparición notable)

Invención, innovación y principios técnicos relacionados.

Las imágenes a tamaño completo y las descargas sólo están disponibles, 100% gratis, para los miembros registrados.

> Acceso <