TESINA

EVOLUZIONE INNATURALE

SOMMARIO

1) Introduzione 2) La macchina di Turing

3) Paradossi della macchina di Turing Reti neurali ed intelligenza artificiale

4) Emulazione VISUAL BASIC di una macchina di Turing

5) Nuova frontiera: La crittografia + macchine di Turing collegate insieme

6) I problemi della 1a gara risolti e commentati

7) I problemi della 2a gara risolti e commentati

8) I problemi della 3a gara risolti e commentati

La Macchina di Turing

Introduzione

Sebbene l'uso della macchina di Turing non sia generalmente insegnato nelle scuole, esso costituisce un sicuro riferimento ed esercizio mentale per tutti coloro che scrivono codice su computer, e che, a prescindere dal linguaggio utilizzato, devono attenersi a schemi mentali per così dire 'informatici' (comunemente chiamati 'diagrammi di flusso', che spaziano nel campo della logica nelle sue forme più contorte.

Ho avuto (fortunata) occasione di conoscere la Mdt (Macchina Di Turing), in seguito alla terza gara di informatica a Pisa, dove lo svolgimento della gara prevedeva la soluzione di più quesiti logici attraverso una versione emulata della Mdt. (della quale io stesso ho creato una versione scritta in Visual Basic)

Il primo impatto con questo meccanismo non è sicuramente uno dei più semplici, sia per la obsoleta forma di linguaggio che utilizza, sia per le limitate capacità della macchina (ma ciò solo nella pratica), sicuramente caratteristiche che non ne favoriscono lo studio tutt'oggi (una Mdt non può essere assolutamente paragonata ai nostri moderni processori), ma dopo un breve allenamento (le basi del funzionamento della Mdt sono molto semplice , come vedremo, ciò che è complicato sono gli sviluppi di queste basi) la Mdt si rivela come una potente macchina di 'logicità', ma soprattutto lo spunto reale di questioni filosofiche assai controverse.

Ciò che mi ha spinto a scrivere questo trattato su questa limitato (ma pur affascinante) 'oggetto' è che esso costituisce la base di quella dottrina azzardatamente filosofica che riguarda l'intelligenza artificiale, probabilmente uno degli aspetti più interessanti e affascinanti dell'informatica.

La macchina di Turing

'algoritmo è tutto e soltanto ciò che può essere

elaborato con un'opportuna Macchina di Turing'

Alan Turing

La Macchina Di Turing (d'ora in poi chiamata MdT) può essere considerato il primo esperimento riuscito di ricreare artificialmente gli aspetti più elementari del ragionamento umano. Essa fu creata da un matematico inglese di nome Alan Mathison Turing (1912-1954) . Una macchina semplice, una scatola nera esteticamente poco appagante, che a prima vista potrebbe destare un sorriso se si pensa agli sviluppi che la sua esistenza comporta. Infatti questa opera costituisce il punto di inizio di quelle branche della scienza che si stanno sviluppando soprattutto ultimamente, e che prendono il nome di Cibernetica e AI, ovvero Intelligenza artificiale. Le caratteristiche del pensiero umano che questa Mdt può, e riesce, ad emulare sono le più semplici: principalmente passi che chiameremo 'di scelta' ma che si rifanno, in termini informatici, all'istruzione fondamentale dell'informatica che prende il nome dell'istruzione 'IF' ovvero istruzioni per il controllo del flusso correlate con i parametri 'E' , 'O', 'NON'(in termini matematici AND, OR, NOT); nel caso della Mdt ciò avviene tra soltanto due parametri (VERO / FALSO; 1/0 ovvero tra variabili booleane)

Ecco un piccolo esempio dell'istruzione IF:

IF condizione THEN fai qualcosa (THEN in inglese significa 'ALLORA')

(vedremo più avanti che Alan Turing scelse per la sua famosa macchina il parametro NAND composto da NOT e AND dal quale discendono tutte le altre possibilità.)

Ovviamente man a mano che vengono poste condizioni di scelta (IF) e vengono posti di parametri, le opzioni possibili diventano più numerose, l'algoritmo, ovvero il procedimento matematico, fatto di vari passi, che produce un risultato, l'insieme di istruzioni che fa lavorare una macchina) si fa più tortuoso (esempio:)

IF condizione AND condizione THEN IF condizione OR NOT(parametro) AND NOT(parametro) THEN .

e quindi il ragionamento, diventa sempre più complesso, quasi simile al nostro, in alcuni casi, come vedremo più avanti, indistinguibile!

Infatti il meccanismo di una macchina di Turing è semplice, la base su cui si muove questo apparecchio è elementare: ad esempio :'riconosci il simbolo', oppure ' scrivi 1', o anche 'sposta il nastro '.

La complessità si ottiene concatenando numerose istruzioni elementari. Infatti una Mdt è in grado di risolvere qualsiasi calcolo dei più moderni calcolatori digitali.

La Mdt oggigiorno non viene più studiata, ma considerare questa macchina obsoleta, e' un errore estremamente grave: essa costituisce il principio base di tutti i nostri personal computer, che sebbene siano infarciti di processori e periferiche, e ci mostrino , con gli adeguati programmi , gradevoli immagini ed effetti, lavorano tutti scambiando uno 'zero' con un 'uno' e viceversa, e ciò avviene in una determinata zona di memoria, chiamata BIT. Ogni computer che utilizziamo è sostanzialmente una macchina di turing.

Sembra incomprensibile che una macchina possa ricreare i meccanismi del pensiero umano, ma se considerassimo un momento a come funziona il nostro ragionamento/pensiero (NON cosa e'; per quello se ne sta occupando attualmente un'altra scienza: la dialettica) vedremo che esso e' composto essenzialmente da una moltitudine di sotto-pensieri minori, che si possono classificare come semplici decisioni. Cosa e' una decisione? Una scelta, cioè un ragionamento logico e quindi una operazione. Facciamo un esempio.

Supponiamo che il nostro ragionamento mentre sfogliamo questo testo funzioni così:

Quello che ho appena mostrato non e' altro che un diagramma di flusso, che invece di essere utilizzato con un procedimento matematico è utilizzato con il nostro pensiero. Questo diagramma può benissimo essere applicato anche ad un ragionamento di tipo matematico, come la somma di due numeri, anche se in questo caso il nostro cervello conosce già questo 'algoritmo', insieme ad esempio alla sottrazione, alla divisione, al minimo comune multiplo, alla radice quadrata.ovviamente poi gli algoritmi vengono descritti esplicitamente per un computer. Questo succede perché un algoritmo che può valere per noi, non può valere ovviamente per una macchina. Ciò che per noi magari è immediato (fare la somma di due numeri, riconoscere un triangolo.o addirittura riconoscere il viso di una persona, distinguere una calligrafia da un'altra) manca ad un calcolatore. Come ho già detto una Mdt può risolvere qualsiasi calcolo, qualsiasi funzione. Ma ci sono dei problemi incomputabili, ovvero delle funzioni che non possono essere calcolate nemmeno da un personal computer. Generalmente si indica una funzione f:N -> N calcolabile quando, secondo la 'tesi di Church' (uno dei maggiori studiosi di problemi logico-matematici) la funzione viene identificata con l'esistenza di un algoritmo rappresentato teoricamente da una Mdt, in grado di calcolarne i valori per ogni n. Cioè abbiamo l'identificazione 'calcolabile = calcolabile mediante una macchina di turing'

Non mi divagherò molto su questo aspetto estremamente affascinante, per questioni di sintesi, ma vale la pena ricordare che un esempio di incomputabilità è il <problema dell'arresto> ovvero stabilire se un dato programma scritto in un qualsiasi linguaggio di programmazione, al suo avvio genererà un ciclo infinito oppure, prima o poi, si fermerà (un ciclo infinito sarebbe per esempio il calcolo del pi greco). Questo problema non può essere risolto da nessun calcolatore, semmai da un 'ipercalcolatore' (la macchina in grado di calcolare l'incomputabile, ovvero la proiezione filosofica del computer, attualmente irrealizzabile)

L'unico ipercalcolatore che si conosca oggi è il cervello umano. Ritornando alla questione ragionamento/algoritmo possiamo dedurre che tutte le nostre scelte, i nostri pensieri, sono riconducibili a schematizzazioni e a semplificazioni di tipo matematico (come ho dimostrato nel diagramma di flusso mostrato sopra). Una Mdt può essere programmata per svolgere funzioni di una complessità a dir poco preoccupante. Ovviamente non si può chiedere ad una Mdt se trova gradevole il profumo di un fiore, ma una Mdt può ingannare un uomo facendogli credere di essere una donna (o una donna credendo di essere un uomo)!

Questa parte sarà ampliata nella sezione successiva.

Il primo tentativo di creare una macchina che svolgesse delle operazioni matematiche al posto dell'uomo lo dobbiamo a Pascal ed alla sua pascalina ovvero una macchina che con una serie di ruote rappresentava i numeri. Un giro intero di una ruota (che rappresentava le unità) faceva scattare di 36 gradi un'altra ruota (che rappresentava le decine)

La Mdt che conosciamo noi oggi, e che è per noi oggetto di studio, è quella creata da Alan Matison Turing

