dijous, 5 d’agost de 2010

Quin és el número més gran que podem escriure?

Dedicat a l'Adrià Gascon.
Extret de http://www.scottaaronson.com/writings/bignumbers.html


Imaginem que participem en un concurs on, en 15 segons, hem d'escriure el número més gran que coneguem (un nombre concret, no s'hi val escriure "infinit"). Quins nombres podem escriure?

La primera idea que ens ve al cap és escriure una seqüència de nous:
999999999999999999

Però de seguida ens n'adomem que, si en comptes d'escriure nous escrivim uns, anem molt més ràpid i podem escriure moltes més xifres en el mateix temps:
11111111111111111111111

I si exponenciem? Quin número és més gran: (9^9)^9 o 9^(9^9)? El segon, així que una nova proposta és el número
9^(9^(9^(9...)))
que s'abrevia com
9^9^9^9...

Hi ha operacions més poderoses que l'exponencial? Sí, de fet l'operació exponencial forma part d'una cadena d'operacions, anomenada la seqüència d'hiperoperacions.
La hiperoperació elemental consisteix en sumar 1:
H0(a,b) = b + 1

La hiperoperació primera consisteix en sumar:
H1(a,b) = a + b

La segona és la multiplicació:
H2(a,b) = a * b

La tercera és l'exponenciació:
H3(a,b) = a ^ b

La quarta s'anomena tetració, i es defineix com:
H4(a,b) = a ^ a ^ a ^ ... ^ a (b vegades)

La fórmula general d'una hiperoperació és:
Hn(a,b) = b + 1 si n = 0
Hn(a,b) = a si n = 1, b = 0
Hn(a,b) = 0 si n = 2, b = 0
Hn(a,b) = 1 si n >= 3, b = 0
Hn(a,b) = Hn-1(a,Hn(a,b-1)) altrament

Així, pel cas de la tetració, tenim el que havíem comentat:
H4(a,b) = H3(a,H4(a,b-1)) = H3(a,H3(a,H4(a,b-2))) = ... = a ^ (a ^ ... ^ a)

Si fixem els valors de a i b al subíndex de la hiperoperació obtenim (una versió de) la seqüència d'Ackermann. Els seus primers elements en són:
A(1) = 1 + 1
A(2) = 2 * 2
A(3) = 3 ^ 3
A(4) = 4 ^ 4 ^ 4 ^ 4

i la fórmula general és:
A(n) = Hn(n,n)

que podem calcular amb la recurrència que hem presentat abans.

Una bona resposta a la pregunta que plantegem en aquest escrit és, doncs, un número ben gran de la seqüència d'Ackermann.

La funció d'Ackermann, és a dir, la funció que donat n computa A(n) té propietats que la fan especial. És una funció computable total que no és primitiva recursiva. És a dir, existeix un algorisme (un programa) que la pot computar, però que creix més ràpid que les funcions primitives recursives. Per aquest escrit en tenim prou quedant-nos amb aquesta idea, no ho detallarem més. La funció d'Ackermann mostra que, tot i que totes les funcions primitives recursives són computables, el recíproc no és cert.

Però encara hi ha nombres més grans que els de la seqüència d'Ackermann. Però necessitem utilitzar la definició de Màquina de Turing. Una funció és computable si existeix una Màquina de Turing que la calcula en un nombre finit de passos. I podem classificar les Màquines de Turing segons el nombre de regles que tenen escrites a la cinta. Llavors, fixat un nombre N de regles, hi ha un nombre finit de MT que tenen N regles, i es divideixen en dos conjunts: les que no s'aturen i les que s'aturen. D'aquestes últimes, cadascuna executarà un nombre de passos fins aturar-se. Doncs la seqüència "Busy Beaver" es defineix com:
BB(N) = max{nombre de passos abans d'aturar-se d'una MT amb N regles}

Aquests nombres són immensos: de fet se'n coneixen ben pocs:
BB(1) = 1
BB(2) = 6
BB(3) = 21
BB(4) = 107

No es coneix el valor de BB(5), tot i que se sap que és més gran de 47 milions. I pel que fa al valor de BB(6), es coneix que supera els 8.000 bilions...

Què us sembla si responem la pregunta inicial amb un nombre ben gran de la seqüència BB?