Interro surprise

Bonjour,

- le langage Tex est Turing-complet
- le jeu de la vie de Conway est Turing-complet

J'imagine que python est Turing-complet

C'est quoi pour un langage informatique d'être Turing-complet ?
J'attends une définition minimale self-contained et c'est urgent, merci.

Réponses

  • Pouvoir simuler n'importe quelle machine de Turing, c'est à dire un ruban infini sur lequel se déplace une tête de lecture écriture. A chaque instant, en fonction de la donné écrite à la position actuelle et d'une variable d'état, la tête peut se déplacer et/ou écrire une nouvelle valeur et/ou modifier la variable d'état.

    https://fr.wikipedia.org/wiki/Machine_de_Turing
  • En termes moins précis, pouvoir faire n'importe quel calcul que peut faire n'importe quel ordinateur. Du moins en principe, sans tenir compte des contraintes de place mémoire ou de temps d'exécution. 
  • Merci pour vos réponses,

    je me permets d'ajouter qu'il faut connaître le langage qui simule la simulation de ces machines de Turing.
Connectez-vous ou Inscrivez-vous pour répondre.