Essa e' composta da una scatola nera (con un meccanismo interno a noi sconosciuto) e un nastro di lunghezza infinita diviso in celle che trapassa la scatola nera; è su questo nastro che la Mdt svolge le sue funzioni di scrittura e cancellatura e di spostamento, infatti il nastro può essere spostato avanti e indietro dalla Mdt. Sul nastro può essere scritta qualsiasi cosa (numeri e lettere), ovviamente ogni simbolo occupa una e una sola cella. Ma la Mdt ha una particolarità che spiegherò tra poco: essa svolge le sue funzioni in STATI.

Come viene programmata una Mdt??? Semplicemente attraverso una serie di 'Quadratiche' ovvero delle celle di simboli a gruppi di 4, insomma un array (x,y) con estensione [4,y] (y varia da 0 a +infinito)

Un esempio di quadratica può essere :0 A 1 B. Come viene letta questa quaterna di simboli? Le posizioni dispari , ovvero la 1 e la terza, servono a gestire lo stato della Mdt, che ripeto, varia da un intervallo compreso tra 0 e 36 (come poi vedremo a livello di emulazione gli stati potranno essere di gran lunga aumentati). Ma a cosa servono gli stati? Ogni istruzione viene definita in uno stato e non puo' essere cambiata. Lo 'stato' della Mdt è un componente estremamente importante: infatti le Mdt sono macchine a memoria finita ma estendibile illimitatamente. Come? Grazie agli stati: infatti una Mdt può essere programmata a svolgere determinate istruzioni se si trova in un determinato stato, le istruzioni definite in uno stato non valgono per gli altri stati. E' come se utilizzassimo più Mdt insieme, solamente che invece di utilizzare ad esempio 2 Mdt utilizzo 2 stati in una Mdt. In termini informatici uno stato può essere paragonato ad un flag ovvero ogni volta che si verifica una condizione (di cambiamento di direzione, di scelta ) viene impostato il flag e cambiato stato. Cambiando stato si possono ottenere un maggior numero di istruzioni e riutilizzare codice già scritto in precedenza in modo da processare codice già scritto semplicemente ritornando ad uno stato precedente nel quale erano state assegnate precise istruzioni.

In tal modo si possono creare dei cicli INFINITI con soltanto 2 istruzioni! Le posizioni pari invece (la 2a e la 4a) indicano istruzioni di lettura ed i scrittura. Nel caso sopra descritto della quadratica 0 A 1 B la mdt si comporta in questo modo: SE (condizione) ti trovi nello stato 0 e Mdt legge sulla cella il simbolo A allora passa allo stato 1 e scrivi al posto della A il simbolo B. Messa in questo modo la Mdt eseguirà una sola operazione se noi invece ponessimo come seconda istruzione 1 B 0 > avremmo creato un ciclo ricorsivo della mdt. Perché? Cosa succede? Se noi dessimo in entrata (in INPUT) alla Mdt una successione determinata di A il codice in questione la trasformerebbe in una successione di B. Ora spiegherò come. Il simbolo '>' significa propriamente 'avanza di una cella' (non esistono salti nella Mdt!); ipotizziamo una stringa composta da 3 'A' ad esempio (Il Simbolo 'V' sopra le celle significa in che posizione e' la Mdt):

ESEMPIO 1.1

V

A A A Stato: 0

Seguendo la prima istruzione la Mdt riconoscerebbe che il primo simbolo e' una A, quindi passerebbe allo stato 1 e scriverebbe al posto della A una B come segue:

V

B A A Stato: 1

In che condizione si trova adesso??? La Mdt è nello stato 1 e trova sul nastro una B. Ha istruzioni per questa condizione??? Si! Ovvero la seconda 1 B 0 > che le impone che in questa condizione avanzi di una cella e ritorni allo stato 0. Ecco come appare in questo momento la Mdt:

V

B A A Stato: 0

La macchina si trova di nuovo nella condizione stato 0 e simbolo A. Ci sono istruzioni per questa condizione? La risposta, anche in questo caso, e' affermativa: e' la prima, quella che ha generato la condizione per la seconda, che ha generato la condizione per la prima , che a sua volta...ecc.

E facile immaginare gli sviluppi futuri di un tal progetto; ecco, per coloro che non avessero abbastanza fantasia, il risultato finale:

V

B B B Stato: O

Cosa e' successo? Alla fine del nastro non c'e' alcun simbolo.e quindi la Mdt non avendo istruzioni per questa condizione si e' fermata, ma era quello che volevamo! Avremmo potuto porre benissimo un' istruzione per questa condizione, ad esempio 0 - 3 U, (il simbolo '-' sta a significare il vuoto) essa trovandosi nello lo stato 0 e trovando niente sul nastro passerebbe allo stato 3 e scriverebbe una 'U' in fondo al nastro INDIPENDENTEMENTE alla lunghezza del nastro. Ecco alcuni esempi di uscita:

BU

BBU

BBBBBBBBBBBBBBBBBBBU

U

E' facile immaginare come in quest'ultimo caso la Mdt sia passata subito all' ultima istruzione , mancando le 'B' che generavano le istruzioni precedenti.Ovviamente la Mdt con questo codice e' stata programmata solamente per riconoscere i simboli A e B e - (ovvero cella vuota), altri simboli come altre lettere o altri numeri genererebbero un errore e quindi l'arresto inevitabile della Mdt, se non si aggiungessero altre istruzioni: ovvero non esistono simboli universali o standard e la Mdt non si inventa nulla, essa fa solo ciò gli e' espressamente programmato (come qualsiasi computer del resto).

Ora che abbiamo imparato a programmare una Mdt guardiamo qualche applicazione filosofica della stessa.

Paradossi della Macchina di Turing : L'Intelligenza artificiale

Una profonda questione controversa e filosofica si è affacciata agli albori del progetto di Turing.

Una domanda che si è posta da quando sono nati i primi calcolatori. Date le premesse che qualsiasi pensiero logico può essere ricondotto ad un'operazione matematica , può una macchina pensare? (d'altronde la logica è una branca della matematica) . Molte disquisizioni sono nate intorno a questa domanda (spesso molto confuse). Ecco la mia interpretazione. Come ho dimostrato prima il pensiero può essere considerato un insieme di operazioni logico matematiche. Ma anche l'algoritmo è un insieme di istruzioni matematiche, quindi il nostro ragionamento non è altro che la proiezione naturale dell'algoritmo. Ne consegue, per proprietà commutativa, che l'algoritmo è un ragionamento. Ma le macchine funzionano ad algoritmi. Quindi le macchine ragionano. La mia risposta a questo sillogismo è NO. Le macchine NON pensano. Perché ritengo come prerequisito essenziale per affermare la facoltà di pensiero che ci debba essere

1) la consapevolezza della propria capacità di pensiero o esistenza, ciò che manca nel modo più assoluto ad una macchina. Ma d'altronde qualcuno potrebbe obbiettare che neppure un mollusco ha coscienza di sé stesso. Ma nessuno ha ancora dimostrato che i molluschi pensino. (a cosa poi?)

2) la capacità di divergenza, caratteristica del cervello umano, ovvero la capacità di potersi adattare a qualsiasi condizione. Matematicamente se una macchina non è programmata per una condizione, cioè manca nel codice una IF corrispondente alla condizione A la macchina non può sviluppare il 'THEN' seguente se si verifica la condizione A. Mentre il cervello umano è capace di adattarsi a qualsiasi condizione.

Nel 1950 apparve su una rivista inglese di filosofia intitolata 'MIND' l'articolo di Turing 'Computing machinery and intelligence' dove si poneva la seguente questione: 'Può una macchina pensare?' Turing, considerando una simile domanda troppo vaga, suggerì di sostituirla con questa: 'Si può insegnare ad una macchina a vincere il 'Test di imitazione' (oggi chiamato 'Test di Turing')? '

Questo test è basato su un gioco di società: Un uomo e una donna si rinchiudono ciascuno in una rispettiva stanza e un'altra persona (uomo o donna) al di fuori di queste stanze deve rivolgere delle domande a queste due persone nascoste in modo da stabilire chi sia l'uomo e chi sia la donna (le risposte vengono consegnate in maniera dattiloscritta), ovviamente sia l'uomo che la donna cercheranno di convincere l'interlocutore di essere , diciamo, la donna. L'interrogatore vince se in un certo tot di domande e in base alle risposte riesce a stabilire la verità.

'Supponiamo', dice Turing,' di sostituire uno dei giocatori nascosti con una macchina che apprende, alla quale sia stato insegnato ad esprimersi in inglese' E' possibile per una simile macchina riuscire ad ingannare l'interrogatore, quando sia la macchina che l'altro interrogato cerchino di convincere l'interrogatore ad essere umani? Attualmente nessun calcolatore riesce a superare il 'Test di Turing'

o meglio, ci riesce solo se gli sono concesse poche domande, oppure se l'interlocutore è un bambino.

Ma ovviamente le macchine parlanti potrebbero migliorare gradualmente fino ad arrivare ad un punto che solo ci vorranno domande sempre più intelligenti e dialoghi sempre più lunghi per battere la macchina.

