Màquines per parlar amb extraterrestres

Us imagineu un codi, un llenguatge, una forma de descriure una màquina que fos comuna a tot l’Univers? Ens serviria per comunicar-nos entre civilitzacions diferents de la nostra i fins i tot més enllà, amb altres galàxies!
No sabem encara si n’hi ha, de civilitzacions, a altres llocs, tot i que segurament n’hi deu haver moltes, però molt molt lluny. Tampoc tenim gens clar com podran ser aquests éssers, ni com són, ni què entenen, ni com pensen. 
Però algunes coses sí que ens semblen força clares: si mai ens hi poguéssim comunicar, seria perquè tenen tecnologia. La tecnologia es basa en una física i unes matemàtiques que, segons tots els nostres indicis, són les mateixes a tot l’Univers.

I aquí és on entra el nostre protagonista, un jove matemàtic anglès, pioner de la informàtica, anomenat Alan Turing. Aquest home, a part de fer altres coses, com desxifrar els codis secrets alemanys de la Segona Guerra Mundial, va estudiar com serien els ordinadors més senzills i potents possibles, i tot amb llapis, paper i la seva imaginació. Vegem el que es va empescar:

Imaginem-nos que tenim un paper tan llarg com vulguem i que és quadriculat, de manera que a cada quadrícula hi podem escriure un símbol o lletra. A aquest paper li direm cinta i servirà per escriure-hi les dades d’entrada i les de sortida de la nostra màquina imaginària.
Imaginem també que tenim un aparell que pot llegir aquesta cinta i entendre quin símbol hi ha escrit en una quadrícula i que, així mateix, pot fer moure la cinta cap a un costat i cap a l’altre per anar llegint símbols de la cinta. També pot escriure símbols nous a la cinta o esborrar el que hi ha i escriure’n un altre. A aquesta peça de la màquina li direm capçal. 
Per últim, tenim una part de la màquina que decideix què ha de fer el capçal a cada moment, si s’ha de moure, si ha d’escriure, si ha de llegir el símbol que té al paper, etc. El que decideixi aquesta part a cada moment només dependrà del seu passat i del símbol que acabi de llegir de la cinta.
En una primera versió d’aquesta màquina, les ordres del que ha d’anar fent la màquina estan gravades d’alguna manera que impedeix que es puguin canviar. Així, podem tenir diferents màquines amb diferents programes que facin coses diferents segons el que hi tinguin gravat.
A aquesta màquina imaginària així dissenyada se li diu màquina de Turing (MT) en honor al seu inventor.

Pensem, ara, com seria una MT que multipliqués dos números. Primer, establim que a la cinta d’entrada hi posarem els dos números, i ho farem posant tants símbols X com el valor del número a multiplicar, un 0 per separar els dos números i un altre cop tantes X com calgui segons el valor del segon número.

Així, si volem multiplicar 4 per 3, escriurem això a la cinta d’entrada:

0XXXX0XXX0

i després d’uns quants passos de la màquina (més de 250!), a la cinta tindríem això:

0XXXXXXXXXXXX0

I la MT ens indicaria que ja ha acabat.

Una cosa meravellosa d’aquesta classe de màquines és que són iguals de potents, independentment de com triem de codificar la informació a la cinta: al capdavall, ve a ser el mateix codificar tot amb X i 0, amb 1 i 0 o amb els dígits del 0 al 9. També és equivalent tenir una cinta que diverses, la màquina podrà resoldre els mateixos problemes o executar els mateixos programes.

A més, Turing es va adonar que podia anar una mica més enllà, i que es podia imaginar una màquina que pogués llegir de la cinta mateixa les instruccions o el programa a executar, i tot seguit les dades a processar. D’això, actualment en diem màquina universal de Turing (UTM, en anglès). En una UTM, a la cinta hi tenim codificada, primer, la informació de com ha d’actuar la màquina a cada moment (el que en diem programa), i tot seguit, hi ha les dades a processar. Per tant, una UTM pot llegir la seva cinta i actuar com qualsevol altra MT.

Tot això acaba per assemblar-se molt a com funcionen els ordinadors actuals, i això el bo de Turing ho va pensar als anys trenta del segle XX!

I amb aquestes UTM és on apareix la màgia: podem imaginar-nos que podríem fer servir una descripció d’una UTM per enviar-la a altres civilitzacions tecnològiques i després enviar-nos mútuament diferents programes per compartir coneixement i missatges. Per poc intel·ligents que siguin i per poc que hagin desenvolupat les matemàtiques, hauran tingut un raonament similar al de Turing i tindran un concepte d’UTM molt similar al nostre.

Us imagineu d’aquí a uns anys comunicant-nos amb alguna civilització i compartint informació d’aquesta manera? Quins avenços, quina informació, quines notícies podríem rebre d’aquests nous veïns? O potser el que ens caldria és estar-nos ben callats per sempre més, no sigui que alguna civilització malèfica ens trobi i vulgui acabar amb nosaltres...

A part d’això, aquestes MT i UTM serveixen als informàtics teòrics per estudiar quins problemes es poden resoldre amb els ordinadors, siguin de la mena que siguin, inclús quàntics. Però d’això, en parlarem en una altra ocasió.

Per saber-ne més

• Màquina de Turing (Viquipèdia)
• Exemple de màquina de Turing que multiplica