Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 23-12-2019 06:52:04

Architas
Membre
Inscription : 21-12-2019
Messages : 37

Sur la Machine de Rturing.

Bonjour,

KLjZ1.jpg

On voit bien que ce "programme" ajoute 1 à un nombre n quelconque
La machine de Turing est en quelque sorte l’ancêtre logique de l’ordinateur.
C’est en effet un concept théorique qui n’a jamais été construit sauf sous la forme de simulation sur un ordinateur.
Une machine de Turing est composée d’un ruban illimité dans les deux sens et divisé en cases, d’une tête de lecture/écriture et qui ne peut à chaque étape du calcul que se déplacer d’une case à droite ou a gauche ou s’arrêter.
Chaque case peut contenir que  un bâtonnet vertical, soit un blanc. C’est tout !
Les instructions qu’on lui donne sont vraiment rudimentaires et sont composées de lignes de commandes numérotées  :
Si la tête de lecture/écriture voit un bâtonnet, soit elle le laisse, soit elle l’efface.
Même chose si elle voit un »blanc ».
Puis, elle peut se déplacer soit d’une case à droite, soit d’une case à gauche, soit s’arrêter.
Puis une indication lui donne le numéro de la ligne de commandes où elle doit exécuter la ligne de commandes suivante.


Et voici un résultat inattendu :
Il est démontré qu’il est impossible de créer un langage logiquement plus puissant que celui de cette machine !

Que les langages modernes soient plus « confortables », certes, mais ils ne sont pas logiquement plus puissants.

Cela signifie que tout logiciel écrit pour le plus puissant ordinateur existant peut être réécrit (mais à quel prix !) pour une machine de Turing.
Cordialement.

Dernière modification par Architas (24-12-2019 06:49:25)


"Plus tu t'élèves et plus te voient petits ceux qui ne savent pas voler" (Friedrich Nietzsche)

Hors ligne

Pied de page des forums