Turing stesso scrisse nel '39 che entro il duemila i calcolatori parleranno inglese in modo da ingannare l'interlocutore per circa il 30% delle volte, dopo 5 minuti di dialogo. Ecco una sua conversazione immaginata tra una persona e un calcolatore del 2000:

Domanda: Scrivimi un sonetto su Forth Bridge

Risposta: Lascia perdere, non sono mai stato bravo a scrivere sonetti.

D: Addiziona 34957 e 70764

R: (pausa di circa 30 secondi) 105621

D: sai giocare a scacchi?

R: Si

D: Bene: ho il re e1 e nessun altro pezzo. Tu hai solo il re in e3 e la torre in h8. Tocca a te muovere. Cosa fai?

R. (pausa di 15 secondi) h8-h1. Matto.

Ora noi alle soglie del 2000 cose del genere non le abbiamo ancora viste, anche se bisogna ammettere che grossi passi sono stati portati avanti soprattutto nello sviluppo di reti neurali. L'evoluzione dell'intelligenza artificiale non è affatto ad un punto morto, anzi, è stato recentemente sperimentato anche con successo (e ciò provoca un certo turbamento) le prime connessioni biologia-tecnologia ovvero proteine organiche che lavorano con i circuiti elettrici. Probabilmente non siamo tanto lontani dal computer che avrà coscienza di sé stesso.

Comunque esistono parecchi programmi che consentono di emulare una conversazione. Ad esempio il seguente dialogo (comparso nel New York Times il 5 giugno del 1968) riproduce un dialogo tra una donna e un calcolatore con caricato un programma di nome ELISA, in veste di psicanalista.

Donna: Gli uomini sono tutti uguali

Calcolatore: Perché ?

D: Ci seccano sempre per un motivo o per l'altro

C: Puoi darmi un esempio specifico?

D: Bèh, il mio amico ha insistito perché venissi da lei

C: Il suo amico ha insistito?

D: Si, dice che sono depressa

C: Mi spiace sentire che lei è depressa

D: E' vero sono infelice

C: Crede che venendo da me troverà un aiuto?

D: Ho bisogno di aiuto certo

C: che specie di aiuto cerca?

D: Forse dovrei imparare ad andare d'accordo con mia madre.

C: Mi dica qualcosa di piu' sulla sua famiglia.

D: Mia madre si occupa di me

C: Chi altro si occupa di lei in famiglia

D: Mio padre

C: Suo padre?

D: Lei è un po' come mio padre in un certo senso

C: che somiglianze trova?

D: Lei non è molto aggressivo, ma credo che non voglia farmelo notare.

C: Cosa le fa pensare che io non sia molto aggressivo?

D: Bè, non mi contraddice

Diciamo che leggendo questo dialogo, ci fa piacere essere ingannati. Effettivamente la conversazione sembra quella di un paziente e di uno psicanalista. Probabilmente la ricerca produrrà macchine in grado di creare algoritmi che simulino perfettamente il nostro pensiero, riuscendo a ingannarci benissimo. In proposito all'emulazione sono d'accordo che arriveremo ad un punto tale, ma noi non conosciamo neppure come funzioni il nostro cervello, figuriamoci di illuderci di riprodurlo attraverso algoritmi. L'intelligenza artificiale non esiste. La macchina si limita a svolgere quello che gli è stato ordinato di fare: sia di scrivere che di parlare. Come dimostrazione ho provato io a dialogare con Elisa. Ecco il mio dialogo:

Gianluigi. Le macchine non pensano.

Calcolatore: Sei dispiaciuto perché le macchine non pensino?

G: No, ritengo solamente che tu non possa pensare come faccio io

C: oh, io non posso pensare come te?

G: Già.prova a dimostrarmi il contrario.

C: Che cosa significa per te?

G: se tu riesci a dimostrarmi che tu puoi pensare allora io crederò che tu possa pensare

C: Qualcuno ti ha detto che io posso pensare?

G: No, nessuno mi ha detto che tu possa pensare

C: Nessuno?

G: Nessuno.

C: Che cosa significa per te?

G: Che tu non potrai mai pensare

C: Tu non stai realmente parlando di me vero?

G: Sbagliato. Io sto parlando di te

C: Da quanto tempo stai parlando di me?

G: Dall'inizio della conversazione

C: Vai avanti.

G: Tu puoi pensare?

C: Forse ti piacerebbe essere abile di pensare

G: Io ho la capacità di pensare (.almeno credo!)

C: Sei venuto da me perché hai la capacità di pensare?

G: Sono venuto da te per vedere se tu hai la capacità di pensare.

C: Oh, io ho la capacità di pensare?

G: Sei te che devi rispondere a questa domanda

C: Forse nelle tue fantasie io devo rispondere a questa domanda

G: Per favore rispondi alla mia domanda.

C: La tua domanda (NB: Sono riuscito a metterlo in crisi!)

G: Rispondi stupida macchina!

C: Le macchine ti fanno arrabbiare?

Alla fine avevo perso abbastanza la pazienza dato che le risposte date da Elisa non esauriscono mai la domanda ma ci girano sempre intorno. Ho provato pure a chiederle perché non rispondeva direttamente alle mie domande, ma mi ha risposto con un'altra domanda: 'che differenza fa per te se non rispondo direttamente alle tue domande?' Il dialogo potrebbe continuare fino all'infinito.e Elisa non capirebbe nulla di quanto dialogato.

Un dialogo sull'intelligenza dei computer ha la stessa valenza per Elisa quanto una conversazione sui datteri caramellati. Un simile programma non potrebbe certamente superare il test di Turing.

Supponiamo pero' che dopo dei calcolatori riescano a superare il test di Turing. Questo cosa spiegherebbe dal punto di vista filosofico?

La macchina se riuscisse a risponderci correttamente si avvarrebbe della proprietà di pensante? Probabilmente per la maggior parte delle persone sì, ma in realtà è solo una macchina inerte costruita per imitare una persona. Probabilmente in futuro vedremo Robot in grado di condurre uno show televisivo nella quale memoria siano state caricate migliaia di barzellette e in grado di far divertire il pubblico. Ma ciò non vuol dire che il robot abbia la capacità di pensare. E comunque anche una persona che sia battuta da un computer nel gioco degli scacchi non può ritenere che il computer abbia vinto perché sia più intelligente di lui. Ci sorprende notare che in certi casi, come nel gioco degli scacchi, bisogna programmare un computer non per innalzarlo alla abilità dell'uomo, ma per diminuire la sua 'invincibilità' fino a livelli umani!

Un computer programmato a giocare a scacchi, può benissimo calcolare tutte le migliaia di combinazioni possibili e scegliere quella che gli dà maggior probabilità di vittoria. Un uomo, una cosa del genere non può ovviamente farla. D'altronde bisogna considerare un altro punto della questione. Se consideriamo i progressi fatti dalle macchine (o meglio che l'uomo ha fatto fare alle macchine) durante gli ultimi cento anni, e notiamo invece quanto hanno progredito lentamente regno animale e vegetale, notiamo che le macchine più organizzate non sono tanto creature di oggi, quanto degli ultimi secondi in confronto alla lenta evoluzione naturale. Ovviamente la risposta alla domanda a cosa ci riserva il futuro è un 'algoritmo' che non potrà mai essere calcolato da alcun calcolatore.

Emulazione della Macchina di Turing in Visual Basic

Devo ammetterlo, non e' stato facile. Nonostante l'enorme potenzialità che offre questo linguaggio, ero impedito dal continuo numero di variabili che non funzionano se non erano dichiarate esplicitamente. eppure il pregio del linguaggio BASIC, nelle versioni più vecchie, era proprio questo, che le variabili non dovevano essere dichiarate! Perchè gli hanno tolto questo pregio (insieme alla cortocircuitazione delle espressioni logiche)? Ma tralasciamo i rimpianti e passiamo all'analisi della struttura portante del mio programma.

If b(1, k) = 'Alt' Then flag = True

If (Val(b(1, k)) = Val(sta)) Then

If (LCase(b(2, k)) = LCase(a(i))) Or (b(2, k) = '-' And (a(i) = '' Or a(i) = '-')) Then

sta = b(3, k)

If b(4, k) = '<' Then i = i - 1

If b(4, k) = '>' Then i = i + 1

If b(4, k) = '-' Then a(i) = ' '

If (b(4, k) <> '<') And (b(4, k) <> '>') And (b(4, k) <> '-') Then

a(i) = b(4, k)

End If

Else

k = 0

End If

End If

k = k + 1

