Catégorie : Concepts

Les fonctions récursives constituent une manière de définir ce qu’est un calcul par le seul langage des nombres entiers. L’idée consiste à partir de quelques fonctions extrêmement simples, considérées comme évidemment calculables, puis à autoriser un petit nombre de procédés pour en fabriquer de nouvelles à partir des anciennes. Parmi ces procédés figure la récursion…

Le lambda-calcul est un modèle de calcul entièrement fondé sur la notion de fonction, c’est-à-dire sur l’idée d’une opération qui reçoit quelque chose en entrée et renvoie un résultat. Là où la machine de Turing imite un dispositif mécanique parcourant un ruban, le lambda-calcul adopte un point de vue tout différent: calculer y consiste uniquement…

Une machine de Turing est un modèle théorique d’ordinateur, une sorte de machine imaginaire réduite à l’essentiel, conçue pour capturer ce qu’est fondamentalement un calcul. On se la représente comme un ruban de papier infiniment long, divisé en cases pouvant chacune contenir un symbole, que parcourt une tête de lecture capable de lire le symbole…

En théorie de la calculabilité, une réduction est un procédé qui consiste à ramener un problème à un autre, de manière à transférer ce que l’on sait de l’un vers l’autre. L’idée est la suivante: si l’on dispose d’une méthode mécanique pour transformer toute question du premier problème en une question équivalente du second, alors…

Le théorème de Rice généralise et amplifie considérablement le résultat du problème de l’arrêt. Il affirme, en substance, que toute question intéressante portant sur ce qu’un programme fait vraiment, c’est-à-dire sur son comportement et non sur la façon dont il est écrit, est indécidable. Autrement dit, il n’existe aucune méthode mécanique capable de déterminer à…

Le problème de l’arrêt pose une question en apparence simple: peut-on construire un programme qui, en examinant n’importe quel autre programme accompagné de ses données de départ, déterminerait à coup sûr si celui-ci finira par s’arrêter ou bien continuera de tourner sans fin? Un programme peut en effet s’exécuter puis se terminer normalement, ou au…

Les notions de décidabilité, de semi-décidabilité et d’indécidabilité concernent les problèmes de décision, c’est-à-dire les questions dont la réponse attendue est simplement oui ou non. Un problème est dit décidable lorsqu’il existe une procédure mécanique garantissant, pour n’importe quelle donnée qu’on lui soumet, de fournir la bonne réponse en un temps fini et de toujours…

Une fonction calculable est une opération pour laquelle il existe une méthode mécanique, une suite d’instructions précises et sans ambiguïté, permettant d’obtenir le résultat à partir des données de départ en un nombre fini d’étapes. L’idée intuitive est celle d’une recette que n’importe qui, ou n’importe quelle machine, pourrait suivre à l’aveugle sans avoir besoin…