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

29

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.

hsalin
fonte
Ao comparar dois conjuntos infinitos, a semântica de "mais" precisa ser revisada.
Raphael

Respostas:

31

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 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{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.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:NNf:{0,1}{0,1}NN=2N

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 .2N

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 ).N<2N

Kaveh
fonte
Boa resposta! O que eu não entendo (talvez esteja faltando algo trivial aqui) é como você obtém ? NN=2N
Hsalin
É aritmética cardinal. Escreva os números naturais em uma sequência infinita de números naturais em binário, que deve dar a intuição.
22413 Kaveh
Por que essa suposição é verdadeira - "Cada algoritmo tem uma descrição finita usando símbolos de um conjunto finito"? Por que um algoritmo não pode ter uma descrição infinita?
Roland Pihlakas
@RolandPihlakas que faz parte da definição de um algoritmo (se você preferir, um programa de computador).
Kaveh
9

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:N{0,1}:xN,f(2x)=K(x)}.
fFF

R

G={g:N{0,1}:nNmn,g(m)=R(m).}
gGRGG

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.

Yuval Filmus
fonte