Questo codice (che ho scritto io), non e' complicato come può sembrare a prima vista. Le quadratiche che compongono il codice della Mdt l'ho rinchiuso in una matrice chiamata 'B' e di estensione 4 per k. (Il massimo valore di k e' 10000) . Cosi' la prima istruzione viene rinchiusa in B(1,k) la seconda in B(2.k) la terza in B(3,k) la quarta in B(4,k). E alla fine della matrice ho posto un bell' 'ALT'. Il numero dello stato l'ho definito con la variabile STA, e invece la posizione corrente del nastro l'ho definita con 'i', mentre l'oggetto presente alla posizione i l'ho inserito in una matrice A(i) (che si legge 'matrice A in indice-ordine i') Questa parte del programma viene ripetuta per un numero estremamente elevato, in pratica questo codice controlla l'istruzione numero K, e avanza sempre in K=K+1 finche' non trova l'istruzione giusta. Appena arriva ad B(1,k)='Alt' allora il programma si ferma dato che non ha trovato più istruzioni per continuare il programma. Rammento inoltre che in una MDT non si limita a svolgere istruzione in modo sequenziale, ma o in modo RICORSIVO, cioè funzioni che richiamano sé stesse, o processando codice scritto, cioè riutilizzando codice già utilizzato non appena ne capita la condizione.

Analizziamo più in profondità. (Val e Lcase sono istruzioni di conversione, nel flusso dell'algoritmo hanno poca importanza)

If (Val(b(1, k)) = Val(sta))

'SE nella matrice B(1,k) compare il numero corrispondente alla variabile STA (che rappresenta lo stato)'

then 'ALLORA' fai un altro controllo, ovvero:

If (LCase(b(2, k)) = LCase(a(i)))

'SE nella matrice B(2,k) compare il simbolo corrispondente a quello momentaneamente caricato dal nastro (rappresentato come un' Array chiamato 'a' di indice i e di estensione 10000)'

Or (b(2, k) = '-' And (a(i) = '' Or a(i) = '-')) Then

'OPPURE SE nella matrice B(2,k) compare il simbolo '-' E CONTEMPORANEAMENTE O il simbolo caricato dal nastro è nullo cioè c'è uno spazio vuoto nel nastro O il simbolo caricato dal nastro equivale a '-' (che significa la stessa cosa di prima, cioè che il nastro presenta uno spazio vuoto. Questa istruzione poteva anche essere omessa, ma per sicurezza, in quanto lo spazio vuoto viene rappresentato con due simboli (che vengono confusi in fase di debug) ho preferito lasciarla) ALLORA'

sta = b(3, k)

' il numero corrispondente alla variabile STA (che rappresenta lo stato) diventa uguale alla matrice B(3,k) (lo stato viene cambiato)'

--- Ed ora diamo via alle istruzioni di movimento o di scrittura

If b(4, k) = '<' Then i = i - 1

If b(4, k) = '>' Then i = i + 1

If b(4, k) = '-' Then a(i) = ' '

'SE nella matrice B(4,k) compare il simbolo '<' allora sposta il nastro verso destra (ricordo che i è l'indice dell'array del nastro che viene aggiornato sul nastro da un timer con una frequenza di 100 hz )'

'SE nella matrice B(4,k) compare il simbolo '>' allora sposta il nastro verso sinistra'

'SE nella matrice B(4,k) compare il simbolo '-' allora il simbolo sul nastro viene cancellato'

If (b(4, k) <> '<') And (b(4, k) <> '>') And (b(4, k) <> '-') Then

'SE nella matrice B(4,k) non compare nè simbolo '<', né il simbolo '>', né il simbolo '-' (cioè non è soddisfatta alcuna delle condizioni precedenti)'

a(i) = b(4, k)

'ALLORA nel nastro viene scritto il simbolo sconosciuto che compare nella B(4,k)'

(i successivi 'End if 'servono a chiudere le condizioni 'IF')

ELSE (altrimenti)

k = 0

Reimposto l'indice della matrice b(,k) a 0 in modo che ogni qualvolta che si sia verificata una condizione, cosi' è possibile ricontrollare tutte le condizioni in modo da non perderne alcuna.

Nuova frontiera: La crittografia + macchine di turing collegate insieme

Un uso molto interessante della Mdt è l'estensione della sua funzionalità nel campo della crittografia.

Perché la crittografia? Sappiamo che Alan Turing durante la seconda guerra mondiale prestò la sua opera nel dipartimento di comunicazioni del ministero degli esteri britannico, e si dice che egli ebbe un ruolo chiave nella decifrazione del codice tedesco Enigma: un' operazione segreta che , a secondo alcuni storici, contribui' ad abbreviare di due anni il corso del conflitto.

Molto interessante è infatti riuscire a creare un nuovo tipo di crittografia che venga letto solo dalla Mdt, ma che in realtà contiene un significato nascosto che deve essere opportunamente decifrato. Inutile aggiungere che la crittografia ha avuto un ampio sviluppo nell' ambito della seconda guerra mondiale

Il meccanismo è semplice: Ad ogni lettera cella frase che si inserisce dobbiamo dire alla mdt di inserire un carattere corrispondente, in modo da creare un messaggio incomprensibile per noi!

Ad esempio poniamo un tipo di codice segreto:

a=m b=q

c=h d=z

e=f f=a

g=u h=s

i=t l=b

m=v n=c

o=r p=d

q=p r=e

s=o t=g

u=n v=d

z=l ' '=0 (spazio vuoto)

e' evidente che le combinazioni sono infinite..(un altro possibile meccanismo potrebbe essere quello di scambiare posto alle lettere.) ovviamente faremo finire la frase con un bel punto '.' per evitare qualsiasi problema. Ecco il listato.

0 a 1 m

0 b 1 q

0 c 1 h

0 d 1 z

0 e 1 f

0 f 1 a

0 g 1 u

0 h 1 s

0 i 1 t

0 k 1 y

0 l 1 b

0 m 1 v

0 n 1 c

0 o 1 r

0 p 1 d

0 q 1 p

0 r 1 e

0 s 1 o

0 t 1 g

0 u 1 n

0 v 1 i

0 w 1 k

0 z 1 l

1 a 0 >

1 b 0 >

1 c 0 >

1 d 0 >

1 e 0 >

1 f 0 >

1 g 0 >

1 h 0 >

1 i 0 >

1 k 0 >

1 l 0 >

1 m 0 >

1 n 0 >

1 o 0 >

1 p 0 >

1 q 0 >

1 r 0 >

1 s 0 >

1 t 0 >

1 u 0 >

1 v 0 >

1 y 0 >

1 w 0 >

1 z 0 >

1 0 0 >

Con un programma del genere potremmo avere una cosa cosi':

'Penso che questa tesina sia stupenda'

Diventa:

'dfcor0hsf0pnfogm0gfotcm0otm0ogndfczm.' Totalmente Incomprensibile!!!

Per DECRIPTARE invece utilizziamo questo codice:

0 m 1 a

0 q 1 b

0 h 1 c

0 z 1 d

0 f 1 e

0 a 1 f

0 u 1 g

0 s 1 h

0 t 1 i

0 y 1 k

0 k 1 w

0 b 1 l

0 v 1 m

0 c 1 n

0 r 1 o

0 d 1 p

0 p 1 q

0 e 1 r

0 o 1 s

0 g 1 t

0 n 1 u

0 i 1 v

0 l 1 z

1 a 0 >

1 b 0 >

1 c 0 >

1 d 0 >

1 e 0 >

1 f 0 >

1 g 0 >

1 h 0 >

1 i 0 >

1 l 0 >

1 m 0 >

1 n 0 >

1 o 0 >

1 p 0 >

1 q 0 >

1 r 0 >

1 s 0 >

1 t 0 >

1 u 0 >

1 v 0 >

1 y 0 >

1 z 0 >

1 w 0 >

1 - 0 >

E' molto interessante adesso prendere in considerazione un nuovo aspetto dell'uso di questa Mdt, cioè usarne più di una contemporaneamente ( magari sullo stesso nastro). Il ragionamento è semplice:

attivare 2 mdt e poi usarne una per Criptare il nastro e l'altra invece per de-criptare lo stesso .O se vogliamo scendere nel complicato, se il codice presenta 2 livelli di criptazione (uno cambia i simboli, l'altra le posizioni degli stessi) possiamo utilizzare più Mdt in serie per risparmiare una quantità di tempo notevole, ma non solo, anche per scrivere codice più semplice che nell'insieme delle sue funzioni e' più complesso..

Insomma anche in questo caso le possibilità sono infinite!

I problemi della 1° gara risolti e commentati

Programmare una Mdt che, dato un nastro iniziale contenente la sua rappresentazione decimale di un numero intero positivo n (diverso da 0) , termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n X 100

Nastro Iniziale  Nastro Finale

43100

Questo problema è molto semplice.in quanto non c'è alcun bisogno di far calcolare alla Mdt 100 moltiplicazioni, infatti il numero in entrata nel nastro è un numero positivo N, quindi basterà aggiungere alla fine del nastro 2 zeri..più semplice di cosi'..

Ci imbattiamo subito in una limitazione della Mdt. Il problema richiede che venga riconosciuto qualsiasi numero decimale.quindi bisogna dare necessariamente condizioni per tutti i numeri.

0 1 0 > Va avanti per qualsiasi numero

0 2 0 > Tipica istruzione di 'scorrimento'.

0 3 0 >

0 4 0 >

0 5 0 >

0 6 0 >

0 7 0 >

0 8 0 >

0 9 0 >

0 - 1 0 Quando arriva alla fine del numero passa allo stato 1, e scrive il primo '0'

1 0 2 > Va avanti di una cella.

2 - 2 0 Scrive il secondo '0'

