Comment prouver l'existence d'un nombre qui ne peut être écrit par aucun algorithme?

14

J'ai le problème:

Montrez qu'il existe un nombre réel pour lequel aucun programme n'existe qui s'exécute infiniment long et écrit les chiffres décimaux de ce nombre.

Je suppose que cela peut être résolu en le réduisant au problème de l'arrêt, mais je ne sais pas comment le faire.

J'apprécierais également les liens vers des problèmes similaires pour une pratique ultérieure.

algorithms reductions halting-problem fresheed
la source
Relavant: math.stackexchange.com/q/1266587/294695
John Coleman
1
en.wikipedia.org/wiki/Chaitin's_constant
chi
Yuval Filmus a fourni une réponse intéressante que vous devez lire attentivement. Le problème d'arrêt "est la chose" que vous pouvez essayer de réduire à votre problème, et non l'inverse (réduisez votre problème à l'arrêt - comme vous le supposez dans votre question).
quetzalcoatl
Cette question pourrait-elle être améliorée en corrigeant la grammaire dans la section citée? J'ai du mal à analyser.
JimmyJames
@JimmyJames, je l' ai fait de mon mieux pour le traduire du russe: Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. J'espère que quelqu'un améliorera ma traduction.
fresheed

Réponses:

18

Comme Sebastian l'indique, il n'y a que (en gros mais) de nombreux programmes. Listez-les pour créer une liste de programmes. La liste est (infiniment mais) infiniment longue. Chaque programme génère un nombre dans R. À partir de cela, nous pouvons créer une liste (infinie mais) dénombrable de nombres dans R. Maintenant, nous pouvons appliquer directement l' argument diagonal de Cantor pour prouver qu'il doit encore y avoir d'autres nombres.

Soit dit en passant, si l'algorithme a des arguments (finis), vous pouvez simplement réécrire cela comme une liste "plus longue" de programmes où chaque programme n'a pas d'arguments.

En ce qui concerne votre commentaire "Que faire si des nombres réels sont autorisés comme argument", alors la prémisse de la question est fausse: tous les nombres dans R peuvent alors être générés. Si quelqu'un trouve un nombre, disons 皮 et prétend qu'il ne peut pas être calculé, nous avons "l'algorithme" suivant:

func(number):
    return number

et appelez func (皮)

Albert Hendriks
la source
17

C'est en fait beaucoup plus simple. Il n'y a qu'un nombre dénombrable d'algorithmes. Pourtant, il existe d'innombrables nombres réels. Donc, si vous essayez de les coupler, certains vrais chiffres resteront suspendus.

Sebastian Oberhoff
la source
1

Le nombre est un nombre infiniment long qui, après la virgule décimale, code de toute façon toutes les machines de turing qui ne s'arrêtent pas. Avec ce numéro, vous seriez en mesure de résoudre le problème d'arrêt.

Vous pouvez "rechercher" la MT dans le numéro et l'exécuter en parallèle. Si TM s'arrête, il s'arrête. Sinon, vous "trouveriez son code dans le numéro".

Il existe de nombreuses modifications de la preuve et vous devriez pouvoir les reproduire après la toute première leçon de complexité :-)

smrt28
la source
Ceci est étroitement lié à la constante de Chaitin .
David Richerby
yah, bud beaucoup plus facile à comprendre ...
smrt28
-2

Un point se déplace dans un chemin par la fonction y = 2x. Lorsque l'abscisse est un nombre non calculable, le Point n'a aucun moyen de calculer son chemin, mais nous savons qu'il continue. Des nombres non calculables peuvent donc exister du tout.

Valmir
la source