Utilisateur:Ydadloupi/Brouillon

Démonstration pour les fonctions (par le théorème du point fixe de Kleene)

Le 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 ($\phi _{p}=\phi _{T(p)}$).

Supposons que la propriété F soit non triviale (F$\neq \emptyset$ et F$\neq$FC). Nous montrons que la récursivité de P conduit à une contradiction.

Comme F est non triviale, il existe f $\in$ F et g $\in FC\setminus F$. Les fonctions f et g étant calculables, il existe deux programmes p et q avec $\phi _{p}$ = f et $\phi _{q}$ = g . Définissons le transformateur de programmes T:

T(x) = q si x $\in$ P

T(x) = p si x $\not \in$ 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 $\phi _{n}=\phi _{T(n)}$. Quelle est la valeur de T(n); est-ce p ou q ?

Si T(n)=p, par définition de T, on a n $\not \in$ P. Comme $\phi _{n}=\phi _{T(n)}$, T(n) $\not \in$ P. Or T(n)=p$\in$ P. Contradiction.

Si T(n)=q, alors n $\in$ P. Comme $\phi _{n}=\phi _{T(n)}$, T(n) $\in$ P. Or T(n)=q $\not \in$ P. Contradiction.

${\displaystyle }$

test

lien vers article interne

• Gérer mon brouillon
• Demander une relecture (voir les demandes)
• Publier mon brouillon

Cette page est un brouillon appartenant à Ydadloupi

Conseils de rédaction

• → 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.

Rice

Titre section

Ligne d'exemple, à annuler