La Maquina Senzilla
TEO FRIGOLA
Qui la va inventar?
Alan M. Turing
Biografía
Alan Mathison Turing va néixer el 1912, i molt aviat en va mostrar una
extraordinària intuïció científica.
Mentre el seu pare era a Madrás, treballant per al
Indian Civil Service, Turing va guanyar nombrosos premis escolars, i
més tard una beca que el portaria al King's College de
Cambridge. Va ser aquí quan va començar a interessar-se seriosament per
els problemes de lògica matemàtica.
El 1931, el matemàtic txec Kurt Godel va descobrir que hi havia
teoremes matemàtics que eren veritables encara quan no es
poguessin provar. Davant això, Alan Turing es va posar a investigar
aquells que sí que podien ser provats. Volia intentar demostrar la
vella idea que les matemàtiques no són un art misteriós, sinó
una ciència exacta regida per regles lògiques.
Per fer-ho, va idear una màquina imaginària capaç de realitzar de
manera totalment mecànica els processos que normalment portaria
a terme un matemàtic. Hi havia una màquina per a cada procés; així,
hi havia una màquina que sumava, una altra que multiplicava, etc. Aquestes
màquines acabarien per rebre el nom de "Màquines de Turing".
Bàsicament, el que volia era fer una llista dels problemes
que una màquina seria capaç de resoldre seguint regles lògiques.
Si aquesta llista abraçava tots els problemes matemàtics, llavors
la seva tesi quedaria demostrada, i amb ella la teoria de la
computabilitat.
Que es?
Una màquina de Turing és un dispositiu que manipula símbols sobre una tira de cinta segons una taula de regles.
Una màquina de Turing que és capaç de simular qualsevol altra màquina de Turing és anomenada una màquina universal de Turing .
Com funciona?
Una màquina de Turing consisteix, bàsicament, en una cinta infinita, dividida en caselles.
Sobre aquesta cinta hi ha un dispositiu capaç de desplaçar-s'hi al llarg d'una casella cada cop.
Aquest dispositiu compta amb un capçal capaç de llegir un símbol escrit a la cinta, o d'esborrar l'existent i imprimir-ne un de nou al seu lloc.
Els símbols que defineixen l'estat del dispositiu no han de coincidir amb els símbols que es poden llegir o escriure a la cinta.
Els possibles símbols a llegir o escriure a la cinta són el 0 i l'1, i els possibles estats es representen amb lletres majúscules.
Amb aquestes dues dades accedeix a una taula, on llegeix el símbol que ha d'escriure a la cinta, el nou estat al qual ha de passar i si s'ha de desplaçar a la casella esquerra o dreta.
Suma de dos numeros
Una de les tasques més simples que pot dur a terme una màquina de Turing és la suma de dos números.
Per això hem de definir primer una convenció per representar aquests números a la cinta.
Si tenim dos números en una cinta, separats un de l'altre per un zero, la forma més fàcil de sumar-los seria convertir-ne un dels uns dels extrems en zero,
i canviar el zero de separació per un zero. D'aquesta manera tindríem una cadena formada per tants uns com indica la suma dels dos números originals.
sumem tres y cinc:
cinta inicial:
0000111011111000
posem un zero al lloc de l'u de l'esquerra:
0000011011111000
posem un u al lloc del zero de separació:
0000011111111000
el resultat: vuit uns, el numero vuit.
Modificacións de la maquina de Turing
Màquina de Turing amb moviment d'espera
La funció de transició de la MT senzilla està definida per
δ : Q × Γ → Q × Γ × { L , R } , \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\},
la qual pot ser modificada com
δ : Q × Γ → Q × Γ × { L , R , S } . \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R,S\}.
Màquina de Turing amb cinta infinita a banda i banda
Aquesta modificació es denota igual que una MT senzilla, el que la fa diferent és que la cinta és infinita tant per la dreta com per l'esquerra
Màquina de Turing amb cinta multipista
És aquella que mitjançant la qual cada cel·la de la cinta d'una màquina senzilla es divideix en subcel·les.
Cada cel·la és així capaç de contenir diversos símbols de la cinta. Per exemple, la cinta de la figura té cada
cel·la subdividida en tres subcel·les.
Es diu que aquesta cinta té múltiples pistes ja que cada cel·la d'aquesta màquina de Turing conté múltiples caràcters,
el contingut de les cel·les de la cinta pot ser representat mitjançant n-tuples ordenades. Els moviments que faci aquesta màquina
dependran del seu estat actual i de la n-tupla que representi el contingut de la cel·la actual. Cal esmentar que posseeix un sol
capçal igual que una MT senzilla.
Màquina de Turing multicinta
Una MT amb més d'una cinta consisteix en un control finit amb capçals lectors/escriptors i cintes. Cada cinta és infinita en tots dos sentits.
La MT defineix el seu moviment depenent del símbol que està llegint cadascun dels seus capçals, dóna regles de substitució per a cadascun dels símbols
i direcció de moviment per a cadascun dels capçals.
Inicialment la MT comença amb l'entrada a la primera cinta i la resta de les cintes en blanc.
Màquina de Turing multidimensional
Una MT multidimensional és aquella la cinta de la qual es pot veure com estenent-se infinitament en més d'una direcció,
l'exemple més bàsic seria el d'una màquina bidimensional la cinta de la qual s'estendria infinitament cap amunt, avall, dreta i esquerra.
D'aquesta manera, la definició dels moviments que realitza el capçal serà {L,R,U,D}.
FI