Programmare una Mdt che , dato un nastro iniziale contenente una sequenza di A e di B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene una B, una sola F altrimenti.

Problema abbastanza banale e noioso rispetto a tutti quelli che incontreremo più avanti. Lo schema comunque è semplice : si tratta di fare un algoritmo di scorrimento per le A, e nel caso ci siano solo quelle cancella tutto e scrive F. Nel caso incontri una B (ma anche di più), cancella tutto e scrive T

Esempi:

Nastro Iniziale  Nastro Finale

BABBAB

B

AAA

T

T

F

0 A 0 > Inizia l'istruzione di scorrimento per le A

0 - 2 < Nel caso il nastro finisca e la Mdt è ancora allo stato 0 passa allo stato 2

2 A 3 - Allo stato 2 inizia l'algoritmo di cancellazione per A (B non era necessario metterla)

3 - 2 <

2 - 2 F e scrive un bel F (false)

0 B 4 > Nel caso che trovi una B allora il discorso cambia: Passa immediatamente allo stato 4

4 A 4 > Ormai se ci sono A

4 B 4 > oppure se ci sono B non ci interessa più

4 - 5 < e difatti finito il nastro torna indietro per cancellare tutto

5 A 6 - (tipica procedura per cancellarela incontreremo spesso!)

5 B 6 -

6 - 5 <

5 - 5 T E scrivere una T

Programmare una Mdt che dato un nastro iniziale contenente una sequenza serie di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra. Se la sequenza iniziale è composta da tutte cifre 0 , la macchina deve lasciare sul nastro un solo 0

Nastro Iniziale  Nastro Finale

431

0 0 1 - Controlla se nella cella c'è uno 0 se in caso affermativo lo cancella e passa allo stato 1

1 - 0 > Fatto ciò ritorna allo stato 0 e va avanti per cercare se c'è un' altro 0

0 - 2 0 Nel caso che il nastro sia vuoto passa allo stato 2 e lo zero lo scrive lui.

Una sequenza si dice palindroma se la lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra. Programmare una Mdt che, dato un nastro iniziale contenente una sequenza di A e di B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è palindroma,

la sola sequenza NO altrimenti.

Qui iniziamo a trovare qualcosa di più interessante. Per scoprire se una sequenza è palindroma basta controllare rispettivamente il primo e l'ultimo simbolo del nastro. Se sono uguali allora li cancelliamo e riniziamo tutto d'accapo, fino a cancellare tutto il nastro. In questo caso scriviamo SI

Nastro Iniziale  Nastro Finale

ABABA

ABBA

BABBA

SI

SI

NO

0 A 1 - Controlla la prima casella. Se c'è una A passa allo stato 1 e la cancella

0 B 5 - se invece c'è una B passa allo stato 5 e la cancella

1 - 2 > Adesso nello stato 2 deve giungere in fondo al nastro per scoprire se c'è una A

2 A 2 > Va avanti..

2 B 2 >

2 - 3 < Fine nastro! Torna indietro di una cella.

3 A 3 - Se c'è una A allora questa condizione per l'attributo di palindromia è stata verificata.

3 B 7 B Se c'è una B allora la sequenza non può essere palindroma. Passa allo stato 7

3 - 4 < Nel caso che ci fosse una A ritorna all'inizio del nastro per ricominciare il controllo da 0

4 A 4 <

4 B 4 <

4 - 0 > Ritorna d'accapo però con 2 simboli cancellati

5 - 6 > In pratica fa tutto il procedimento di prima però cercando una B

6 A 6 > Va avanti

6 B 6 >

6 - 11 < fino alla fine del nastro.

11 A 7 A Trova una A, la condizione di palindromia non si è verificata. Passa allo stato 7

11 B 11 - Qui va tutto bene invece, cancella il nastro.

11 - 12 <

12 A 12 <

12 B 12 <

12 - 0 > E ritorna allo stato 0 per ricominciare d'accapo

7 B 8 - Se si è arrivati qui vuol dire che la condizione non si è verificata.cancelliamo tutto

7 A 8 -

8 - 7 <

7 - 9 N E scriviamo NO

9 N 10 >

10 - 10 O

0 - 13 S Nel caso non trovi nulla (cioè il nastro è stato cancellato tutto dal controllo) passa

13 S 14 > allo stato 13 e scrive SI

14 - 14 I

Indichiamo con A^n B^m una sequenza del tipo

A..A } n volte

B..B } m volte

Programmare una Mdt che, dato un nastro iniziale contenente una sequenza del tipo A^nB^m , con n>0 e m>0 , termina la sua esecuzione lasciando sul nastro una sola A se n>m, una sola B se m>n, una sola C se n=m

Esempi:

Nastro Iniziale  Nastro Finale

AAAABB

AAABBBBB

AAABBB

A

B

C

Questo problema si può risolvere in modo simile al precedente..cancello in ogni ciclo una A per ogni B, finchè non rimane una stringa o di sole A o di sole B, elimino quelle in eccesso, ed il gioco è fatto.

Nel caso invece che il nastro rimanga vuoto, vuol dire che il numero di A era equivalente a quello delle B.in quel caso , come richiesto dal problema, scrivo una C

0 A 1 A Controllo se nella prima casella c'è una A e passo allo stato 1

0 B 6 - Se si verifica questa condizione, vuol dire che le B prevalevano sulle A.Passo allo stato 6

1 A 1 > Fatto ciò vado in fondo al nastro con un algoritmo di scorrimento

1 B 1 >

1 - 2 < Torno indietro di una casella

2 B 2 - Se c'è una B la cancello

2 A 9 - Se si verifica questa condizione vuol dire che le A prevalevano sulle B. Passo allo stato 9

2 - 3 < Ritorno indietro

3 A 3 <

3 B 3 <

3 - 4 >

4 A 4 - Fino all'inizio del nastro e ricomincio d'accapo.

4 - 0 >

6 - 7 > C'è maggioranza di B! cancello tutto e scrivo una B come richiesto

7 B 6 -

7 - 8 B

0 - 0 C Le A e B si equivalgono..scrivo una C come richiesto

9 - 10 < Le a prevalgono. Scrivo una A come richiesto dal problema

10 A 9 -

10 - 11 A

Indichiamo con S e T due generiche sequenze formate da A e B. programmare una Mdt che, dato un nastro iniziale contenente una sequenza del tipo SCTC termina la sua esecuzione lasciando sul nastro la sequenza SI se S e T sono uguali, la sequenza NO altrimenti.

Esempi:

Nastro Iniziale  Nastro Finale

ABACABAC

BBBCBBBC

BABACBBAC

SI

SI

NO

Questo problema è molto interessante, io l'ho risolto in questo modo: in pratica controllo le lettere di ogni serie scandite dalle C partendo dalle ultime lettere. In questo modo, se vedo che le lettere sono uguali le rimpiazzo con il simbolo E. Alla fine se tutto va bene, cioè se le due sequenza formate da A e B sono uguali mi risulta fuori un nastro composto così EEECEEEC (salute!). Se ciò accade, cancello tutto e scrivo SI

0 A 0 > Scorro tutte le A e le B

0 B 0 >

0 C 1 < Fino a raggiungere la C e torno indietro.

1 E 1 <

1 A 2 E Nel caso trovassi una A scrivo al suo posto una E

2 E 2 > E nello stato 2 vado avanti.

2 C 3 > Fino a raggiungere la C e passare oltre

3 A 3 > senza curarmi né delle A

3 B 3 > che delle B,

3 E 3 > (e delle eventuali E che posso aver scritto)

3 C 4 < Fino a giungere alla C della seconda sequenza.

4 E 4 < Quindi torno indietro,

4 A 5 E e appena trovo la A , cioè quella corrispondente alla prima sequenza, passo allo stato 5 e scrivo E

4 B 14 B nel caso ci fosse una B invece, le sequenze non sono uguali.quindi passo allo stato 14

5 E 5 < Nello stato 5 invece vado indietro

5 A 5 <

5 B 5 <

5 C 0 C fino a giungere alla C della prima sequenza, in questo modo passo allo stato 0 e ricomincio

1 B 6 E Stesso procedimento..solo che in questo caso devo controllare l'esistenza della B

6 E 6 >

6 C 7 >

7 A 7 >

7 B 7 >

7 E 7 >

7 C 8 <

8 E 8 <

8 B 9 E

8 A 14 A

9 E 9 <

9 A 9 <

9 B 9 <

9 C 0 C

1 - 10 > Se si verifica questa condizione (cioè stato 1 con cella vuota) significa che le due sequenze sono uguali..passo allo stato 10 e inizio a cancellare tutto, per scrivere SI

10 E 11 - Cancello sia le E,

10 C 11 - che le C,

11 - 10 > e infine scrivo SI

10 - 12 S

12 S 13 >

13 - 13 I

14 A 14 < Se sono nello stato 14 allora significa che le due sequenze non sono uguali.

14 B 14 < Quindi per qualsiasi simbolo sul nastro torno indietro fino all'inizio

14 C 14 <

14 E 14 <

14 - 15 > In modo che adesso qualsiasi simbolo che ci sia sul nastro lo cancello

15 A 16 - (cancello le A,B,C,E)

