La diagonalització és un truc logicomatemàtic tan elegant com devastador. Tot i que va néixer per comparar la mida dels infinits, s’ha convertit en l’eina preferida per demostrar que hi ha coses que, senzillament, no es poden fer (ni en matemàtiques ni en computació).
L’origen: Georg Cantor i els infinits
A finals del segle XIX, Cantor volia demostrar que hi ha més números reals (amb decimals) que números naturals (1, 2, 3…). Per fer-ho, va utilitzar l’argument de la diagonal.
Imagina que fas una llista infinita de tots els números amb decimals entre 0 i 1. Segons Cantor, per molt llarga que sigui la llista, sempre en puc crear un de nou que no hi sigui.
Com es fa?
Escrius la teva llista de números (en binari o decimal):
Núm 1: 0,50000…
Núm 2: 0,12345…
Núm 3: 0,88912…
Núm 4: 0,00001…
Mires la diagonal (els dígits en negreta): 5290.
Crees un número nou canviant cada dígit de la diagonal:
Si el primer dígit del Núm 1 és 5, el meu serà un 6.
Si el segon dígit del Núm 2 és 2, el meu serà un 3.
Si el tercer dígit del Núm 3 és 9, el meu serà un 0.
Resultat: El número nou (0,6301…) no pot ser el primer (perquè el primer dígit és diferent), ni el segon (perquè el segon és diferent), ni cap número de la llista. Has escapat de la llista infinita.
Gödel: La diagonalització de la veritat
Gödel va aplicar aquesta lògica a les frases matemàtiques. En lloc de dígits, va utilitzar la numerització que hem vist abans per fer que una frase mirés la llista de totes les demostracions possibles.
- Va construir una frase que deia, essencialment: Jo sóc el resultat de fer una diagonal sobre totes les demostracions del sistema i canviar el resultat per ‘no demostrable’.
- Això crea un objecte que, per definició, no pot estar a la llista de coses demostrables, però que sabem que és veritat pel mateix mètode de construcció.
Turing: La diagonalització del software
Turing va fer el mateix amb els programes d’ordinador per resoldre el Problema de l’Aturada.
Suposem que tenim una llista infinita de tots els programes possibles (P1, P2, P3…).
Imagina que existeix un programa Expert (H) que ens diu si un programa s’aturarà o no.
Turing crea un programa Diagonal (D) que fa el següent:
Mira què diu l’Expert sobre el programa i quan rep l’entrada i.
Si l’Expert diu S’aturarà, el programa Diagonal entra en un bucle infinit.
Si l’Expert diu Es penjarà, el programa Diagonal s’atura immediatament.
La paradoxa: Què passa quan el programa Diagonal s’analitza a si mateix?
Si s’ha d’aturar, es penja.
Si s’ha de penjar, s’atura.
Com que hem arribat a una contradicció lògica, la conclusió és que l’Expert (el programa que ho calcula tot) no pot existir.
La diagonalització és el mètode per dir: Si em dónes un sistema de regles, jo puc construir un objecte que les teves regles no poden atrapar.
És la prova definitiva que la realitat (ja sigui numèrica, lògica o computacional) és sempre més gran que qualsevol llista o manual d’instruccions que intentem escriure. És, literalment, fer un pas al costat de la línia per veure tot el dibuix.
Enfilall
Deixa un comentari…