Maison » Complétude de Turing

Complétude de Turing

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

A system of data-manipulation rules, such as a langage de programmation, 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.

Cependant, cette puissance théorique a une conséquence importante : le problème de l'arrêt. Turing a démontré l'impossibilité de créer un algorithme général capable de déterminer, pour toutes les entrées possibles, si un programme donné s'arrêtera ou se poursuivra indéfiniment. Cette indécidabilité est une propriété inhérente à tous les systèmes Turing-complets. C'est pourquoi certains langages spécifiques à un domaine sont intentionnellement conçus pour être non Turing-complets. Par exemple, SQL et HTML standard ne sont pas Turing-complets, ce qui garantit la fin de l'exécution de leurs scripts ou définitions et les empêche d'entrer accidentellement dans des boucles infinies, une propriété souhaitable pour les requêtes de bases de données et le rendu de documents.

UNESCO Nomenclature: 1202
- Informatique

Taper

Système abstrait

Perturbation

Incrémentale

Usage

Utilisation généralisée

Précurseurs

  • Kurt Gödel’s work on incompleteness theorems
  • Alonzo Church’s development of lambda calculus
  • David Hilbert’s program to formalize mathematics
  • Le concept d'algorithme remonte à l'Antiquité

Applications

  • langages de programmation à usage général (python, c++, java)
  • systèmes de tableurs avec capacités macro (par exemple, Excel avec vba)
  • minecraft’s redstone circuitry
  • cellular automates like conway’s game of life
  • quelques extensions SQL avancées avec des expressions de table communes récursives
  • le sous-système de métaprogrammation de modèles C++
  • css3 avec certaines combinaisons html

Brevets:

NA

Idées d'innovations potentielles

!niveaux !!! Adhésion obligatoire

Vous devez être membre de l'association pour accéder à ce contenu.

S’inscrire maintenant

Vous êtes déjà membre ? Connectez-vous ici
Related to: turing completeness, turing machine, computability theory, alan turing, church-turing thesis, universal computation, algorithm, formal language, decidability, halting problem.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

DISPONIBLE POUR DE NOUVEAUX DÉFIS
Ingénieur mécanique, chef de projet, ingénierie des procédés ou R&D
Développement de produits efficace

Disponible pour un nouveau défi dans un court délai.
Contactez-moi sur LinkedIn
Intégration électronique métal-plastique, Conception à coût réduit, BPF, Ergonomie, Appareils et consommables de volume moyen à élevé, Production allégée, Secteurs réglementés, CE et FDA, CAO, Solidworks, Lean Sigma Black Belt, ISO 13485 médical

Nous recherchons un nouveau sponsor

 

Votre entreprise ou institution est dans le domaine de la technique, de la science ou de la recherche ?
> envoyez-nous un message <

Recevez tous les nouveaux articles
Gratuit, pas de spam, email non distribué ni revendu

ou vous pouvez obtenir votre adhésion complète - gratuitement - pour accéder à tout le contenu restreint >ici<

Contexte historique

(si la date est inconnue ou non pertinente, par exemple « mécanique des fluides », une estimation arrondie de son émergence notable est fournie)

Inventions, innovations et principes techniques connexes

Retour en haut

Vous aimerez peut-être aussi