Turing Machine

Lorsque le mathématicien Alan Turing a développé sa théorie, il a imaginé une machine comprenant :

  • un ruban infini sur lequel sont inscrits des symboles,
  • une tête de lecture qui peut lire ou écrire un symbole à la fois,
  • une suite finie d’instructions qui changent le symbole courant et déplacent la tête de lecture.

À quoi sert cette machine ?

Elle décrit simplement le fonctionnement de tout ordinateur. Tout ce qui peut s’écrire comme une suite finie d’instructions, c’est-à-dire tout programme ou algorithme, peut donc être exécuté par cette machine. Avec un ensemble bien choisi d’instructions, une machine de Turing peut simuler n’importe quelle autre machine de Turing : c’est ce qu’on appelle une machine de Turing universelle.

À quoi ça ressemble ?

Une machine de Turing est d’abord une expérience de l’esprit. Néanmoins, rien n’empêche d’en construire une. C’est ce qu’a fait Mike Davey.

(Via Seweryn)

Publicités

3 Replies to “Turing Machine”

  1. « Néanmoins, rien n’empêche d’en construire une. »
    Euh, le ruban infini peut-être? 😉

    Ah non, attends, je viens d’en trouver un au fond de la poche de mon jean. J’ai rien dit.

    Puis je sors.

    J'aime

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.