Números Grandes e Maiores Ainda (6)

Saltemos um nível e saimos do esquema computável. Normalmente, usar formas combinatórias como iterar funções, criar arranjos, vetores, matrizes que iteram em cada entrada, etc, quase sempre são computáveis. Definamos então a função BB(n) como a Busy Beaver, que é o maior número de 1's que uma Máquina de Turing com até n estados pode computar. Digite "Máquina de Turing" na wikipédia português. É um dispositivo com poder de executar a maioira das operações que conhecemos. Os computadores atuais usam algoritmos que podem ser simulados por uma Máquina de Turing. A função BB(n) não é computável. Por exemplo, não podemos escrever um programa de computador que calcule BB(n) para cada n dado. Ela cresce, portanto, mais rápido que qualquer função citada anteriormente. Mas se quisermos definir um número bem grande, tomar BB(100) por exemplo pode não funcionar. Já tentei fazer uma máquina de Turing que calcula a função de Ackerman (digamos a função a[b]c, para b finito), e ela tinha mais de 4 mil estados. Não escrevi isso diretamente, mas fui iterando vários conceitos um no outro e um efeito multiplicativo me dava uma máquina com muitos estados. O número de Graham, portanto, certamente é menor que BB(4500). Mas evidências indicam que BB(25) já seria mais que suficiente. É difícil compactar a linguagem que usamos pra descrever alguma coisa em um número pequeno de estados. Mas, de qualquer forma, é de se esperar que para um texto com 1000 caracteres, 1 milhão de estados seria suficiente pra representar a máquina. Digamos que a função 10^n nos daria uma segurança em representar uma função definida em um texto com n caracteres (desde que essa função seja computável, é claro). Resumindo, BB(10^n), é uma função bem interessante, e BB(Googolplex) nos daria um número satisfatoriamente grande. Poderia chamá-lo de Superbusyplex.
E como ir alémn disso?

O próximo passo, é inserir a função BB(n) numa máquina de turing. Já que essa função não é computável, inseri-la no sistema de funções computáveis daria um salto bem grande. Vou definir uma coisa agora. Definimos uma máquina de Turing com função extra f(n), como uma máquina de Turing com a seguinte estrutura: tem a fita e todos os estados e tal, mais um estado extra. Esse estado, uma vez que um outro estado passe a função pra ele, terá uma sequência de 1's na fita que segue do leitor dele da esquerda pra direita. A sequência termina com o primeiro 0. A sequência começa na posição o leitor se encontra. Se a sequência começar com 0, o número associado é 0. Se começar com 1, o número associado é o número de 1's seguidos que vem a partir do leitor até o primeiro 0 após os 1's conecutivos. O que o estado extra faz é substituir a sequência de 1's com n algarismos por uma sequência com f(n) algarismos 1, sem sobrescrever o restante da fita que se encontra à direita (apenas empurrando-a para direita, ou recuando se f(n)Essa função f(n) costuma ser chamada de oráculo. Assim, definimos BB_1(n) como o maior número de 1's que uma máquina com oráculo BB(n) e n estados (exceto o estado extra) pode retornar.
BB_2(n) definido usando a mesma lógica com oráculo BB_1. E para um ordinal limite a, definimos BB_a(n)=BB_a(n)(n). Por exemplo, BB_2w(5)=BB_w+5(5)= BB de máquinas de turing com oráculo BB_w+4. E, é claro, BB_w(n)=BB_n(n).
Pensemos então no BB_CX(número de graham) com notação de sequências fundamentais da notação C de Taranovsky, o "Absurdgol". E Absurdgolplex = BB_CX(Absurdgol). Não digo que paro por aqui. Mas é quase isso. Os passos que vou dar daqui pra frente, são obscuros. Creio que BB_CX(graham) seja bem definido certinho, mas os do próximo capítulo já começa a suscitar a dúvida. Os motivos explicarei depois. Ir além desses números (sem cair no referido obscurantismo) parece muito difícil. Ainda não tive uma idéia clara, parece que não dá pra saltar além disso sem soltar uma notação avançada de ordinais. E transcender a idéia dos Busy Beaver com oráculos parece muito difícil mesmo. Teria que dar um jeito de diagonalizar esse argumento, ou criar um mecanismo que generalize isso. Máquinas de Turing de tempo infinito parece ser um caminho. Fica por enquanto pra próxima.