Por que existem mais funções não computáveis ​​do que funções computáveis?

Atualmente, estou lendo um livro sobre algoritmos e complexidade. No momento, estou lendo sobre funções computáveis ​​e não computáveis, e meu livro afirma que há muito mais funções que não são computáveis ​​do que computáveis; na verdade, a maioria é não computável, diz. Em certo sentido, posso aceitar intuitivamente isso, mas o livro não fornece uma prova formal nem elabora muito sobre o assunto.

Eu só queria ver uma prova / deixar alguém aqui elaborar sobre isso / entender mais estritamente por que existem tantas funções não-computáveis ​​quanto as computáveis.

O são countably muitas funções computáveis:

Cada função computável possui pelo menos um algoritmo. Cada algoritmo tem uma descrição finita usando símbolos de um conjunto finito, por exemplo, cadeias binárias finitas usando símbolos $\{0,1\}$ . O número de cadeias binárias finitas denotadas por $\{0,1\}^*$ é contável (ou seja, o mesmo que o número de números naturais $\mathsf{N}$ ).

Portanto, pode haver no máximo muitas funções computáveis. Existem , pelo menos, muitos função calculável contáveis uma vez que para cada , a função da constante de f ( x ) = C é calculável.$c\in \{0,1\}^*$$f(x)=c$

Em outras palavras, há uma correspondência entre:

• o conjunto de funções computáveis,
• o conjunto de algoritmos,
• , o conjunto de cadeias finitas de { 0 , 1 } e$\{0,1\}^*$$\{0,1\}$
• , o conjunto de números naturais.$\mathbb{N}$

Por outro lado, existem inúmeras funções sobre seqüências de caracteres (ou números naturais). Uma função (ou f : { 0 , 1 } ∗ → { 0 , 1 } ∗ ) atribui um valor para cada entrada. Cada um desses valores pode ser escolhido independentemente dos outros. Portanto, existem N N = 2 N possíveis funções. O número de funções sobre números naturais é igual ao número de números reais.$f:\mathbb{N} \to \mathbb{N}$$f:\{0,1\}^* \to \{0,1\}^*$$\mathbb{N}^\mathbb{N}=2^\mathbb{N}$

Como apenas muitas das funções são computáveis, a maioria não é. De facto, o número de funções uncomputable é também .$2^{\mathbb{N}}$

Se você quiser imaginar isso intuitivamente, pense em números naturais e números reais, ou em seqüências binárias finitas e seqüências binárias infinitas. Há muito mais números reais e seqüências binárias infinitas do que números naturais e seqüências finitas. Em outras palavras, (para uma prova desse fato, veja o argumento diagonal de Cantor e a aritmética cardinal ).$\mathbb{N} < 2^\mathbb{N}$

Aqui está uma construção "explícita" de inúmeras funções booleanas não computáveis. Seja uma função booleana fixa não computável, digamos a função característica do problema de parada. Considere o conjunto de funções F = { f : N → { 0 , 1 } : ∀ x ∈ N , f ( 2 x ) = K ( x ) } . Cada f ∈ F não é computável e F é incontável.$K$

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

$R$

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

Portanto, existem muitas funções não computáveis, pois temos "infinitamente muitos" graus de liberdade - infinito real, em vez de infinito "potencial", como no caso computável.