Parece inacreditável, mas existe uma meta-máquina universal de Turing, capaz de computar *qualquer* função f:N->N, *incluindo as não-computáveis*, desde que você ache um universo paralelo apropriado!
A demonstração em si não é difícil, mas eu vou dar uma simplificada aqui para ficar mais fácil de entender. Quem quiser ver a versão original, é só pegar no link acima que tem os detalhes (thx
Joao Kogler pelo link):
Passo 1: Vamos relembrar o "teorema do reirom": existe um emulador capaz de emular qualquer sistema. Formalmente: as máquinas de Turing são enumeráveis, ou seja, para cada máquina você atribuir um número inteiro único. Com isso, você consegue construir uma máquina universal que tem como input o número da máquina que você quer emular, e o input original do problema que você quer resolver. Assim, você emula qualquer função computável.
Passo 2: Vamos relembrar que nenhum sistema formal é completo. Pelo teorema de Gödel, sempre existem proposições de um sistema que não admitem demonstração. E mais, mesmo que você pegue uma proposição e adicione com axioma ao sistema, ele continua sendo incompleto. Você pode adicionar infinitas proposições, sempre vai faltar uma.
Passo 3: Vamos relembrar que um sistema formal admite proposições que são independentes do sistema. Ou seja, tanto faz se você adiciona p ou não-p ao sistema, ele continua consistente. Exemplos conhecidos são o teorema das paralelas em relação aos outros axiomas do Euclides, ou a hipótese do continuum em relação à teoria dos conjuntos (ZFC).
Passo 4 (a pegadinha): Se você tem um sistema formal S onde tanto faz adicionar a proposição p ou a não-p, isso significa que, depois de adicionar a proposição, os sistemas S+p e S+não-p tem *um bit a mais de informação*. Para checar o valor desse bit, é só verificar qual proposição foi adicionada, se foi p o bit é 1, se foi não-p o bit é 0.
Passo 5 (a parte técnica): Se você conseguir construir uma sequência ordenável de proposições p_i, onde todas são independentes entre si, então você consegue adicionar ao sistema S uma string infinita de bits. Essa é a parte complicada da demonstração original, onde ele mostra como construir essa sequência. Mas o fato é que é possível, em qualquer caso.
Passo 6: Se você adicionou uma string infinita de bits ao sistema, então você codificou uma função binária f:N->{0,1} dentro do sistema. Agora é só escrever um algoritmo que, dado n, calcula f(n) através da enumeração das propriedades que você construiu dentro do sistema. Esse é um algoritmo universal que calcula qualquer função binária, até as não-computáveis!, dado que você codificou a função na unha, valor a valor. Assim como o input da máquina universal era o problema + o código da máquina que tem que ser emulado, nessa aqui o input é o problema + o sistema formal acrescido dos p_i que você codificou.
Passo 7: Obviamente, se você tem uma função f:N->{0,1}, então você também tem uma função f:N->N, é só usar um código de comprimento variável, tipo UTF-8.
Pronto, agora você tem um meta-algoritmo que calcula qualquer função. É só levar o algoritmo para um universo onde as regras são S+p_i que ele computa sozinho a função para você! Achar um universo paralelo fica como exercício para o leitor.
Agora as implicações do teorema:
1. Utilidade prática: nula
2. Você consegue codificar f:N->N, mas não consegue codificar f:R->R (Como você adiciona um bit por vez, o máximo que você consegue colocar é aleph-zero. Para suportar os reais precisaria colocar c).
3. Uma das funções não-computáveis que você pode computar é a parada de Turing. Então tem um universo aí onde você pode determinar exatamente quais das nossas máquinas de Turing param, e quais não param! Mas nesse universo, eles não conseguem calcular a parada das máquinas deles, só das nossas.
4. Se você estiver criando um universo do zero, é um jeito bacana de esconder um easter egg dentro da matemática que rege seu universo. Fica a dica aí pra quem for onipotente.
