Montrez qu'il y a infiniment plus de problèmes que nous ne pourrons jamais en calculer

8

Je regardais cette lecture du MIT sur la complexité de calcul et à la minute 15h00, Erik Demaine se lance dans une démonstration pour montrer ce qui est indiqué dans le titre de cette question. Cependant, je ne peux pas suivre son raisonnement, dans la pratique ce qu'il dit est le suivant:
nous pouvons énoncer un problème de décision sous la forme d'une chaîne de et qui, en pratique, est la table de vérité de la fonction. Il poursuit en disant qu'un problème de décision est une chaîne infinie de bits alors qu'un programme est une chaîne finie de bits et jusqu'ici aucun problème. Ce que je ne comprends pas, c'est la suite de la preuve à partir de là: les problèmes de décision sont dans01
R car vous pouvez mettre un point décimal avant la chaîne représentant le problème, obtenant ainsi la partie décimale d'un réel

 for example if you have 0111011010101010101... it could become x.0111011010101010101... 

Un programme est "juste" un entier dans car il s'agit d'une chaîne finie de bits. Le point que je n'arrive pas à comprendre est comment il est possible qu'un problème de décision soit comparable à un nombre réel au lieu d'un entier ... Je veux dire, si nous utilisons l'argument de "mettre un point devant le nombre" ne pourrait pas le même raisonnement s'applique-t-il également au nombre d'algorithmes possibles pouvant être produits?N

Yamar69
la source
11
Le fait est que le nombre d'algorithmes est dénombrable, tandis que le nombre de problèmes de décision est indénombrable. Je suggère de rechercher ces termes dans un manuel sur la théorie des ensembles élémentaires.
Yuval Filmus
1
@Yuval Filmus Je suis parfaitement conscient de la signification de ces termes, ce que j'ai du mal à assimiler est la raison de ces différentes cardinalités (algorithmes / problèmes de décision).
Yamar69
1
@JimmyB la même affirmation est vraie pour les nombres rationnels, mais les nombres rationnels sont toujours dénombrables (ayant la même "taille" que les entiers) tandis que les nombres réels ne le sont pas.
Gregory J.Puleo
1
Plus intéressant peut-être, il existe une infinité de problèmes de décision à spécification finie qui ne peuvent être résolus par aucune machine de Turing. Vous n'avez pas besoin de faire appel à des ensembles innombrables pour conclure qu'il existe une infinité de problèmes algorithmiquement insolubles. Vous n'avez pas besoin de l'indénombrabilité des nombres réels pour conclure que l'ensemble des nombres réels calculables a un complément infini.
John Coleman
1
"... que nous ne pourrons jamais calculer" suggère que les problèmes que nous pouvons calculer varient avec le temps. La définition de "calculable" ne dépend pas du temps.
David Richerby

Réponses:

9

Si je vous comprends bien, votre question est - pourquoi une solution peut être codée par un nombre naturel et un problème avec un nombre réel. (Je suppose que vous comprenez la phase suivante de la preuve qui est basée sur la différence entre les ensembles de cardinalitéc et 0.)

La raison réside dans la théorie des ensembles, plus précisément dans la cardinalité des différents ensembles. Comptez le nombre de programmes - c'est la taille des différentes chaînes d'une langue spécifique ou d'un jeu de caractères (ASCII par exemple). Cette taille est équivalente à la taille de l'ensembleN(nombres naturels). (Chaque chaîne peut être représentée comme sa valeur calculée par sa représentation binaire.)

Mais, en comptant le nombre de fonctions des nombres naturels (ou chaînes qui les représentent) à {0,1}, eh bien c'est une toute autre histoire, et ici nous avons affaire à des différences de taille entre deux ensembles infinis; la taille de cet ensemble est plus grande. Il y a une belle preuve qui est basée sur le fait que les fonctions deNà tous les ensembles mentionnés ci-dessus ne peut pas être "sur", ce qui conduit à la conclusion de la différence de cardinalité. Vous pouvez lire la preuve ici .

royashcenazi
la source
11

Reformulant d'une manière mathématique plus précise, ce que le professeur essaie de dire est le suivant: tout algorithme peut être (uniquement) codé comme une chaîne finie de bits, et toute chaîne finie de bits (de manière unique) code un programme; il y a donc une bijection entreNet l'ensemble d'algorithmes, donc les deux sont des ensembles dénombrables. A l'inverse, après avoir corrigé un ordre de chaînes, tout problème de décisionP peut être (uniquement) codé comme une chaîne infinie de bits, où le je-th bit représente si le je-la chaîne est dans Pou non, et toute chaîne infinie de bits (de manière unique) code un problème de décision (de la même manière); Par conséquent,R et l'ensemble des problèmes de décision sont tous deux indénombrables.

dkaeae
la source
6

Chaque algorithme peut être décrit par une chaîne finie, et il n'y a donc que de nombreux algorithmes. En revanche, nous pouvons décrire chaque problème de décision comme une décimale infinie dans la base 2, et en plus c'est une cartographie surjective : chaque nombre dans[0,1]peut être "décodé" en un problème de décision. Il existe donc de nombreux problèmes de décision.

L'argument de décodage ne fonctionne pas pour les algorithmes - alors que chaque algorithme correspond à une décimale finie, cela ne couvre pas tout [0,1], mais seulement un sous-ensemble dénombrable de celui-ci.

Yuval Filmus
la source