Comment peut-on décider si a une séquence de chiffres?

On nous a donné l'exercice suivant.

Laisser

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Prouver que est calculable.$f$

Comment est-ce possible? Pour autant que je sache, nous ne savons pas si $\pi$ contient toutes les suites de chiffres (ou lesquelles) et un algorithme ne peut certainement pas décider qu'une séquence ne se produit pas . Par conséquent, je pense que $f$ n’est pas calculable, car le problème sous-jacent n’est que semi-décidable.

Il n'y a que deux possibilités à considérer.

• Pour chaque entier positif , la chaîne apparaît dans la représentation décimale de . Dans ce cas, l'algorithme qui renvoie toujours 1 est toujours correct.$n$$0^n$$\pi$

• Il existe un plus grand entier tel que apparaisse dans la représentation décimale de . Dans ce cas, l'algorithme suivant (avec la valeur codée en dur) est toujours correct:$N$$0^N$$\pi$$N$

  Zeros-in-pi(n):
   if (n > N) then return 0 else return 1
  

Nous n'avons aucune idée de laquelle de ces possibilités est correcte, ou quelle valeur de est la bonne dans le second cas. Néanmoins, l'un de ces algorithmes est garanti d'être correct. Ainsi, il existe un algorithme pour décider si une chaîne de zéros apparaît dans ; le problème est décidable.$N$$n$$\pi$

Notez la différence subtile avec l'ébauche de preuve suivante proposée par gallais :

1. Prenez une machine de Turing aléatoire et une entrée aléatoire.
2. Soit le calcul dure indéfiniment, soit il s’arrête à un moment donné et il existe une fonction calculable (constante) décrivant chacun de ces comportements.
3. ???
4. Profit!

Alex ten Brink explique:

observez ce que dit le théorème Halting: il dit qu’il n’existe pas de programme capable de décider si un programme donné est interrompu. Vous pouvez facilement créer deux programmes tels que l’un ou l’autre calcule si un programme donné s’arrête: le premier dit toujours «il s’arrête», le second «ça ne s’arrête pas» - un programme a toujours raison, nous ne pouvons pas calculer lequel d'entre eux est!

sepp2k ajoute:

Dans le cas de l'exemple d'Alex, aucun des algorithmes ne donnera le bon résultat pour toutes les entrées. Dans le cas de cette question, l'un d'entre eux le fera. Vous pouvez affirmer que le problème est décidable parce que vous savez qu'il existe un algorithme qui produit le bon résultat pour toutes les entrées. Peu importe que vous sachiez lequel est cet algorithme. dix

Je viens de poster une légère précision sur la réponse de JeffE.

Nous savons qu'il existe deux fonctions / cas pouvant calculer la fonction f (n):

1. Une fonction qui retourne toujours vrai (pour tout n, il existe n nombre de 0 consécutifs)
2. Une fonction qui renverra true si n est inférieur à un entier N, où N est défini comme la longueur maximale des zéros consécutifs existant dans le nombre irrationnel donné (sinon, elle renvoie false).

Une et une seule de ces fonctions peut être correcte. Nous ne savons pas lequel, mais nous savons avec certitude qu'il existe une réponse. La calculabilité nécessite l'existence d'une fonction capable de déterminer la réponse en un nombre fini d'étapes.

Le nombre d'étapes dans le cas 1 est trivialement lié à simplement renvoyer 1.

Dans le cas 2, le nombre d'étapes est également fini. Pour chaque entier nous pouvons construire une machine de Turing qui accepte si et sinon rejette en temps fini. Donc, ne pas savoir une limite supérieure sur n'a pas d'importance. Pour chaque il existe une machine de Turing, à savoir , qui calcule correctement si (nous ne savons pas lesquelles sont correctes, mais peu importe, il en existe une).T N ( n ) n < N N N T N ( n ) n < $N$$T_N(n)$$n < N$$N$$N$$T_N(n)$$n < N$

Bien qu'il ne soit peut-être pas possible de choisir entre les deux cas (même si l'un semble plus probable qu'un autre), nous savons que l'un d'entre eux doit être correct.

En remarque: notre solution suppose que bien que nous ne puissions pas déterminer quelle fonction déclenchera une valeur correcte, l’essence de la calculabilité ne repose pas sur la constructibilité de la preuve. L'existence pure est suffisante.

L'étape 5 de la tentative de preuve suivante est injustifiée et en fait fausse - un contre-exemple peut être trouvé ici . (merci, Yuval; cela ressemblait à la partie la plus esquissée du croquis). J'ai laissé la réponse ici car je pense que l'erreur est instructive.

Tout d'abord: la paire de réponses de JeffE est suffisante; f est calculable de toute façon.

Un bref détour, cependant, pour tenter d’esquisser une preuve par induction:
Prémisse R : ne se répète pas. 1. Regardez en base 2. Ceci est principalement pour réduire le nombre de cas. 2. Peu importe dans quelle mesure la ligne que vous alliez, vous trouverez toujours une autre 1 quelque part: l'alternative est tous les zéros, ce qui voudrait dire commence à répéter, ce qui va à l' encontre R . 3. Même chose pour aller le long de la ligne et trouver 0 . 4. Développez les séquences à deux chiffres: vous ne pouvez pas arrêter de rechercher 01 ou 10 (c’est-à-dire des endroits où il bascule), car sinonπ π π $\pi$
$\pi$
$\pi$

$\pi$ commencerait à répéter sur 1 ou sur 0 . De même, vous ne pouvez pas arrêter de rechercher 11 ou 00 , car sinon, la répétition commence sur 1010101 ...
5. L'étape inductive: chaque séquence finie doit apparaître un nombre infini de fois, car l'alternative est que commence à répéter le l' une des séquences plus courtes, ce qui contredit R .$\pi$