« Calculabilité et modèles de calcul » : différence entre les versions
(Page créée avec « '''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 ... ») |
Aucun résumé des modifications |
||
| Ligne 1 : | Ligne 1 : | ||
= 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. |
||
| ⚫ | Une question fondamentale de l’informatique théorique est de déterminer si un problème donné peut ou non |
||
La calculabilité est une branche de la logique et de l'informatique théorique. |
|||
| ⚫ | |||
| ⚫ | |||
== Fonction calculable == |
|||
''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 |
|||
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 |
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… |
- somme, différence, produit, égalité, division, puissance…union, intersection, quantification bornée… |
||
- PGCD ( |
- PGCD (algorithme 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. |
|||
== 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 : |
|||
| ⚫ | |||
'''-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. |
|||
- « 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. |
|||
''Étudions maintenant le nombre de fonctions calculables.'' |
|||
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. |
|||
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. |
|||
== 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. |
|||
| ⚫ | |||
| ⚫ | |||
'''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. |
|||
| ⚫ | |||
| ⚫ | |||
== Machine de Turing == |
|||
[[Fichier:Lego_Turing_Machine.jpg]] |
|||
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. |
|||
| ⚫ | |||
| ⚫ | |||
Q est un ensemble fini d’états. |
Q est un ensemble fini d’états. |
||
| Ligne 40 : | Ligne 63 : | ||
Σ est l’alphabet (fini) d’entrée. |
Σ est l’alphabet (fini) d’entrée. |
||
Γ est l’alphabet (fini) du ruban |
Γ est l’alphabet (fini) du ruban. |
||
δ : Q × Γ → Q × Γ × {G, D, I} est la fonction de transition. |
δ : Q × Γ → Q × Γ × {G, D, I} est la fonction de transition. |
||
| Ligne 47 : | Ligne 70 : | ||
F ⊆ Q est l’ensemble des états accepteurs. |
F ⊆ Q est l’ensemble des états accepteurs. |
||
Exemple d'utilisation de Turing : |
Exemple d'utilisation de Turing : |
||
[https://interstices.info/jcms/nn_72391/comment-fonctionne-une-machine-de-turing |
[https://interstices.info/jcms/nn_72391/comment-fonctionne-une-machine-de-turing |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
== Automate cellulaire == |
|||
| ⚫ | |||
[[Fichier:canon.png]] |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
Il est constitué d'une grille et de plusieurs états, souvent 2 : mort ou en vie. |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
''Les règles du jeu de la vie sont les suivantes :'' |
|||
Les cellules qui survivent sont celles qui ont 2 ou 3 cellules adjacentes. |
|||
== Jeu de la vie == |
|||
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... |
|||
[http://www.cypris.fr/loisirs/le_jeu_de_la_vie/jeu_de_la_vie.htm] |
|||
| ⚫ | |||
''Extension possible :'' automate d'ulma, automate de la neige extraterrestre. |
|||
[http://therese.eveilleau.pagesperso-orange.fr/pages/truc_mat/textes/conway.htm |
|||
| ⚫ | |||
== Explication plus complète == |
|||
Version du 25 mai 2017 à 12:18
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.