Pourquoi y a-t-il plus de fonctions non calculables que de fonctions calculables?

Je lis actuellement un livre sur les algorithmes et la complexité. En ce moment, je suis en train de lire sur les fonctions calculables et non calculables, et mon livre indique qu'il y a beaucoup plus de fonctions non calculables que calculables, en fait la majorité est non calculable, dit-il. Dans un certain sens, je peux l'accepter intuitivement, mais le livre ne donne pas de preuve formelle et n'élabore pas beaucoup sur le sujet.

Je voulais juste voir une preuve / laisser quelqu'un ici développer à ce sujet / comprendre plus strictement pourquoi il y a tellement plus de fonctions non calculables que de fonctions calculables.

computability turing-machines combinatorics hsaline
la source

Lorsque l'on compare deux ensembles infinis, la sémantique de "plus" doit être révisée.

Raphael

Réponses:

Le sont comptablement de nombreuses fonctions calculables:

Chaque fonction calculable possède au moins un algorithme. Chaque algorithme a une description finie utilisant des symboles d'un ensemble fini, par exemple des chaînes binaires finies utilisant des symboles . Le nombre de chaînes binaires finies notées est dénombrable (c'est-à-dire le même que le nombre de nombres naturels ). $\{0,1\}$ $\{0,1\}^*$ $\mathsf{N}$

Par conséquent, il peut y avoir tout au plus de nombreuses fonctions calculables. Il existe au moins de nombreuses fonctions calculables car pour chaque , la fonction constante est calculable. $c\in \{0,1\}^*$ $f(x)=c$

En d'autres termes, il existe une correspondance entre:

l'ensemble des fonctions calculables,
l'ensemble des algorithmes,
, l'ensemble de chaînes finies de , et $\{0,1\}^*$ $\{0,1\}$
, l'ensemble des nombres naturels. $\mathbb{N}$

D'autre part, il y a indénombrablement de nombreuses fonctions sur les chaînes (ou nombres naturels). Une fonction (ou ) attribue une valeur à chaque entrée. Chacune de ces valeurs peut être choisie indépendamment des autres. Il y a donc fonction possible. Le nombre de fonctions sur les nombres naturels est égal au nombre de nombres réels. $f:\mathbb{N} \to \mathbb{N}$ $f:\{0,1\}^* \to \{0,1\}^*$ $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$

Comme seules de nombreuses fonctions sont calculables, la plupart ne le sont pas. En fait , le nombre de fonctions est également non calculable . $2^{\mathbb{N}}$

Si vous voulez imaginer cela intuitivement, pensez aux nombres naturels et réels, ou aux chaînes binaires finies et aux chaînes binaires infinies. Il y a beaucoup plus de nombres réels et de chaînes binaires infinies que de nombres naturels et de chaînes finies. En d'autres termes, (pour une preuve de ce fait, voir l'argument diagonal de Cantor et l' arithmétique cardinale ). $\mathbb{N} < 2^\mathbb{N}$

Kaveh
la source

Bonne réponse! Ce que je ne comprends pas (je manque peut-être quelque chose de trivial ici), c'est comment obtenir

N^{N} = 2^{N}

$\mathbb{N}^\mathbb{N} = 2^\mathbb{N}$

hsalin

C'est l'arithmétique cardinale. Écrivez les nombres naturels dans une séquence infinie de nombres naturels en binaire, ce qui devrait donner l'intuition.

Kaveh

Pourquoi cette hypothèse est-elle vraie - "Chaque algorithme a une description finie utilisant des symboles d'un ensemble fini"? Pourquoi un algorithme ne peut-il pas avoir une description infinie?

Roland Pihlakas

@RolandPihlakas qui fait partie de la définition d'un algorithme (si vous préférez, un programme informatique).

Kaveh

Voici une construction "explicite" de nombreuses fonctions booléennes non calculables. Soit une fonction booléenne fixe non calculable, disons la fonction caractéristique du problème d'arrêt. Considérons l'ensemble des fonctions Chaque est non calculable et est indénombrable. $K$

F = {F : N \to {0, 1} : \forall X \in N, F (2 X) = K (X)} .

$F = \{ f \colon \mathbb{N} \to \{0,1\} : \forall x \in \mathbb{N}, f(2x) = K(x) \}.$

f \in F

$f \in F$

F

$F$

$R$

g = {g : N \to {0, 1} : \exists n \in N \forall m \geq n, g (m) = R (m) .}

$G = \{ g \colon \mathbb{N} \to \{0,1\} : \exists n \in \mathbb{N} \forall m \geq n, g(m) = R(m). \}$

g \in G

$g \in G$

R

$R$

G

$G$

G

$G$

Il y a donc beaucoup de fonctions non calculables puisque nous avons "infiniment de degrés" de liberté - l'infini réel plutôt que l'infini "potentiel" comme dans le cas calculable.

Yuval Filmus
la source