Comment peut-il être décidable si $ \ pi $ a une certaine séquence de chiffres?

Question

On nous a donné l'exercice suivant.

  

Soit

     

$ \ qquad \ displaystyle f (n) = \ begin {cas} 1 et 0 ^ n \ texte {se produit dans la représentation décimale de} \ pi \\ 0 & \ text {else} \ end {cas} $

     

Prouver que $ f $ est calculable.

Comment est-ce possible? Pour autant que je sache, nous ne savons pas wether $ \ pi $ contient chaque séquence de chiffres (ou qui) et un algorithme peut certainement pas décider que certaines séquences est pas se produire. Par conséquent, je pense que $ f $ est pas calculable, parce que le problème sous-jacent est que semi-décidable.

Answer 1

Il n'y a que deux possibilités à prendre en compte.

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

• Il y a un plus grand entier $ N $ tels que $ 0 ^ N $ apparaît dans la représentation décimale de $ \ pi $ . Dans ce cas, l'algorithme suivant (avec la valeur $ N $ codées en dur) est toujours correct:

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

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

---

Notez la différence subtile avec l'esquisse suivante proposée par la preuve Gallais :

  

  
1. Prenez une machine de Turing aléatoire et une entrée aléatoire.
  
2. Soit le calcul se poursuivra pour toujours ou il arrête à un moment donné et il y a une (constante) fonction chiffrable décrivant chacun de ces comportements.
  
3. ???
  
4. Profit!
  

Alex ten Brink explique:

  

attention ce que le théorème l'arrêt: il dit qu'il n'y existe pas de programme unique qui peut décider si un programme donné de haltes. Vous pouvez facilement faire deux programmes tels que soit on calcule si un programme donné arrête: le premier dit toujours « il arrête », le second « il ne s'arrête pas » - un programme a toujours raison, nous ne pouvons pas calculer que l'on d'entre eux est!

sepp2k ajoute:

  

Dans le cas de l'exemple d'Alex ni des algorithmes renverra le bon résultat pour toutes les entrées. Dans le cas de celui-ci question d'entre eux. Vous pouvez demander que le problème est décidable parce que vous savez qu'il ya un algorithme qui produit le bon résultat pour toutes les entrées. Il ne sait pas si vous importe lequel cet algorithme est.   10

Answer 2

Il suffit de poster une légère élaboration sur la réponse de Jeffe.

Nous savons que deux fonctions / cas existent qui peuvent calculer la fonction f (n):

1. Une fonction qui retourne toujours vrai (pour tout n, il existe un nombre n de 0 consécutifs)
2. Une fonction qui retourne vrai si n est inférieur à un nombre entier N, où N est défini comme étant la longueur maximale de 0 consécutifs de qui existent dans le nombre irrationnel donné (sinon il retourne faux).

Une et une seule de ces fonctions peut être correcte. Nous ne savons pas qui, mais nous savons avec certitude qu'une réponse existe. Calculabilité exige qu'une fonction existe qui peut déterminer la réponse dans une quantité finie d'étapes.

Le nombre d'étapes dans le cas 1 est lié à trivialement juste retour 1.

Dans le cas 2 le nombre d'étapes sont également finis. Pour tout entier $ N $, nous pouvons construire une machine de Turing $ t_n (n) $ qui accepte si $ N

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

Comme une note de côté: notre solution que le suppose alors que nous ne pouvons pas déterminer quelle fonction va obtenir une valeur correcte, l'essence de la calculabilité ne repose pas sur la constructibilité de la preuve. Existence pure est suffisante.

Answer 3

Étape 5 de la tentative suivante est une preuve injustifiée, et en fait mal - un contre se trouve ici . (Merci, Yuval, il a fait sensation comme la sketchiest partie de l'esquisse). J'ai laissé la réponse ici que je pense que l'erreur est instructif.

---

Tout d'abord: la paire de réponses Jeffe est suffisante; f est calculable ou l'autre manière.

Un bref détour, bien que, dans une tentative d'esquisse d'une preuve par induction:
Prémisse R : $ \ pi $ ne se répète pas
. 1. Regardez $ \ pi $ dans la base 2. Ceci est la plupart du temps à 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 $ \ pi commence $ répéter, ce qui va à l'encontre R .
3. Idem pour aller en bas de la ligne et de trouver 0 .
4. Développez des séquences à deux chiffres: vous ne pouvez pas arrêter de trouver 01 ou 10 (qui est, des endroits où il commutateurs), parce que sinon $ \ pi $ serait commencer à répéter sur 1 's ou sur 0 ' s. De même, vous ne pouvez pas arrêter de trouver 11 ou 00 , car sinon il commence à se répéter sur 1.010.101 ...
5. L'étape inductive: chaque séquence finie doit apparaître un nombre infini de fois, car l'alternative est que $ \ pi $ commence à se répéter sur l'une des séquences plus courtes, ce qui contredit R .