Calculabilité et modèles de calcul

Calculabilité pour des fonctions de N → N

Les cours d’informatique peuvent donner l’impression que pour chaque problème on peut trouver un algorithme de solution. Une question fondamentale de l’informatique théorique est de déterminer si un problème donné peut être ou non résolu par d’un ordinateur (par une procédure effective). En particulier se pose la question de déterminer si une fonction donnée peut être calculée au moyen d’un algorithme. La calculabilité qui est une branche de la logique et de l'informatique théorique, 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’algorithme. La calculabilité nous aide à comprendre les limites de ce que nous pouvons calculer et de ce que nous pouvons faire avec un ordinateur.

Fonction calculable

Une fonction f avec un argument x est calculable s’il existe un algorithme pour calculer f(x) peu importe le nombre d'étapes. Les fonctions calculables sont également appelées fonctions récursives ou fonctions programmables. 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 en mathématiques le sont :

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

- PGCD (algorithme d’Euclide)

-Programmes informatiques qui s'arrêtent.

Fonction non calculable

Une fonction non calculable est donc une fonction pour laquelle aucun programme n’existe. Les deux fonctions non calculables les plus connues sont :

- problème de l'arrêt c’est-à-dire l’exécution interminable d’un programme.

- « Castor affairé » : ce concept a été introduit en 1962 par le mathématicien hongrois Tibor Radó. C’est l'un des premiers exemples connus de fonction non calculable.

Un « castor affairé » est une machine de Turing à n états qui écrit un maximum de « 1 » sur le ruban avant de s’arrêter. Au-delà d’un n trop élevé on ne peut pas déterminer quel est le castor affairé pour un nombre d’états même avec un ordinateur puissant.

dénombrement de fonction calculable

Il existe une infinité de fonctions, l’ensemble des fonctions n’est donc pas dénombrable. Par contre l’ensemble des programmes, lui, est dénombrable. Il existe donc beaucoup plus de fonctions que de programmes par conséquent il existe un nombre infini de fonctions qui ne sont pas calculables par un programme ce qui revient à dire que la plus grande partie des problèmes que l’on peut définir en mathématiques n’ont pas de solution algorithmique.

Modèles de calcul

Machine de Turing 

Cette machine a été inventée par Alan Turing en 1936. Elle va définir la notion de fonction calculable. C’est une machine abstraite et mathématique. On peut exécuter n'importe quel programme que l'on peut exécuter sur un ordinateur, on peut aussi simulé n'importe quel automate fini ou à pile. Une machine de Turing est composée de plusieurs éléments :

- d'une unité de contrôle (registre d'état et table d'action)

- d'un ruban infini divisé en cases

- 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 déplacer à la tête de lecture/écriture.

Le ruban joue le rôle de périphérique entrée, sortie. Vierge au début on y inscrit les données que traite le programme.

La tête lecture/écriture lit le contenu de la case sur laquelle elle se trouve elle permet de l'effacer ou écrit un nouveau symbole. Elle peut se déplacer à gauche ou à droite.

A la fin du programme, les mots sur le ruban constituent le résultat final du calcul.

Le fonctionnement dépend de deux paramètres : du symbole lu (c'est la case où se trouve la tête de lecture/écriture) et de l'état de la machine. Ce couple va exécuter ce que demande le programme.

La machine de Turing est un sextuplé (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 : [https://interstices.info/jcms/nn_72391/comment-fonctionne-une-machine-de-turing ]

Automate cellulaire  

Un automate cellulaire 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 simples. 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 comprendre comment se comportait une structure artificielle, c'est à dire comme les êtres vivants. Elles constituent donc aussi un modèle de calcul.

L’automate cellulaire le plus connu est le jeu de la vie. On peut citer également L'automate d'Ullman et 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éellement un jeu mais plutôt un automate cellulaire qui est représenté sur une grille (un damier) dont les cellules sont blanches pour l'état mort  et noires pour l'état  vivant.

Le but est de faire reproduire, disparaître ou survivre les cellules. Chaque cellule comporte autour d'elles 8 cellules.