Hogar » Completitud de Turing

Completitud de Turing

1936
  • Alan Turing
Computer science lab showcasing Turing completeness in programming languages.

A system of data-manipulation rules, such as a lenguaje de programación, is Turing complete if it can simulate any single-taped Turing machine. This means it is computationally universal and can be used to solve any computable problem, given enough time and memory. Most general-purpose programming languages are Turing complete, forming the theoretical foundation for their expressive power.

Turing completeness is a concept from computability theory that defines the power of a computational system. It originates from Alan Turing’s 1936 paper describing a theoretical device known as the Turing machine. This machine consists of an infinitely long tape, a head that can read, write, and move along the tape, and a set of states and transition rules. Despite its simplicity, a Turing machine can perform any computation that can be described algorithmically. A programming language or any other formal system is deemed ‘Turing complete’ if it has the capability to simulate a universal Turing machine. This implies that the language can compute anything that is computable.

The core requirements for a system to be Turing complete are conditional branching (e.g., if-then-else statements) and the ability to loop indefinitely or recursively (e.g., while, for loops). These constructs allow the system to make decisions and repeat operations, which is sufficient to model the behavior of a Turing machine’s state transitions and tape manipulation. The Church-Turing thesis, a fundamental principle in computer science, posits that any function that is naturally considered ‘computable’ can be computed by a Turing machine. Therefore, a Turing-complete language is, in theory, capable of expressing any algorithm.

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

Disrupción

Incremental

Utilización

Uso generalizado

Precursores

  • Kurt Gödel’s work on incompleteness theorems
  • Alonzo Church’s development of lambda calculus
  • David Hilbert’s program to formalize mathematics
  • 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)
  • minecraft’s redstone circuitry
  • cellular autómatas 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

Posibles ideas innovadoras

Membresía obligatoria de Professionals (100% free)

Debes ser miembro de Professionals (100% free) para acceder a este contenido.

Únete ahora

¿Ya eres miembro? Accede aquí
Related to: turing completeness, turing machine, computability theory, alan turing, church-turing thesis, universal computation, algorithm, formal language, decidability, halting problem.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

DISPONIBLE PARA NUEVOS RETOS
Ingeniero Mecánico, Gerente de Proyectos, Ingeniería de Procesos o I+D
Desarrollo eficaz de productos

Disponible para un nuevo desafío a corto plazo.
Contáctame en LinkedIn
Integración de electrónica de metal y plástico, diseño a coste, GMP, ergonomía, dispositivos y consumibles de volumen medio a alto, fabricación eficiente, industrias reguladas, CE y FDA, CAD, Solidworks, cinturón negro Lean Sigma, ISO 13485 médico

Estamos buscando un nuevo patrocinador

 

¿Su empresa o institución se dedica a la técnica, la ciencia o la investigación?
> Envíanos un mensaje <

Recibe todos los artículos nuevos
Gratuito, sin spam, correo electrónico no distribuido ni revendido.

o puedes obtener tu membresía completa -gratis- para acceder a todo el contenido restringido >aquí<

Contexto histórico

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

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

Scroll al inicio

También te puede interesar