(Faux?) Preuve de calculabilité d'une fonction?

Considérons , une fonction qui retourne 1 si zéros apparaissent consécutivement dans . Maintenant, quelqu'un m'a donné une preuve que est calculable:n π f ( n $f(n)$$n$$\pi$$f(n)$

Soit pour tout n, apparaît dans , soit il y a am st apparaît dans et n'apparaît pas. Pour la première possibilité ; Pour le second ssi , 0 sinon. π 0 m π 0 m + 1 f ( n ) : = 1 f ( n ) : = 1 n ≤ $0^n$$\pi$$0^m$$\pi$$0^{m+1}$$f(n) := 1$$f(n) := 1$$n \leq m$

L'auteur affirme que cela prouve la calculabilité de , car il existe un algorithme pour le calculer.$f(n)$

Cette preuve est-elle correcte?

Pensez-y de cette façon, Mike: Cette preuve se "ramifie" en plusieurs cas possibles, dont l'un doit être vrai (en utilisant la loi du milieu exclu que pour chaque proposition , soit est vrai ou est vrai) . Mais à la fin de chacune de ces branches, vous parvenez toujours à prouver que la fonction est calculable. Par conséquent, quel que soit le cas réel dans la vie réelle, doit être calculable. (Cependant, la raison précise pour laquelle f est calculable sera différente, selon la branche.)p ¬ p f $p$$p$$\neg p$$f$$f$ $f$

C'est correct. C'est la même chose que la suivante: définissez comme la fonction constante x ↦ 0 si Dieu existe, et x ↦ 1 si Dieu n'existe pas. La fonction résultante est une fonction constante, donc calculable. Ce que vous ne pourrez peut-être pas faire, c'est donner cette fonction, mais la fonction elle-même est calculable.$f(x)$$x \mapsto 0$$x \mapsto 1$

Ici, l'une des deux possibilités est vraie: soit il existe un tel , soit il n'en existe pas. La fonction est soit la fonction constante x ↦ 1, soit une fonction seuil simple, définie avec m .$m$$x \mapsto 1$$m$

Je pense - et j'espère - que chaque étudiant en informatique est confronté à ce problème qui ressemble à un paradoxe. C'est un très bon exemple de la différence entre calculable au sens TCS et calculable au sens pratique.

$\pi$$\pi$

$f$$\exists M \in TM : f_M = f$

L'idée de base de la preuve est: je vous donne une classe infinie de fonctions, toutes calculables (à montrer; triviales ici). Je prouve alors que la fonction que vous recherchez est dans cette classe (pour montrer; distinction de casse ici). qed

Oui, c'est vrai, c'est calculable. Le problème est que votre fonction ne produit vraiment pas la solution à une famille infinie de problèmes, comme (par exemple) une fonction calculant une solution au problème d'arrêt - donc il n'y a pas de problème de calcul. Au lieu de cela, vous représentez sous forme de fonction un fait mathématique unique avec une représentation finie - soit un entier, soit le fait que f est la fonction constamment 1

$\Omega$

Bien sûr, trouver l'algorithme correct pourrait être un problème difficile. Mais trouver des algorithmes corrects est généralement difficile!

poster un peu vieux, mais je voulais poster une autre réponse.

Il s'agit d'une preuve (ou argument) non constructif de calculabilité. Il dit simplement que la fonction doit exister dans un certain sens puisque je peux la représenter (ou plus correctement l'indexer), dans l'ensemble (ou l'univers) des fonctions calculables. Cependant, il ne construit ni la machine elle-même (c'est-à-dire l'algorithme), ni l'index (en supposant une énumération efficace des machines calculables). L'expression anglaise « merci pour rien » semble dans ces cas la plus appropriée, comme suit:

-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!

Les gens de l'histoire des mathématiques se sont beaucoup disputés sur la validité réelle (ou la plage de validité) et la signification de ces arguments. Le résultat final est que le même type d'arguments réapparaît dans les théorèmes d'incomplétude de Goedel et se retourne contre cette "hypothèse de l'univers fermé" .

Si vous n'aimez pas tellement ces arguments, je ne vous en voudrais pas.