Utilisateur:Ydadloupi/Brouillon
Démonstration pour les fonctions (par le théorème du point fixe de Kleene)
modifierLe Théorème du point fixe de Kleene dit que pour tout transformateur de programme T qui est une fonction totale, il existe un programme p tel que les programmes p et T(p) calculent la même fonction ().
Supposons que la propriété F soit non triviale (F et FFC). Nous montrons que la récursivité de P conduit à une contradiction.
Comme F est non triviale, il existe f F et g . Les fonctions f et g étant calculables, il existe deux programmes p et q avec = f et = g . Définissons le transformateur de programmes T:
T(x) = q si x P
T(x) = p si x P
Comme P est récursif, T est une fonction totale calculable. Par le Théorème du point fixe de Kleene, il existe un programme n tel que . Quelle est la valeur de T(n); est-ce p ou q ?
Si T(n)=p, par définition de T, on a n P. Comme , T(n) P. Or T(n)=p P. Contradiction.
Si T(n)=q, alors n P. Comme , T(n) P. Or T(n)=q P. Contradiction.
test [1]
- → N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
- → Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.
Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :
- Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
- Indiquez les éléments démontrant la notoriété du sujet (aide).
- Liez chaque fait présenté à une source de qualité (quelles sources – comment les insérer).
- Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
- Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).
- → Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.
Titre section
modifierLigne d'exemple, à annuler
- Henriette Asséo, Les Tsiganes, une destinée européenne, Gallimard, , page 113.
- « Paléomusique : un concert sur les instruments vieux de 10 000 ans », France Musique, (lire en ligne, consulté le )