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 commentaires

  1. AsTeR · avril 10, 2010

    Hey, mais c’est trop la classe comme truc, un peu geek, mais super sympa. Merci pour cet article sur le génie Turing !

    J'aime

  2. François · avril 16, 2010

    « 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

    • Franc belge · avril 16, 2010

      Ha ha ha 😀 Le ruban est théoriquement infini mais la machine peut très bien s’arrêter en temps fini, hein. :-p

      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 )

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 )

Photo Google+

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

Connexion à %s