Calculabilité et modèles de calcul

1-Calculabilité pour des fonctions de N → N

Une question fondamentale de l’informatique théorique est de déterminer si un problème donné peut ou non être résolu au moyen d’un ordinateur (par une procédure effective). En particulier se pose la question de déterminer si une fonction donnée (à arguments et valeurs entiers) peut être calculée au moyen d’un algorithme. La question ainsi formulée est indépendante de la machine utilisée, de ses ́éventuelles performances, de la mémoire disponible ou encore du langage de programmation employé. La calculabilité est une branche de la logique et de l'informatique théorique. Elle permet de définir ce qui est calculable et ce qui ne l’est pas et nous montrera que pour de nombreux problèmes il n’existe pas d’algoritme. La calculabilité nous aide à comprendre les limites de ce que peuvent faire des ordinateurs. Une fonction f avec un argument x est calculable s’il existe un algoritme pour calculer f(x) peu importe le nombre d'étapes.

Qu'est-ce qui est programmable ?

Certaines de ces fonctions sont programmables, d'autres peut-être pas. Les fonctions programmables sont aussi appelées des fonctions calculables ou récursives Nous connaissons de très nombreuses fonctions calculables. En particulier toutes celles que nous avons programmées ! La plupart des fonctions que l'on rencontre naturellement en mathématiques le sont :

- somme, différence, produit, égalité, division, puissance…union,intersection,quantification bornée…

- PGCD (algoritme d’Euclide)

- Programmes informatiques qui s'arrêtent.

. Une fonction non calculable est donc une fonction f pour laquelle aucun programme P n'existe qui donne en sortie la valeur f(n) lorsqu'on lui donne en l'entier n en entrée, et ceci pour tout n ∈ N. -problème de l'arrêt : execution interminable d’un programme

-Castor affairé: Il s'agit d'une fonction bien définie, ayant des valeurs pour chaque entier, mais dont on ne peut pas calculer la valeur.Un castor affairé est, en théorie de la calculabilité, une machine de Turing qui atteint une « activité opérationnelle » maximale (comme le nombre de pas effectués ou le nombre de symboles écrits avant son arrêt) parmi toutes les machines de Turing d'une certaine classe. Celles-ci doivent satisfaire certaines spécifications et doivent s'arrêter après être lancées sur un ruban vierge.Une fonction du castor affairé quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n'est pas calculable. En fait, au bout d'un certain point, une fonction du castor affairé croît plus rapidement que n'importe quelle fonction calculable. Déterminer le castor affairé pour un ensemble de machines de Turing à n états donnés est un problème insoluble algorithmiquement ; en pratique, on ne peut même pas espérer le résoudre pour un nombre n au-delà de 10. Le concept, introduit en 1962 par le mathématicien hongrois Tibor Radó, est l'un des premiers exemples connus de fonction non calculable.

Étudions maintenant le nombre de fonctions calculables.

Il est clair qu'il y en a une infinité. Il suffit de considérer l'infinité des fonctions constantes. De plus, il ne peut pas y avoir plus de fonctions calculables qu'il n'y a de programmes,puisqu'à chaque fonction calculable lui correspond par définition un programme.Donc l’infinité des fonctions calculables n’est pas plus grande que celle des programmes. Et comme l’infini dénombrable est le plus petit infini, on en déduit que l’ensemble des fonctions calculables est infini dénombrable. D'autre part il y a une infinité non dénombrable de fonctions de N dans N. Il existe donc des fonctions non calculables. On peut même ajouter que dans un certain sens les fonctions non calculables sont infiniment plus nombreuses que les fonctions calculables. Les fonctions non calculables sont la règle générale, et les fonctions calculables l'exception.

2-Modèles de calcul

Machine de Turring : Cette machine est inventé de son nom de Alan Turing en 1936. Elle va definir la notion de fonction calculable.C'est une machine abstraite et mathématique.On peut executé n'importe quel programme que l'on peut executé sur un ordinateur, on peut aussi simulé n'importe quel automate fini ou à pile.Une machine de Turing est composé de plusieurs éléments : - d'une unité de contrôle(registre d'état et table d'action), d'un ruban inifini divisé en cases et d'une tête de lecture/ écriture.L'unité de contrôle permet la mémorisation de l'état courant et dit à la machine dans quel sens se deplacer à la tête de lecture/ecriture.Le ruban joue le rôle de périphérique entrée, sortie. Vierge au debut on y inscrit les données que traite le programme.La tête lecture/ecriture lit le contenu de la case sur laquelle elle se trouve elle permit de l'effacer ou ecrit un nouveau symbole. Elle peut se déplacer à gauche ou à droite.A la fin du programme ,les mots sur le ruban consituent le resultat final du calcul. Le fonctionnement depend de deux paramètres : symbole lu c'est la case où se trouve la tête de lecture/ecriture et l'état de la machine. Ce couple va exécuté ce que demande le programme.

La machine de Turing est un sextuplet(Q, Σ, Γ, δ, q0, F) :

Q est un ensemble fini d’états.

Σ est l’alphabet (fini) d’entrée.

Γ est l’alphabet (fini) du ruban .

δ : Q × Γ → Q × Γ × {G, D, I} est la fonction de transition.

q0 est l’état initial.

F ⊆ Q est l’ensemble des états accepteurs.

Exemple d'utilisation de Turing : [1]

Automate cellulaire : Un automate cellulaire c'est un objet mathématique que l'on peut étudier aussi en informatique. Il évolue par étape et selon des règles plus ou moins simple. Il est constitué d'une grille et de plusieurs états, souvent 2 : mort ou en vie. Cet objet mathématique provient des travaux de John Von Neumann et Stanislaw Ulaw en 1950 qui voulaient savoir comment se comportait une structure artifcielle, c'est à dire comme les etres vivants. Elles constituent donc aussi un modèle de calcul.

Un automate cellulaire très connu est le jeu de la vie.Autre automate cellulaire: L'automate d'Ulman, L'automate Neige extraterrestre des dérivés du jeu de la vie.

Jeu de la vie : Il est inventé en 1970 par John Conway ce n'est pas réelement un jeu mais plutot un automate cellulaire qui est représenté sur une grille( un damier) dont les cellules sont blanches pour l'etat 'mort' et noir pour l'etat 'vivant. Le but est de faire reproduire, disparaître ou survivre les cellules. Chaque cellules comporte autour d'elles 8 cellules.

3-Jeu de la vie en pratique

Les règles du jeu de la vie sont les suivantes :

Les cellules qui survivent sont celles qui ont 2 ou 3 cellules adjacentes.

Les celllles qui passent a l'état 'mort' sont celles ayant 4 ou plus cellules ajdcentes ou celle n'ayant une ou aucune cellule adjacentes.

Les cellules qui pasent à l'état 'vie' sont celles ayant exactement 3 cellules adjacentes.

Toutes les naissances et toutes les morts ont lieu en même temps au cours d'une génération.

Un site avec des exemples d'oscillations, des formes stables, des pulsars... [2]

Extension possible : automate d'ulma, automate de la neige extraterrestre. [http://therese.eveilleau.pagesperso-orange.fr/pages/truc_mat/textes/conway.htm ]