15 B 16 -

15 C 16 -

15 E 16 -

16 - 15 > per poi scrivere NO

15 - 17 N

17 N 18 >

18 - 18 O

Programmare una Mdt che, dato un nastro iniziale contenente una sequenza di A e di B, con almeno una B, termina la sua esecuzione lasciando sul nastro la sequenza di sole B consecutive (cioè non separate da alcuno spazio) che si ottiene da quella iniziale eliminando tutte le A.

Esempi:

Nastro Iniziale  Nastro Finale

ABAABA

BAAABABB

BBB

BB

BBBB

BBB

Questo problema può essere risolto con un procedimento interessante che rincontreremo anche più avanti: Si tratta di determinare innanzitutto l'inizio e la fine del nastro e per far ciò poniamo una C e una D rispettivamente all'inizio e alla fine. Fatto ciò ripercorriamo il tutto e cancelliamo tutte le A presenti. Quando il nastro avrà raggiunto la C o la D (dipende come viene strutturato il programma) allora la Mdt inizierà una procedura di 'ordinamento', ovvero cancellando le B e scrivendole una accanto all'altra, in modo da riordinarle.

0 A 1 < Istruzione di spostamento già vista ..torna indietro per qualsiasi A e B

0 B 1 <

1 - 1 C E all'inizio del nastro scrive una C.

1 C 2 > Fatto ciò invece deve arrivare alla fine del nastro, quindi con lo stato 2 va avanti per

2 A 2 > qualsiasi simbolo che trova.

2 B 2 >

2 - 3 D E infatti alla fine scrive una D

3 D 4 < Poi torna indietro e con lo stato 4 inizia una istruzione di scorrimento finalizzata a

4 A 4 - cancellare tutte le A

4 B 4 < Invece le B le ignora

4 - 4 < Per ogni simbolo vuoto che trova va indietro

4 C 5 > finché giunge alla c, e va avanti.

5 B 5 > Ora trovandosi un nastro di sole B deve riordinarle, ma ignora quelle che sono già in sequenza.quelle che sono sparse hanno uno spazio che le divide e se capita questo

5 - 6 > la mdt passa allo stato 6

6 - 6 > va avanti per qualsiasi spazio.

6 B 7 - Se trova una B allora questa deve essere spostata. Passa allo stato 7.

6 D 10 - Se si verifica questo allora vuol dire che ha raggiunto la fine del nastro e cancella la D

5 D 10 - idem come sopra

7 - 7 < Allo stato 7 torna indietro per qualsiasi cella vuota

7 C 8 > finchè non raggiunge ho l'inizio del nastro

7 B 8 > oppure la fine della sequenza ordinata della B.allora va avanti di una cella

8 - 5 B e scrive una B. Torna allo stato 5

10 - 10 < Allo stato 10 la mdt deve solo ripercorrere il nastro per cancellare la C all'inizio

10 B 10 < il nastro ormai è composto da sole b, quindi basta questa istruzione

10 C 11 - Cancella la C

Dato un numero intero positivo n , n div 2 è il numero n/2 se n è pari , (n-1)/2 se n è dispari. Ad esempio 6 div 2 è il numero 3 , mentre 9 div 2 è il numero 4. Programmare una Mdt che, dato un nastro iniziale contenente una sequenza composta da n A consecutive (con n>1) termina la sua esecuzione lasciando sul nastro la sequenza composta da n div 2 A consecutive.

Esempi:

Nastro Iniziale  Nastro Finale

SI

NO

Anche questo problema può essere risolto in vari modi..innanzitutto bisogna stabilire se il numero n di A è un numero pari o dispari. In quest'ultimo caso, togliamo l'ultima A. Fatto ciò bisogna dimezzare il numero di A presenti sul nastro. In pratica ripercorro tutte le A, e ad ogni posizione infrappongo delle B in questo modo: ABABAB. Arrivato all'inizio del nastro scrivo una C per segnare l'inizio del nastro e ripercorro di nuovo il nastro con lo stato 5 , questa volta per cancellare tutte le B che ho scritto. Giunto alla fine del nastro scrivo una D per segnarne la fine e inizio ad riordinare tutte le A secondo una procedura che abbiamo già visto nell'esercizio precedente.

0 a 1 > Inizio a scorrere il nastro per determinare se il numero di A è pari o dispari.

1 a 0 >

1 - 2 < Nel caso il numero di A fosse dispari torno indietro con lo stato 2 per cancellare una A

2 a 2 -

2 - 3 <

0 - 3 < In questo caso le A sono pari.

3 a 3 b Nello stato 3 invece interpolo le A usando le B

3 b 4 <

4 a 3 <

3 - 4 c Giunto all'inizio scrivo una C

4 c 5 > e vado avanti.

5 a 5 > Con questa procedura invece ripercorro il nastro per cancellare tutte le B

5 b 6 -

6 - 5 >

5 - 7 d Giunto alla fine del nastro scrivo una D per segnarne la fine.

7 d 7 < Torno indietro e inizio a riordinare le A

7 - 8 < Cioè quando trovo spazi vuoti vado indietro finchè non trovo una A

8 - 8 <

8 a 9 - Appena la trovo la cancello

9 - 9 > e ritorno indietro.

9 d 10 < Appena incontro la d

9 a 10 < oppure la A, mi sposto verso sinistra

10 - 10 a per scrivere la A che ho cancellato.

10 a 8 < e rinizio il giro

8 c 11 - Giunto alla fine cancello la C

11 - 11 > e vado fino alla fine per cancellare la D.

11 a 11 >

11 d 12 -

Programmare una Mdt che, dato un nastro iniziale contenente una sequenza di A e di B, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene da quella iniziale rimpiazzando due o più A consecutive con una sola A e due o più B consecutive con una sola B.

Esempi:

Nastro Iniziale  Nastro Finale

ABABAA

BBAAABBAAA

AAAAA

BBBBB

ABABA

BABA

A

B

Questo problema è interessante: per mettere a posto la stringa poniamo una C e una D rispettivamente all'inizio e alla fine del nastro. Successivamente controlliamo per ogni A e per ogni B se c'è un 'surplus' di questi caratteri e li cancelliamo. Alla fine troveremo un nastro composto da una C e una D all'interno dei quali dei simboli A e B insieme a degli spazi all'interno. Ci basta riordinare il tutto con una procedura già vista (di spostamento) e il gioco è fatto!

0 A 1 < Istruzione di scorrimento all'indietro

0 B 1 <

1 - 2 C per scrivere una C all'inizio del nastro

2 C 3 > successivamente vado avanti per qualsiasi simbolo (A,B,C)

3 A 3 >

3 B 3 >

3 - 4 D per giungere alla fine del nastro e scrivo D

4 D 4 < ora torno indietro e inizio a eliminare tutti i simboli in eccesso

4 A 5 < Infatti se trova una A passa allo stato 5 e va indietro di una cella

5 A 6 - se nello stato 5 incontra di nuovo una A allora la cancella

6 - 5 < e tornando allo stato 5 questa operazione può essere ripetuta per tutte le A

5 b 4 b Nel caso che ci sia una B allora non c'è bisogno di eliminare nulla

4 B 7 < Adesso se trova una B invece deve controllare che non ce ne siano altre dopo: passa a stato 7

7 b 8 - se nello stato 7 trova una B la cancella

8 - 7 < torna indietro e ripete l'operazione (se trova altre B)

7 a 4 a Se trova una A allora la sequenza di B è finita. Ritorna allo stato 4

7 c 5 c Se si verifica questa condizione allora siamo giunti all'inizio del nastro

5 c 9 > '7 c' e '5 c' avvengono a seconda che la sequenza inizi con A o con B. Iniziamo a riordinare

9 - 9 > vado avanti per qualsiasi cella vuota.

9 a 10 - finché non incontro una A e la cancello

10 - 10 < poi allo stato 10 torno indietro

10 c 11 > finché non giungo all'inizio del nastro: per qualsiasi simbolo che trovo mi devo fermare

10 a 11 >

10 b 11 >

11 - 12 a quindi vado avanti e scrivo una A

12 a 9 > e ritorno allo stato 9

9 b 13 - Stesso procedimento di prima applicato alla B

13 - 13 <

13 a 14 >

13 b 14 >

13 c 14 >

14 - 15 b

15 b 9 >

9 d 16 - Se si verifica ciò allora siamo giunti alla fine del nastro. Si cancella la D

16 - 16 < e si torna indietro

16 a 16 < per qualsiasi simbolo

16 b 16 <

16 c 17 - per raggiungere la C e cancellarla.

I problemi della 2° gara risolti e commentati

a)Programmare una Mdt che dato un nastro iniziale contenente la rappresentazione decimale di un numero positivo K, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti.

Esempi:

Nastro Iniziale  Nastro Finale

SI

NO

Per risolvere questo tipo di problema non sarà necessario operare alcuna divisione .per vedere se il numero è pari basta controllare l'ultima cifra a destra del numero, quella delle unità. Se quella cifra è 0, 2, 4, 6, 8 allora il numero è pari, invece se la cifra delle unità è 1, 3, 5, 7, 9 allora il numero risulta dispari. L'unico problema come ho già citato per altri è la lunghezza del codice in questione, dato che dobbiamo estenderlo a tutti i casi possibili.

