Demandez le programme !

Quelques repères historiques de la calculabilité

  • Wilhelm Schickard (1592 – 1635) , professeur à l’Université de Tübingen (Allemagne), aurait dessiné les plans de la première machine à calculer (mécanique). Cette machine n'a pas été construite.
  • Blaise Pascal (1623 – 1662) , mathématicien et philosophe, construit à l’age de 19 ans la Pascaline, première machine à calculer opérationnelle du XVIIè siècle .
  • Gottfried Wilhelm Leibniz (1646 – 1716), mathématicien et philosophe, développe aussi une machine à calculer. Il préconise des idées très modernes : la machine de calcul universelle, le schéma “entrée-calcul-sortie”, la base 2 pour la représentation des nombres.
  • Le métier à tisser de Joseph Marie Jacquard (1752 – 1834) est basé sur l’utilisation de cartes perforées, et est à l’origine des premiers programmes de calcul.
  • Charles Babbage (1791 – 1871), professeur à Cambridge, construit la machine différentielle et imagine les plans de la machine analytique (machine programmable). La dernière peut être considérée comme précurseur des ordinateurs modernes, consistant d’une unité de contrôle, une unité de calcul, une mémoire, ainsi que l’entrée-sortie.
  • Ada Lovelace (1815 - 1852) , est une pionnière de la science informatique. Elle est principalement connue pour avoir réalisé le premier véritable programme informatique, lors de son travail sur un ancêtre de l'ordinateur : la machine analytique de Charles Babbage. Dans ses notes, on trouve en effet le premier programme publié, destiné à être exécuté par une machine, ce qui fait considérer Ada Lovelace comme le premier programmeur du monde. Elle a également entrevu et décrit certaines possibilités offertes par les calculateurs universels, allant bien au-delà du calcul numérique et de ce qu'imaginaient Babbage et ses contemporains. Elle est assez connue dans les pays anglo-saxons et en Allemagne, notamment dans les milieux féministes ; elle est moins connue en France, mais de nombreux développeurs connaissent le langage Ada, nommé en son honneur.
  • David Hilbert (1862 – 1943) , mathématicien allemand. En 1900, Hilbert propose 23 problèmes dont certains ne sont pas résolus à ce jour. Pour voir la liste des problèmes. Il présente en 1920 un programme de recherche visant à clarifier les fondements des mathématiques : “tout énoncé mathématique peut être soit prouvé ou réfuté”. Plus tard il énonce le “Entscheidungsproblem” : montrer de façon “mécanique” si un énoncé mathématique est vrai ou faux. Il faudra attendre 1936 pour qu' Alan Turing s'intéresse au problème n°10 avec Church (dont il était le doctorant). Ils définissent rigoureusement la notion d'algorithme.
  • Kurt Gödel (1906 – 1978) , un des logiciens les plus fameux de l’histoire, répond 1931 négativement quand au programme proposé par Hilbert, en montrant que tout système formel suffisamment puissant est soit incomplet ou incohérent. Il montre ceci en construisant une formule qui exprime le fait qu’elle n’est pas démontrable.
  • Alan Turing (1912 – 1954) et Alonzo Church (1903 – 1995) montrent indépendamment, en 1936, l’indécidabilité de l’Entscheidungsproblem. Turing propose "la machine de Turing" comme modèle mathématique de calcul, et Church le lambda calcul. Ils énoncent le principe selon lequel tout ce qui est calculable peut être calculé sur un de ces deux modèles (“thèse de Church-Turing”). La Machine de Turing est inventée pour répondre au problème mathématiques de la décidabilité proposé par Hilbert. Une machine de Turing a pour but de décrire les algorithmes. Il faut savoir que Turing ne verra pas de son vivant une réalisation concrète de sa "machine".
  • Quelques vidéos pour votre culture :

    Alan Turing (1912-1954), sa vie en quelques minutes.

    Vous pouvez également visionner le film "imitation game". Synopsis officiel du film : "En 1939, alors que la guerre débute, Turing, déjà reconnu pour ses talents de mathématicien, se rend à Bletchley Park et rejoint l'équipe de cryptographie, sous les ordres du commandant Alastair Denniston. Il est accompagné par le maître d'échecs Hugh Alexander, John Cairncross, Peter Hilton, Keith Furman et Charles Richards. Cette équipe va alors tenter de décrypter la machine de cryptographie utilisée par les nazis : Enigma."

    Ce travail secret ne sera connu du public que dans les années 1970. Après la guerre, il travaille sur un des tout premiers ordinateurs, puis contribue au débat sur la possibilité de l'intelligence artificielle, en proposant le test de Turing. Vers la fin de sa vie, il s'intéresse à des modèles de morphogenèse du vivant conduisant aux « structures de Turing ». Poursuivi en justice en 1952 pour homosexualité, il choisit, pour éviter la prison, la castration chimique par prise d'œstrogènes. Il est retrouvé mort par empoisonnement au cyanure le 8 juin 1954 dans la chambre de sa maison à Wilmslow (une pomme croquée posée sur sa table de nuit). La reine Élisabeth II le reconnaît comme héros de guerre et le gracie à titre posthume en 2013.

    La pomme croquée d'une célèbre marque est un hommage à ce brillant mathématicien.

    Pour les curieux : le coin des machines à calculer mécaniques.

    Quelques vidéos :

  • Une de mes machines (années 60 environ):
  • Une de mes machines (années 30 environ) :
  • Une vidéo qui explique toutes les techniques :
  • La machine de Turing

    Attention cette section 2 sur la machine de Turing hautement culturelle n'est pas un attendu du programme de terminale NSI. Elle peut néanmoins servir de support à un projet.

    En 2012 Alan Turing aurait fêté son 100 ième anniversaire. A cette occasion, des universitaires ont construit une machine de Turing en LEGO.

    Accès au site

    Une machine de Turing est un appareil théorique disposant :

    • d'une bande infiniment longue ;
    • une tête qui peut lire et écrire sur cette bande ;
    • un registre de mémoire (fini) ;
    • un "processeur" capable de réaliser les opérations suivantes :
      • déplacer la bande vers la droite / la gauche ;
      • modifier l'état du registre selon sa valeur actuelle et la valeur sur la bande ;
      • écrire ou effacer une valeur sur la bande.

    le fonctionnement de la machine atteint (ou pas) un état particulier qui provoque son arrêt. Cet état particulier est souvent appelé état final.

    texte de remplacement

    Pour représenter l'ensemble des états, on peut utiliser une table des transitions.

    Elle permet de définir, pour chaque état, selon le résultat de la lecture, les actions à exécuter : écriture, déplacement, choix d'un nouvel état.

      Pour écrire cette table, il faut :
    • définir un alphabet utilisé par la machine : liste des caractères utilisés ;
    • noter les états sous la forme e0, e1, e2, etc (ou q0, q1, q2, etc) ;
    • représenter l'état final par qf (ou ef) mais parfois indiqué par une chaine de caractères ou un caractère particulier ("final" ou □).

    Dans certains exercices, on déplace le ruban mais pas la tête de lecture/écriture.

    Alphabet : {'0','1','b'}

    Etat Lit Ecrit Déplace Suivant
    e0 blanc rien droite e0

    A l'état e0 si la tête lit un blanc, elle n'écrit rien, se déplace à droite et reste à l'état e0

    Cette table des transitions donnait naissance à une carte percée de trous que l'on pouvait insérer dans la machine. A l'aide d'aiguilles et de relais électro-mécaniques, ces informations provoquaient des actions dans la machine. Ces cartes étaient les programmes de la machine. Par contre Alan Turing ne verra pas sa "machine" fonctionner.

    On peut construire un diagramme de la machine (on parle aussi d'automate).

      Pour définir un diagramme, il faut :
    • un alphabet utilisé par la machine : liste des caractères utilisés. Exemple {'0','1','b'}.
    • des états sont symbolisés par des cercles et écrits sous la forme q1, q2, etc (ou e1, e2, etc).
    • un état final représenté par ef (ou qf) mais parfois indiqué par une chaine de caractères ou un caractère particulier ("final" ou □).
    • représenter les déplacements par les lettres L et R (left et right).
    • utiliser des triplets (lecture; écriture; déplacement) et des flèches qui indiquent l'état suivant.

    Alphabet : {'0';'1;'b'}

    texte de remplacement A l'état e0, si la tête lit un blanc alors elle n'écrit rien et se déplace à droite en restant à l'état e0.

    Alphabet : {'0';'1;'b'}

    texte de remplacement
    • A l'état e1, si la tête lit un 0 alors elle écrit 1, se déplace à droite et reste à l'état e1.
    • A l'état e1, si la tête lit un 1 alors elle écrit 0, se déplace à droite et reste à l'état e1.
    • A l'état e1, si la tête lit un blanc alors elle n'écrit rien et passe à l'état ef (elle s'arrête).

    Alphabet : {'0';'1;'b'}

    texte de remplacement
      A l'état e0,
    • si la tête lit un blanc alors elle n'écrit rien et se déplace à droite en restant à l'état e0.
    • A l'état e0, si la tête lit un 0 alors elle n'écrit rien, ne se déplace pas et passe à l'état e1.
    • A l'état e0, si la tête lit un 1 alors elle n'écrit rien, ne se déplace pas et passe à l'état e1.
    • A l'état e1, si la tête lit un 0 alors elle écrit 1, se déplace à droite et reste à l'état e1.
    • A l'état e1, si la tête lit un 1 alors elle écrit 0, se déplace à droite et reste à l'état e1.

    Dans cet exemple, on écrit une machine de Turing qui remplace les 0 par des 1 et les 1 par des 0.

    Analyse du problème et liste des états à écrire.

  • Un état e0 qui lit des caractères "blancs" et qui avance de gauche à droite.
  • Un état e1 qui lit, remplace les 0 par des 1 (et réciproquement) et qui avance de gauche à droite.
  • Si l'état e1 lit un blanc, on passe à l'état final ef
  • un état final ef qui arrête la machine.
  • Cela peut donner le diagramme suivant : texte de remplacement

    Réalisons la table des transitions de l'exemple précédent.

    Etat Lit Ecrit Déplace Suivant
    e0 blanc rien droite e0
    0 rien rien e1
    1 rien rien e1
    e1 0 1 droite e1
    1 0 droite e1
    b rien rien ef
    ef Arrêt de la machine

    D'un point de vue machine, cela donnerait les représentations suivantes :

    Etat initial : texte de remplacement Etat final : texte de remplacement

    Ecrire une machine de Turing qui remplace les 1 par des 0 et qui laisse les 0. Cette machine doit transformer le nombre 01010001 par 00000000.

    D'un point de vue machine, cela donnerait les représentations suivantes :

    Etat initial : texte de remplacement Etat final : texte de remplacement

    Vous écrirez le diagramme d'états ainsi que la table des transitions.

    Que produit la machine de Turing décrite par le diagramme suivant en partant d'un ruban vide? texte de remplacement

    Un simulateur de machine de Turing (attention c'est le ruban qui se déplace ):

    Source : INRIA-interstices-machine de Turing

    Explications sur le simulateur

    Un autre simulateur du site de M. PECHAUD (professeur en classe préparatoire)

    Quelques liens et ressources :

  • Site dans lequel on peut trouver des diagrammes.
  • Article et explications sur le fonctionnement de la machine de Turing
  • La notion de programme en tant que donnée

    Il est important de comprendre qu'un programme utilise des données sur lesquelles il travaille. Ces données peuvent être également des programmes.

    Voici des exemples dans lesquels un programme est une donnée d'un autre programme

  • Le compilateur Python (ou les autres langages) est un programme (Edupython, Jupyter, idle de python, etc) qui utilise votre programme comme une donnée.
  • Windows est un programme qui utilise d'autres programmes (applications).
  • Tous les systèmes d'exploitation (windows, linux, unix, macos, androïd) utilise des programmes comme données.
  • Un débuggeur.
  • Le téléchargement de logiciels.
  • Calculabilité et décidabilité

    Calculabilité

    Une fonction calculable est une fonction que l'on peut écrire sous forme d'algorithme.

    Quelques remarques :

  • Les machines de Turing sont une réponse à la recherche de définition d'une fonction calculable.
  • Toute fonction calculable est calculable grâce à une machine de Turing. C'est la thèse de Church : "Toute fonction physiquement calculable est calculable par une machine de Turing".
  • Les fonctions calculables par d'autres modèles de calculs suffisamment riches (machines à registres, machine RAM, lambda calcul...) sont les mêmes que les fonctions calculables par des machines de Turing.
  • Il existe même une machine de Turing universelle qui simule toutes les autres machines de Turing. Les machines de Turing sont en fait des modèles universels de calcul.
  • Fonctions non-calculables : contrairement à ce que l'on pourrait imaginer, il existe des fonctions qui ne sont pas calculables (fonctions des castors affairés). Il y en a même une infinité.
  • La calculabilité ne dépend pas du langage utilisé.

    Si une fonction est calculable, il existe un algorithme dans le langage que vous utilisez qui permet de la calculer.

    Ecrire la fonction successeur qui prend en paramètre un entier et qui renvoie son successeur dans différents langages de programmation. Ecrire cette fonction à l'aide d'une machine de Turing.

    Décidabilité

    Une propriété est décidable s'il existe un algorithme qui la confirme ou l'infirme en un nombre fini d'étapes. L'algorithme doit répondre par oui ou par non à la question posée par le problème. On parle dans ce cas de problème de décision.

    Quelques remarques :

    Le problème de l'arrêt est non décidable

    Il nous est arrivé à tous d'écrire une boucle infinie. C'est le drame car notre programme ne s'arrête jamais. Dans certains domaines, ce problème devient un problème essentiel. Pensez aux problèmes de sécurité (centrale nucléaire, aviation, transports, etc).

    Il est donc naturel de se poser cette question :

    Peut-on écrire un algorithme capable de prédire que n'importe quel programme va s'arrêter ? La réponse est non. On dit que le problème de l'arrêt d'un programme est indécidable.

    Des exemples de programmes qui ne s'arrêtent pas.

    Que pensez-vous du script suivant ?

    def est_pair(n:int)->bool :
        """Renvoie true si n  est pair"""
        assert(isinstance(n,int)) # Test si n est entier
        test=False
        if n%2==0 : test=True
        return test
    
    
    def infini(n:int) : 
        while est_pair(n):
            n=n*2
        return n
    
    print(infini(5))
    print(infini(4))
    
    

    Inventer une boucle infinie qui ne soit pas triviale.

    Un exemple :

    # Boucle infinie
    a=1
    while a==1:
        a=0
        if a==1 : a==0
        else :a=1
    

    Démonstration par l'absurde de la non décidabilité du problème de l'arrêt d'un programme.

    Raisonnement par l'absurde : manière de raisonner qui consiste à démontrer la vérité d'une proposition en prouvant l'absurdité du contraire de celle-ci. Synonyme : apagogie.

    On cherche à démontrer une propriété. On prend comme hypothèse la proposition contraire et on en déduit une (ou des) conséquence(s) absurdes.

    Nous allons utiliser ce moyen pour démontrer la propriété suivante :

    Le problème de l'arrêt d'un programme est indécidable.

    Dans un premier temps, on fait l'hypothèse que l'on est capable de construire un algorithme halt qui résout le problème de l'arrêt d'un programme. L'objectif est de démontrer que cette hypothèse est fausse.

    fonction halt(P : programme) : booléen si P s'arrête alors on renvoie vrai sinon on renvoie faux

    On construit maintenant un deuxième algorithme que l'on appelle contradiction qui :

  • exécute l'algorithme halt
  • renvoie le mot "arrêt" si l'exécution de halt renvoie vrai
  • exécute une boucle infinie si l'exécution de halt renvoie vrai
  • procédure contradiction(P : programme) test←halt(P) si test=vrai alors on exécute une boucle infinie sinon on affiche "stop"

    On applique maintenant la procédure contradiction à elle même. On exécute contradiction(contradiction).

    1. On appelle halt(contradiction).
    2. Deux cas possibles :
      • Soit le programme contradiction s'arrête alors halt(contradiction) renvoie vrai. Mais dans ce cas le programme contradiction ne s'arrête pas car on exécute une boucle infinie.
      • Soit le programme contradiction ne s'arrête pas alors halt(contradiction) renvoie faux. Mais dans ce cas le programme contradiction s'arrête en affichant "stop".

    On obtient donc une contradiction : contradiction(contradiction) aboutit à deux cas contradictoires. Par ce raisonnement par l'absurde, notre hypothèse de départ : "on est capable de construire un algorithme halt qui résout le problème de l'arrêt d'un programme" est fausse.

    Nous venons donc de démontrer que le programme de l'arrêt est indécidable.

    Vous retrouverez cette démonstration dans cette vidéo.

    Pour les curieux : la notion en logique de paradoxe.

    Intéressez vous à la proposition suivante :"je suis un menteur".

    Si je dis que je suis un menteur alors ce que je dis est faux, donc je ne mens pas. Mais j'ai donc menti en disant que je suis un menteur.

    Maintenant, considérons que ce que je dis est faux. On peut donc dire que je ne mens pas. Si je ne mens pas alors l'affirmation "je suis un menteur" est vraie. Donc je mens, ce qui contredit mon hypothèse de départ.

    Ce paradoxe du menteur serait attribué à Epiménide le Crétois (VIIème sicle av J-C).

    On parle dans ce cas d'autoréférence. Une phrase ou une formule fait référence à elle même. Cette notion a beaucoup d'applications en mathématiques, philosophie et en programmation. Un énoncé contenant une autoréférence est parfois paradoxal.

    En 1931, Kurt Gödel, pour démontrer son théorème d'incomplétude, utilise un énoncé inspiré de ce paradoxe.

    Pour aller plus loin

    Savoir et Savoir faire