Aula de Teoria da Computabilidade de 19.08.2004, Prof Prolo
1 Cantor, conjuntos não enumeráveis, funções não-computáveis e
problemas não decidíveis
George Cantor mostrou (1874) que existem cardinais acima de ℵ0 , usando um método que hoje é conhecido como Método da diagonal de Cantor. Nas próximas seções mostramos alguns conjuntos não
enumeráveis importantes, utilizando este método. O trabalho de Cantor vai muito além disto, mas aqui
nos restringimos ao que nos interessa para a disciplina. Ao final concluimos, a partir de resultados de
cardinalidae vistos, que existem funções não computáveis e problemas não decidíveis.
2 O conjunto dos números reais (R) é não-enumerável
Vamos nos restringir aqui apenas ao intervalo (0, 1] por simplicidade. (É óbvio que R não pode ser menor
do que (0, 1].
1. A prova é por contradição (ou redução ao absurdo). Primeiro assumimos como Hipótese que o
conjunto é enumerável. Ora, nós queremos provar exatamente o contrário, isto é, ao final concluímos
que se tal hipótese for verdadeira chega-se a uma contradição, e portanto a hipótese não é verdadeira:
o conjunto dos reais não é enumerável.
2. Ora, se o conjunto é enumerável por hipótese, então deve existir uma enumeração para ele (mesmo
que nós não saibamos qual/como ela é):
r0 , r1 , r2 , r3 , r4 , r5 , r6
3. Nota: Todo número real pode ser representado
em decimal com mantissa infinita. Alguns porque
√
naturalmente a tem como 0.033333 · · · , π, abc. Mas mesmo os que tem mantissa finita, como 0.25,
podem ser representados como 0.2499999 · · · . Isto não é central ao argumento, apenas mostra que
representações com mantissa infinita (sem zeros não significativos à esquerda) tem correspondência
bijetora com os reais.
4. O diagrama abaixo mostra esquematicamente uma enumeração qualquer do intervalo (0, 1], que deve
existir de acordo com 2 acima. Cada linha representa um número. Cada número é uma sequência
infinita de dígitos a partir do ponto decimal (Como estamos representando apenas o intervalo (0, 1],
antes do ponto decimal é sempre 0, que não é representado). O número π/10, por exemplo, seria
representado como
3 1 4 1 5 ··· ,
e deve ser listado em uma linha k ∈ N. rk,0 = 3, rk,1 = 1, rk,2 = 4, rk,3 = 1, rk,4 = 5, · · · . Na
verdade, para todo número no intervalo (0, 1] deve haver um k ∈ N tal que o número é representado
na linha k da tabela abaixo.
Linha
0
1
2
3
4
5
6
...
Representação do número
r0,0 r0,1 r0,2 r0,3 r0,4 . . .
r1,0 r1,1 r1,2 r1,3 r1,4 . . .
r2,0 r2,1 r2,2 r2,3 r2,4 . . .
r3,0 r3,1 r3,2 r3,3 r3,4 . . .
r4,0 r4,1 r4,2 r4,3 r4,4 . . .
r5,0 r5,1 r5,2 r5,3 r5,4 . . .
r6,0 r6,1 r6,2 r6,3 r6,4 . . .
... ... ... ... ... ...
5. Imagine agora o número real x, cuja representação
x0 x1 x2 x3 x4 . . . xl . . .
é construída da seguinte forma:
x0 = 9 − r0,0
x1 = 9 − r1,1
x2 = 9 − r2,2
x3 = 9 − r3,3
x4 = 9 − r4,4
...
xl = 9 − rl,l
Para cada l ∈ N, o l_ésimo dígito de x após o ponto decimal é o complemento de 9 do l_ésimo
dígito do número listado na linha l da enumeração.
6. Não há a menor dúvida de que a construção acima representa um número real no intervalo (0, 1].
Portanto o número deve pertencer à enumeração, por exemplo numa linha k ∈ N qualquer. Mas
pela definição o k_ésimo dígito de x é diferente do k_ésimo dígito desta linha. Ou seja, x não
corresponde a nenhum dos elementos da enumeração. Isto é uma CONTRADIÇÃO! A hipótese
original é, portanto, falsa;
7. NOTA1: O método de Cantor acima é chamado de método da diagonal porque o número x foi
definido utilizando os elementos da diagonal (rk,k ) da tabela da enumeração da hipótese.
3 O conjunto de funções totais dos naturais para os naturais (F =
{f : N → N|f é total }) não é enumerável
1. Primeiro note que ao provarmos que F não é enumerável provamos também que as funções parciais
não o são pois F é um subconjunto das parciais. O motivo da restrição para totais é por força do
argumento que será utilizado abaixo.
2. O método é o mesmo usado acima. Primeiro assumimos como Hipótese que o conjunto F é enumerável. Ora, nós queremos provar exatamente o contrário, isto é, ao final concluímos que se tal
hipótese for verdadeira chega-se a uma contradição, e portanto a hipótese não é verdadeira: o conjunto das funções de N em N não é enumerável.
3. Ora, se o conjunto é enumerável por hipótese, então deve existir uma enumeração para ele (mesmo
que nós não saibamos qual/como ela é):
f0 , f1 , f2 , f3 , f4 , f5 , f6
4. Nota: Duas funções f, g :∈ N são iguais, sse elas são iguais par todo elemento do domínio; são
diferentes sse existe algum x ∈ N para o qual f (x) 6= g(x). Podemos portanto representar uma tal
função f como uma sequência infinita
f (0), f (1), f (2), f (3), ...
(ou imagine o grafo de f = {(0, f (0)), (1, f (1)), (2, f (2)), (3, f (3)), . . .}).
5. O diagrama abaixo mostra esquematicamente uma enumeração qualquer de F , que deve existir pela
hipótese. Cada linha representa uma função. Cada coluna x corresponde ao valor da função aplicada
a x. Para toda a função de F deve haver um k ∈ N tal que a função é representada na linha k da
tabela abaixo.
Função
0
1
2
3
4
5
6
...
0
f0 (0)
f1 (0)
f2 (0)
f3 (0)
f4 (0)
f5 (0)
f6 (0)
...
1
f0 (1)
f1 (1)
f2 (1)
f3 (1)
f4 (1)
f5 (1)
f6 (1)
...
Argumentos
2
3
f0 (2) f0 (3)
f1 (2) f1 (3)
f2 (2) f2 (3)
f3 (2) f3 (3)
f4 (2) f4 (3)
f5 (2) f5 (3)
f6 (2) f6 (3)
...
...
4
f0 (4)
f1 (4)
f2 (4)
f3 (4)
f4 (4)
f5 (4)
f6 (4)
...
...
...
...
...
...
...
...
...
...
6. Imagine agora a função f ∈ F , cuja representação
f (0) f (1) f (2) f (3) f (4) . . . f (l) . . .
é construída da seguinte forma:
f (0) = f0 (0) + 1
f (1) = f1 (1) + 1
f (2) = f2 (2) + 1
f (3) = f3 (3) + 1
f (4) = f4 (4) + 1
...
f (l) = fl (l) + 1
Para cada l ∈ N, f é diferente da função fl da linha l da enumeração, pois por construção, f é
diferente de fl quando aplicada ao argumento l (f (l) = fl (l) + 1). Portanto f não pertence à
enumeração. Mas como f ∈ F , por hipótese f pertence à enumeração. Novamente chegamos a
uma contradição. A hipótese original é portanto falsa. F não é enumerável.
4 CONCLUSÃO 1: Existe função não computável.
Vimos que o conjunto de todos os programas (procedimentos efetivos) em uma dada linguagem (PROGS)
é enumerável. Mas o conjunto das funções sobre os naturais (F ) não é enumerável card(F ) > ℵ0 ..
Portanto, não existe bijeção entre PROGS e F . Não tem como associar um programa para cada função.
Tem “mais” funções do que programas. Donde se conclui que existem funções não computáveis (na
verdade muitas!, infinitas! – existem “mais” funções não-computáveis do que funções computáveis).
5 CONCLUSÃO 2: Existe problema não decidível.
1. Com argumento similar ao usado para o conjunto F das funções totais dos naturais para os naturais,
pode-se mostrar o subconjunto de F , das funções totais binárias de naturais F B = {f : N →
{0, 1}|f é total }) também não é enumerável. Esta prova foi incluída como exercício na página da
disciplina.
2. Ora, F B é exatamente o conjunto dos problemas de decisão (definidos anteriormente) para os naturais. Em termos de conjuntos, F B representa o conjunto potência de N (2N , o conjunto de todos
os subconjuntos de naturais) – de fato, cada membro f de F B é a função característica de um
subconjunto dos naturais.
3. Ou seja o número de problemas de decisão não é enumerável. Visto que PROGS é enumerável,
novamente concluímos pela existência de (infindáveis) problemas que não são decidíveis.
4. Note que F B ⊂ F , portanto o fato de que F B não é enumerável por si só implica que F também
não é.
6 Conclusão final:
Existem funções matemáticas que não podem ser computadas (não podem ser expressas por procedimento
efetivo), problemas que não podem ser decididos por computador e conjuntos que não podem ser enumerados por programa de computador.