0 1 0 > Vado alla fine del numero..

0 2 0 > per qualsiasi simbolo numerico che incontro.

0 3 0 >

0 4 0 >

0 5 0 >

0 6 0 >

0 7 0 >

0 8 0 >

0 9 0 >

0 0 0 >

0 - 1 < Arrivato qui torno indietro per controllare l'ultima cifra

1 0 3 - Per 0, 2 ,4 , 6 ,8 il numero è pari

3 - 5 < Infatti ora torno indietro a cancellare il numero (con lo stato 5)

5 1 3 - Cancello qualsiasi simbolo che mi trovo davanti

5 - 8 S

8 S 13 > e scrivo SI

13 - 13 I

1 1 4 - Per 1, 3, 5, 7, 9 il numero è dispari

4 - 6 < Difatti torno indietro a cancellare il numero (con lo stato 6)

6 - 9 N E scrivo NO

9 N 10 >

10 - 10 O

b) Programmare una Macchina di Turing che, dato un nastro iniziale contenente

una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI

se la sequenza iniziale contiene la sottosequenza ABA, la sola sequenza NO altrimenti.

Nastro Iniziale  Nastro Finale

AABAB

ABBA

BA

SI

NO

NO

Esempi:

0 A 1 > Inizia il controllo della sottosequenza ABA.

1 B 2 > Poi controlla se la A è seguita dalla B

2 A 7 > E se la B è seguita dalla A.se ciò avviene passa allo stato 7

0 B 0 >

1 A 0 A

1 - 3 <

2 B 0 B

7 A 7 > In questo caso la sequenza contiene ABA

7 B 7 > Quindi cancella tutto

7 - 8 <

8 A 9 -

8 B 9 -

9 - 8 <

8 - 10 S E scrive SI

10 S 11 >

11 - 12 I

0 - 3 < Nel caso sia giunto alla fine della sequenza senza trovare ABA passa allo stato 3

3 A 4 - Cancella tutto

3 B 4 -

4 - 3 <

3 - 5 N E scrive NO

5 N 6 >

6 - 13 O

c) Programmare una Mdt che dato un nastro iniziale contenente una sequenza di A e di B di lunghezza dispari, termina la sua esecuzione lasciando sul nastro il simbolo in posizione centrale della sequenza iniziale.

Esempi:

Nastro Iniziale  Nastro Finale

AABAB

AAA

B

B

A

B

Questo problema è semplicissimo..basta eliminare un simbolo per volta dal nastro sia a destra che a sinistra. Fino a lasciare quello centrale.

0 A 1 <

0 B 1 <

1 - 2 >

2 A 3 >

2 B 3 >

3 A 5 <

3 B 5 <

5 A 5 <

5 B 5 <

5 - 6 >

6 A 6 -

6 B 6 -

6 - 7 >

7 A 7 >

7 B 7 >

7 - 8 <

8 A 9 -

8 B 9 -

9 - 10 <

10 A 10 <

10 B 10 <

10 - 0 >

d) Programmare una Mdt che dato un nastro iniziale contenente una sequenza di A e di B termina la sua esecuzione lasciando sul nastro la sequenza ottenuta rovesciando quella iniziale.

Esempi:

Nastro Iniziale  Nastro Finale

SI

NO

0 A 0 >

0 B 0 >

0 - 1 C

1 C 1 <

1 A 3 C

3 C 3 >

3 A 3 >

3 B 3 >

3 - 8 A

8 A 8 <

8 B 8 <

8 C 1 C

1 B 4 C

4 C 4 >

4 A 4 >

4 B 4 >

4 - 9 B

9 A 9 <

9 B 9 <

9 C 1 C

10 C 10 -

10 - 10 >

e) Programmare una Mdt che, dato un nastro iniziale contenente una sequenza di sole A, termina la sua esecuzione lasciando sul nastro una sequenza di A e B intercalate, di lunghezza doppia rispetto alla sequenza iniziale.

Esempi:

Nastro Iniziale  Nastro Finale

SI

NO

Ecco la soluzione del problema (peraltro molto semplice):

0 A 1 C

1 C 1 >

1 A 1 >

1 - 2 C

2 C 2 <

2 A 3 A

3 A 3 <

3 C 0 >

2 - 5 >

5 C 6 A

6 A 6 >

6 C 5 B

5 B 5 >

f) Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza, eventualmente vuota, contenente un numero pari di A, termina la

sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale inserendo al centro della stessa la sequenza BB.

Nastro Iniziale  Nastro Finale

43100

Questo problema è abbastanza semplice, anche se devo ammettere che la sua risoluzione non è stata immediata. Per inserire al centro del nastro 'BB' non devo trovare un modo per fermarmi a metà del nastro, cosa peraltro abbastanza complicata, bensì sposto il primo simbolo del nastro a destra e subito dopo sposto l'ultimo a sinistra, e cosi via fino a creare 2 spazi vuoti dentro al nastro, che riempirò con due B

0 A 1 - Cancello il primo simbolo del nastro

1 - 2 < Torno indietro per spostarlo di una casella

2 - 3 A E scrivo una A passando allo stato 3

3 A 3 > ora vado alla fine del nastro

3 - 4 > ignorando lo spazio che ho creato

4 A 4 >

4 - 5 A finchè arrivo alla fine del nastro e scrivo una A

5 A 6 < torno alla A precedente e la cancello

6 A 6 -

6 - 7 <

7 A 7 <

7 - 0 >

0 - 9 B

9 B 9 <

9 - 10 B

g) Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A, B e C termina la sua esecuzione lasciando sul nastro la

sequenza ottenuta da quella iniziale rimpiazzando ogni sottosequenza ABC con ACB.

Esempi:

Nastro Iniziale  Nastro Finale

SI

NO

0 A 1 >

0 B 0 >

0 C 0 >

1 B 2 >

1 A 0 A

1 C 0 C

2 C 7 C

2 A 0 A

2 B 0 B

7 C 8 B

8 B 9 <

9 B 10 C

10 C 0 >

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro una sequenza contenente lo stesso numero di A e lo stesso numero di B della sequenza iniziale, in cui però tutte le A precedono tutte le B.

Per risolvere questo problema bisogna porre una D alla fine del nastro e riordinare la sequenza riscrivendola DOPO la D. Le lettere riordinate si segnano con una C. Quando la sequenza iniziale è formata da tutte c allora bisogna cancellarle.

Esempi:

Nastro Iniziale  Nastro Finale

SI

NO

0 A 0 >

0 B 0 >

0 - 1 C

1 C 1 <

1 A 2 C

1 B 1 <

1 - 4 >

2 C 2 >

2 B 2 >

2 A 2 >

2 - 3 A

3 A 3 <

3 C 1 <

4 B 5 C

4 C 4 >

5 B 5 >

5 C 5 >

5 A 5 >

5 - 6 B

6 B 6 <

6 A 6 <

6 C 7 <

7 C 7 <

7 B 4 B

7 - 8 >

8 C 9 -

9 - 8 >

i)Programmare una Mdt che dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro una sola sequenza SI se la sequenza iniziale contiene un numero pari di A e un numero dispari di B , la sola sequenza NO altrimenti.

Esempi:

Nastro Iniziale  Nastro Finale

SI

NO

0 A 1 > Una semplice istruzione di scorrimento.ma con una differenza: ogni volta che incontra una

0 B 0 > A cambia di stato, cioè cambia tra 0 e 1

1 A 0 >

1 B 1 >

1 - 8 < In questo caso se il controllo termina con lo stato 1 vorrà dire che il numero delle A era

8 A 9 - dispari

8 B 9 -

9 - 8 < Quindi cancello il tutto,

8 - 10 N E scrivo NO

10 N 11 >

11 - 11 O

0 - 2 < Nel caso che la stringa termini e la Mdt è nello sto 0 vuol dire che il numero di A presenti

2 A 2 < è pari come richiesto dall'esercizio

2 B 3 < in questo caso torno indietro per controllare il numero delle B

3 A 3 < ovviamente utilizzando lo stesso procedimento che ho usato per determinate il numero

3 B 2 < delle A

2 - 0 A Nel caso che il numero di B sia pari, come non richiesto, invece di scrivere una procedura per cancellare tutto, riutilizzo quella che ho scritto prima semplicemente aggiungendo un'altra A e facendo partire il controllo dall'inizio. Poiché se siamo arrivati fino a questo punto il numero delle A è certamente pari. Aggiungendo una A il numero delle A diventa dispari. Quindi andando la Mdt a controllare vede che la condizione delle A pari non è più soddisfatta e cancella tutto scrivendo NO.

3 - 4 > Se siamo giunti all'inizio del nastro con lo stato 3 significa che il numero delle B era dispari

4 A 5 - come richiesto, cancello tutto.

4 B 5 -

5 - 4 >

4 - 6 S e scrivo SI !

6 S 7 >

7 - 7 I

I problemi della 3a gara risolti e commentati

Programmare una Mdt che, dato un nastro iniziale contenente un numero intero n>0 termina la sua esecuzione lasciando sul nastro n-1

