Demander un code

Une fonction d'arrêt constructive

Le projet

Le théorème de l'arrêt de Allan Turing annonce l'impossibilité de construire un algorithme qui sait déterminer quels algorithmes s'arrêtent ou non. Le cadre des machines de Turing est aproprié pour traiter cette question parce qu'il simplifie la notion de calcul et d'algorithme jusqu'à son expression la plus simple. C'est pourtant dans ce cadre que je propose de construire un algorithme d'arrêt (complètement constructif) qui détermine pour chaque entrée si elle s'arrête ou non. Y-a-t-il une erreur dans le théorème de Turing-Church ? Non, c'est rendu possible en élargissant la notion de 'réponse'. interdit le calcul des alogrithmes qui s'arrêtent. L'étude de cet algorithme appliqué à lui-même (l'argument de contradication) est alors très instructive.

L'article

Une fonction d'arrêt constructive
Au format PDF
Année: 2014
Taille: 34 pages

Commentaire sur cette page

--- Aucun commentaire pour l'instant. Ajoutez le premier... ---



Commentaire à ajouter

Nom, alias :

Traduction --

En quelques mots


Le langage exploite la richesse du fond expérimental historiquement synthétisé, mais ne le détient pas en propre.(Théorie du langage)

Texte au hasard


Plongement univoque du paradoxe de Richard. Pour la compréhension de cet article, je suppose connu le concept de Machine de Turing ainsi que le procédé diagonal de Cantor. Introduction Voici un énoncé du paradoxe de Richard : si on numérote tous les nombres réels définissables en un nombre fini de mots, alors par le procédé diagonal de Cantor sur les décimales de ces réels, on peut construire un nombre...
[...la suite ]