Màquines de Turing

Avui toca imaginar i pensar una mica. 
Ara farem un experiment mental, construirem una màquina molt potent. Però ho farem amb quatre coses molt senzilles: una cinta de paper molt llarga, una mena d’impressora molt senzilla per imprimir aquesta cinta, un petit escàner que podrà llegir la cinta i un petit cervell capaç de seguir ordres molt senzilles. També ens caldrà una pissarra on hi haurà escrites les ordres que haurà de seguir l’andròmina que estem muntant.
Com hem dit, aquest cervell petit caldrà que entengui unes petites ordres, que seran les següents:

• Mou la cinta cap a la dreta o l’esquerra.
• Imprimeix un símbol a la cinta.
• Llegeix el símbol de la cinta.
• Que sàpiga comparar els símbols entre ells.

Els símbols que podrem escriure a la cinta també seran pocs i senzills:

• El símbol 1
• El símbol 0
• El símbol B (cinta en blanc)

I ja en tenim prou. Amb aquests components podem fer l’ordinador que pugui fer el mateix que el més potent del món o qualsevol altre que ara mateix puguem construir. Us ho creieu? No? Ens caldrà introduir un concepte, que és l’estat de la màquina, però ho veurem millor amb un exemple.
Ara farem una cosa senzilleta: farem una màquina que sumi números. Com ho fem si només tenim dos símbols a la cinta? Doncs, hi posarem tants 1 com el valor del primer sumand separat per un 0 i a continuació altre cop tants 1 com el valor del segon sumand. Així, si volguéssim fer la suma 3 + 2, posaríem a la cinta això:

El capçal que llegeix la cinta el posarem a l’esquerra del tot, just a sobre del primer 1.

I ara, hem d’escriure les instruccions a la pissarra. Les instruccions indicaran un nom, que li direm estat; quin símbol ha d’haver-hi a la cinta, i què s’ha de fer. Vegem-ho per al cas de la cinta:

Vegem què passaria si engeguem aquesta màquina:

1. La màquina comença que està a l’estat “Inici” i el capçal de la cinta sobre l’1 de l’esquerra, per tant, estarem a la primera línia de la pissarra, que tornaria a escriure un 1 a la cinta i mouria el capçal cap a la dreta una posició.
2. Com que no ha canviat l’estat, seguirà fent això per als tres 1 que hi ha seguits. Quan arribi al 0, es complirà la segona línia de la pissarra, per tant posarà un 1 a la cinta trepitjant el 0, mourà el capçal cap a la dreta i canviarà a l’estat que es diu “Estat 1”.
3. Ara a l’estat 1, a la cinta es trobarà un 1 i per tant es complirà la tercera línia de la pissarra, que ens diu que hem d’escriure-hi un 1, moure el capçal cap a la dreta i seguir a l’estat 1. Això ho farà per als dos 1 que hi ha del segon sumand, fins que arribi a la posició on hi ha un blanc (B) i es complirà la quarta línia de la pissarra.

Què passa llavors? Que hi escriu un símbol B a la cinta, mou el capçal cap a l’esquerra i passa a estar a l’"Estat 2".
En aquest punt, la cinta de l’exemple tindrà aquest aspecte:

Què ha de fer la màquina ara? Doncs, si estant a l’"Estat 2" troba un símbol 1 a la cinta, hi ha d’escriure un blanc, no cal que faci res amb el capçal i s'atura la màquina.
El resultat a la cinta serà el següent:

Com que hem dit que representem els números amb tants 1 com el valor del nombre, la màquina ens dona el resultat correcte de 5.

Una màquina de Turing (CC BY-SA 3.0 GabrielF https://en.wikipedia.org/wiki/File:Model_of_a_Turing_machine.jpg)

Veieu la potència d’aquesta andròmina? Amb unes regles molt i molt senzilles hem pogut fer una sumadora de nombres! 
Tan sols endreçant i escrivint estats i les seves condicions podem fer un munt de màquines diferents que treballin amb nombres, que sumin, restin, multipliquin, divideixin, mirin si és un nombre parell o senar, calculin nombres primers, etc. Podem fer màquines tan complexes com vulguem, només caldrà afegir més i més estats amb les seves condicions. 

També podem afegir més símbols i més cintes i capçals però això no variarà substancialment el que pot fer la màquina sinó que tindrà a veure amb la seva velocitat o senzillesa per dissenyar nous algorismes.

A aquest tipus de màquines els diem màquines de Turing (MT) perquè va ser Alan Turing qui primer les va formalitzar i estudiar allà als anys 30 del segle XX. Turing les va fer servir per estudiar quins problemes matemàtics es poden resoldre amb ordinadors i què era un algorisme, els seus límits i característiques. 

Però tot això ho veurem en una altra entrada...