Esempi:

Nastro Iniziale  Nastro Finale

13

0 0 0 > Semplice istruzione di scorrimento.

0 1 0 >

0 2 0 >

0 3 0 >

0 4 0 >

0 5 0 >

0 6 0 >

0 7 0 >

0 8 0 >

0 9 0 >

0 - 1 < Appena arrivo alla fine torno indietro di una casella.

1 1 2 0 Qui sta la parte più interessante del programma. Appena trovo un numero scrivo quello

1 2 2 1 che lo precede. La cosa diventa più complicata quando trovo lo 0. Allora in questo caso

1 3 2 2 non devo far altro che scrivere un 9, spostarmi sul numero accando e diminuire lo stesso

1 4 2 3 di 1.

2 0 4 > Questo mi serve per controllo..non posso fare 10-1=09 !!! devo cancellare lo zero che

4 9 4 < antecede il 9.

4 0 4 - à infatti.

1 0 3 9 Queste due istruzioni mi consentono di controllare tutti gli 0 e trasformarli in 9

3 9 1 < Così posso diminuire di 1 anche 10000000, ovvero numeri composti da molti 0

Programmare una Mdt che dato un nastro iniziale contenente un numero intero n compreso tra 1 e 9, termina la sua esecuzione lasciando sul nastro n A consecutive

Esempi:

Nastro Iniziale  Nastro Finale

A

AAAAA

AAAAAAAAA

Questo problema è divertente: basta diminuire di 1 il numero scritto e contemporaneamente scrivere una A accanto al numero.peccato che i numeri varino solo da 1 a 9. D'altronde aspettare di vedere scritte 50 A consecutive sarebbe piuttosto noioso.comunque ecco il codice:

0 9 1 8 Qualsiasi numero che trovo lo diminuisco di 1

0 0 7 - Fino allo 0, che rappresenta la fine del lavoro.

1 0 2 > Fatta la sottrazione passo avanti, per qualsiasi numero scritto.

1 1 2 >

1 2 2 >

1 3 2 >

1 4 2 >

1 5 2 >

1 6 2 >

1 7 2 >

1 8 2 >

2 - 3 > Arrivato, salto una casella (così posso riutilizzare codice già scritto quando torno indietro)

3 A 3 > Vado avanti per qualsiasi A già scritta.

3 - 4 A E scrivo una A

4 A 4 < Torno indietro.

4 - 0 < e quando trovo la casella vuota (per questo l'ho messa) vado indietro e torno allo stato 0.

Programmare una Mdt che dato un nastro iniziale contenente una sequenza di n A consecutive (con n>0), termina la sua esecuzione lasciando sul nastro il numero n.

Esempi:

Nastro Iniziale  Nastro Finale

A

AAAAAA

AAAAAAAAAAA

1

Questo problema è l'opposto di quello precedente..solamente che in questo caso il numero può superare ben oltre il numero 9.quindi per evitare complicazioni invece di scrivere il numero a destra del nastro (ad esempio AAAAAA9 come si può scrivere la seguente decina???) , lo scriviamo alla sua sinistra, evitando così qualsiasi problema.

0 A 0 > Vado fino alla fine del nastro.

0 - 1 <

1 A 1 - e cancello l'ultima A

1 - 2 <

2 A 2 < Torno indietro.

2 - 3 1 E scrivo il primo numero. Adesso per qualsiasi numero che trovo scrivo il suo successivo.

2 9 4 0 In questo caso ho trovato 9, quindi devo tramutarlo in 0 e aggiungere 1 alla sua sinistra,

4 0 2 < tornando semplicemente allo stato 2.

3 0 3 > Ora per qualsiasi numero scritto passo avanti.

3 1 3 >

3 2 3 >

3 3 3 >

3 4 3 >

3 5 3 >

3 6 3 >

3 7 3 >

3 8 3 >

3 9 3 >

3 A 0 A E all'inizio del nastro, ritorno allo stato 0.

Programmare una Mdt che dato un nastro iniziale contenente due numeri interi positivi x e y separati da una cella vuota tali che x>y e 9>=y>0, termina la sua esecuzione lasciando sul nastro soltanto la differenza tra x e y.

Esempi:

Nastro Iniziale  Nastro Finale

5

Ci sono vari modi per risolvere questo problema (peraltro di non facile soluzione). Innanzitutto si può trasformare l'y in una striscia di A composta da y A consecutive utilizzando il codice già scritto nel problema c. E poi diminuire l'x di una unità per ogni A del nastro che abbiamo scritto. E' un sistema effettivamente un po' laborioso, e io ho avuto la furbizia di scegliere proprio questo durante la gara di informatica. Comunque c'è né un altro più semplice: si diminuisce di una unità l'y e contemporaneamente si diminuisce di una unità la x. Appena la y arriva a 0, la cancello e mi risulta stampata la differenza tra i due numeri.

0 1 0 > Semplici istruzioni di scorrimento che mi consente di arrivare alla fine del numero.

0 2 0 > Queste istruzioni saranno riprese più volte.

0 3 0 >

0 4 0 >

0 5 0 >

0 6 0 >

0 7 0 >

0 8 0 >

0 9 0 >

0 0 0 >

0 - 1 >

2 8 2 <

2 7 2 <

2 6 2 <

2 5 2 <

2 4 2 <

2 3 2 <

2 2 2 <

2 1 2 <

2 0 2 <

2 - 3 <

5 9 3 <

6 0 4 >

4 9 4 <

4 - 0 >

Indichiamo con S una sequenza formata da A,B o C ed indichiamo con x e y un simbolo che sia A o B. Programmare una Mdt che, dato un nastro iniziale contenente una sequenza del tipo xyS termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da S rimpiazzando tutte le occorrenze di x con y.

Esempi:

Nastro Iniziale  Nastro Finale

ABCAB

BBABC

BA

CBB

ABC

Questo problema è stupidissimo da risolvere ma di difficile comprensione. In pratica il testo richiede di controllare se prima della C ci sia una sequenza formata da A e da B. In caso affermativo il programma dovrà sostituire nella sequenza successiva tutte le A con le B.

I casi sono quattro:

- stringa abS, in cui devo sostituire tutte le a di S con b

- stringa aaS, in cui devo sostituire tutte le a di S con a

- stringa baS, in cui devo sostituire tutte le b si S con a

- stringa bbS, in cui devo sostituire tutte le b di S con b.

0 A 1 - Controlla se nella prima casella c'è una A e la cancella. Passa allo stato 1

0 B 2 - Controlla se nella prima casella c'è una B e la cancella. Stato 2

1 - 1 > Va avanti.

1 A 7 - A questo punto se ci sono due A il programma termina.

1 B 3 - Nel caso che ci sia AB invece va avanti

3 - 5 >

5 A 5 B e sostituisce ogni A con una B

5 B 5 > va avanti sia per B che per C

5 C 5 >

5 - 7 < Fino alla fine del nastro, dove la Mdt si arresta

2 - 2 > Questo nel caso della B va avanti.

2 B 7 - E se c'è un'altra B la cancella e la Mdt si ferma.

2 A 4 - Invece se c'è la sequenza BA la cancella e inizia il controllo di tutte le B

4 - 6 >

6 B 6 A Per sostituirle con le A.

6 A 6 >

6 C 6 >

6 - 7 < Fine!

Programmare una Mdt che dato un nastro iniziale contenente due sequenze di A separate da una D, termina la sua esecuzione lasciando sul nastro la sequenza che contiene il maggior numero di A.

Questo problema è abbastanza semplice: si tratta solo di controllare che per ogni A a destra di D corrisponda una A a sinistra di D. Controllo che per semplificare facciamo partendo dal centro del nastro, cioè da D. Ogni volta che controlliamo una A la tramutiamo in C. Appena finisce il nastro o da destra o da sinistra, cancelliamo tutte le A e tutte le C della sequenza di A più corta, cancelliamo la D, e scriviamo le A al posto delle C.

0 a 0 > Istruzione di scorrimento delle A

0 d 1 < Appena trova la D torna indietro di una casella

1 c 1 < Scorre tutte le C che ha eventualmente scritto.

1 a 2 c Appena incontra una A la trasforma in C

2 c 2 > Poi passa allo stato 2 e torna indietro fino

2 d 2 > alla d, per poi avanzare

2 a 3 c ad una nuova A passando allo stato 3, per scrivere una C

3 c 3 < poi torna indietro per qualsiasi C

3 d 0 d finché giunge alla d e ritorna allo stato 0

1 - 4 > Nel caso che sia giunto alla fine del nastro con lo stato 0 significa che la sequenza delle A destra è stata la più lunga, quindi va avanti con lo stato 4

4 c 1 - e appena incontra una C la cancella

4 d 5 - appena incontra la D cancella anch'essa..

5 - 6 > e va avanti con lo stato 6

6 c 6 a per rimettere tutte le A al posto delle C

6 a 6 >

2 - 7 < Stesso procedimento..solo che in questo caso la sequenza delle A sinistra è stata la più lunga

7 c 2 -

7 d 8 -

8 - 9 <

9 c 9 a

9 a 9 <