Archive for agosto, 2009

La macchina di Turing – Storia e basi tecniche

28 Comments

Ecco qui un estratto della mia tesina di maturità 2008… che parla appunto della Macchina di Turing, parla poco degli aspetti puramente tecnici, ma tuttavia se studiata bene già rappresenta l’ indispensabile per costruire con successo qualsiasi tipo di programma..

Consento la copia anche integrale di questo documento a patto di citare la fonte… poichè è una mia personale rielaborazione presentata pure in sede d’ esame 🙂

Perché ho scelto la Macchina di Turing?

Prima di iniziare a trattare di questo argomento, ritengo utile spiegare ai miei lettori le cause che mi hanno spinto a trattare della Macchina di Turing in sede d’ esame orale. Il motivo principale è ovviamente il mio interesse per questa straordinaria macchina, a dire il vero un poco antiquata ma che suscita il mio interesse per il suo linguaggio estremamente di basso livello.

Come è risaputo ormai quasi la totalità dei PC (Personal Computer) può essere programmato da molte persone che conoscono funzioni “vicine allo schermo”; una persona inserisce istruzioni in un linguaggio semplice e intuitivo e queste istruzioni vengono elaborate e trascritte nel Linguaggio Macchina.

A nessuno verrebbe in mente di scrivere i propri software direttamente in linguaggio macchina, se non per scopi puramente ludici, sarebbe impensabile difatti per un industria pagare i suoi ingegneri per programmare in linguaggio di basso livello (a stretto contatto con la macchina).

A me semplicemente piace questa macchina poiché mi permette di dialogare con la macchina in un modo molto intuitivo, che però dà possibilità di iterazioni con un numero di problemi aritmetici pressoché infiniti.

Il secondo motivo per cui ho scelto di descrivere questa macchina risiede nel fatto che ho una grande ammirazione per colui che l’ha ideata: Alan Turing, come lui io penso che un giorno le macchine tecnologiche saranno così potenti da simulare la mente umana

Come è nata la Macchina?

La Macchina di Turing nasce nel 1936 come risposta a una sfida posta da David Hilbert (un famoso matematico tedesco su cui preferisco non dilungarmi).

La domanda di Hilbert era: <<esiste sempre, almeno in linea di principio, un metodo meccanico (cioè una maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso? >>

Veniva chiesta in parole semplici un metodo per risolvere qualsiasi problema riconducibile a un teorema matematico qualsiasi, e dimostrare se quel teorema è vero o falso. Ma non solo si trattava di paragonare il ragionamento matematico umano a una serie di calcoli meccanici.

Alan Turing ideò un nuovo modello matematico: “La macchina di Turing”; che percorreva passo per passo ogni calcolo umano, la macchina è costituita da un nastro immaginario infinito (ricordo che si tratta di una macchina astratta per ora) suddiviso in caselle, in ognuna di queste caselle è contenuto un solo carattere; vi è poi una testina che legge uno per volta una casella di un nastro e decide a seconda del carattere in esso contenuto di compiere 2 azioni, una di scrittura e una di spostamento della testina

La macchina può decidere a seconda del carattere di spostare la testina sul nastro in avanti, in indietro o farla restare ferma; così come può decidere di cambiare il carattere in un altro oppure lasciarlo inalterato.

Turing riusci a dimostrare che una macchina così precisa e così definita anche se estremamente lenta (forse + lenta di un cervello umano) sarebbe riuscita a risolvere qualsiasi problema; poiché fondeva insieme tutte le teorie della probabilità e della ricorsività; in un colpo solo Turing ha ideato quelle strutture che più avanti i programmatori chiameranno Procedure e Cicli.

Macchina di Turing (funzionamento del codice)

Una Macchina di Turing funziona a Stati; in un qualsiasi momento durante la sua esecuzione la macchina è in un determinato stato, che ne indica un funzionamento; lo Stato può avere un qualsiasi nome alfa-numerico e può essere ovviamente cambiato durante l’istruzione.

La funzione di una macchina di Turing è:

  • Identificarsi in un determinato stato

  • Leggere un determinato simbolo

  • Passare in un altro stato o rimanere in quest’ultimo

  • Sovrascrivere il simbolo o lasciarlo inalterato

  • Scorrere il nastro o la testina di un passo (avanti o indietro) o lasciare il tutto immobile

Il codice per programmare una Macchina di Turing si organizza in quintuple, cioè 5 sequenze di simboli (detti caratteri) separati da una virgola.

Generalmente si segue un esempio del genere:

{[Stato corrente],[carattere trovato],[stato seguente],[nuovo carattere],[spostamento]}

<!– @page { margin: 2cm } P { margin-bottom: 0.21cm } –>

Premetto subito che vi sono diversi metodi per programmare una Macchina di Turing io durante la mia trattazione prenderò riferimento dalle regole del Simulatore per Macchine di Turing. dell’Università di Pisa (tuttora usato nelle competizioni Nazionali di Informatica).

Ho evidenziato volontariamente le parti verdi come condizioni iniziali, e le parti in rosa le successive elaborazioni della macchina.

La macchina dapprima si rende conto dello stato in cui si trova, quindi cerca in blocco tutte le istruzioni che iniziano con quello stato, nel contempo legge il carattere su cui è posizionata la testina, e se sia stato che carattere coincidono inizia la sua elaborazione. La ricerca è di tipo esaustiva, la Macchina cerca le 2 condizioni, cioè la presenza dello stato e del carattere; le cerca per ogni quintupla, se non le trova cessa il suo funzionamento e l’elaborazione si considera conclusa

Una volta trovate queste 2 condizioni (necessarie e sufficienti); procede all’elaborazione, definisce il nuovo stato, il nuovo carattere, e sposta la testina di lettura/scrittura; fatto questo inizia nuovamente il suo ciclo ricercando il nuovo stato appena definito.

Forse è più utile chiarire questa spiegazione con un esempio pratico

<!– @page { margin: 2cm } P { margin-bottom: 0.21cm } –>

Programma Scambio A-B

Si programmi una Macchina di Turing capace di distinguere su un nastro di lettura i simboli A e B e di sostituire le A con le B e viceversa… l’elaborazione si considera conclusa nel momento in cui si trova uno spazio bianco o un qualsiasi altro carattere

In questo caso il programma è particolarmente semplice poiché non necessita di cambiamenti di Stato, semplicemente rimane nel suo stato 0 (per convenzione è uno stato di partenza) e cambia ogni A con una B e viceversa, andando avanti ogni volta; fino a che non trova un altro carattere e si ferma.

http://navigatranqui.altervista.org/img/mdt2.png

<!– @page { margin: 2cm } P { margin-bottom: 0.21cm } –>

Qui sopra è possibile vedere uno schema a blocchi intuitivo; in codice Turing tutto ciò si scrive così:

{0,A,0,B,>}

{0,B,0,A,>}

Il codice può essere ulteriormente semplificato (secondo il simulatore creato dal Dott. Antonio Cisternino) come

{0,AB,0,BA,>}

<!– @page { margin: 2cm } P { margin-bottom: 0.21cm } –>

Programma CIAO JAFAR

E’ pressoché un classico dei “niubbi”(persone che si avvicinano a un linguaggio sconosciuto); si desidera creare un programma che su un nastro vuoto scrive la stringa (insieme di caratteri) “CIAO JAFAR”; in questo caso non esistono probabilità, noi sappiamo di trovare dinanzi a noi in ogni caso uno spazio vuoto (rappresentato per convenzione con il segno “-”) e agiremo di conseguenza per scrivere il messaggio; ogni volta la macchina dovrà essere messa in uno stato diverso, in modo che cambiando di stato possa rendersi conto di cosa effettivamente scrivere; ovviamente la macchina andrà ogni volta avanti sul nastro dato che ogni casella può come detto contenere solo una lettera

http://navigatranqui.altervista.org/img/mdt3.png

Il codice per un programma del genere è questo (mi riservo la libertà di non usare le parentesi dato che non sono obbligatorie).

0,-,1,C,>

1,-,2,I,>

2,-,3,A,>

3,-,4,O,>

4,-,5,J,>

5,-,6,A,>

6,-,7,F,>

7,-,8,A,>

8,-,end,R,>

Adesso una piccola tabella che precisa le condizioni del nastro ad ogni stato.

Stato corrente Stato Seguente Situazione Nastro
0 1 C
1 2 CI
2 3 CIA
3 4 CIAO
4 5 CIAOJ
5 6 CIAOJA
6 7 CIAOJAF
7 8 CIAOJAFA
8 end CIAOJAFAR
end // CIAOJAFAR

<!– @page { margin: 2cm } P { margin-bottom: 0.21cm } –>

La Macchina di Turing, Un precursore di tutti i linguaggi:

E’ evidente nei 2 programmi che ho appena descritto si vede chiaramente quanto la Macchina di Turing abbia influito sui futuri linguaggi di programmazione, sono evidenti le 3 strutture principali della programmazione:

  • Sequenze

  • Diramazioni

  • Cicli

La Macchina di Turing le fonde a volte tutte e 3 insieme; ovviamente paragonato a un computer moderno la macchina di Turing presenta molte limitazioni, ma è da tale modello che ha avuto inizio lo sviluppo delle tecnologie informatiche.

<!– @page { margin: 2cm } –>

Esempi di Matrici e problemi + complessi

Nelle edizioni Nazionali delle gare di informatica è stato introdotto un nuovo concetto che in realtà in origine Turing non aveva considerato, il concetto di matrice, è possibile abbreviare i nomi degli stati, definendo in poche istruzioni tantissime sequenze.. utilizzando una sola quintupla per definire più di una istruzione

(0,[a..z],letto[a..z],-,>)

(letto[a..z],{a..z},letto[a..z],{a..z},>)

(letto[a..z],-,destra[a..z],-,<)

(destra[a..z],[a..z],ritorno,-,<)

(ritorno,[a..z],ritorno,[a..z],<)

(ritorno,-,0,-,>)

Equivale al ben + complicato:

(0,a,lettoa,-,>)

(0,z,lettoz,-,>)

(lettoa,a,lettoa,a,>)

(lettoa,b,lettoa,b,>)

(lettoa,z,lettoa,z,>)

(lettob,a,lettob,a,>)

(lettob,z,lettob,z,>)

(lettoz,a,lettoz,a,>)

(lettoz,z,lettoz,z,>)

(lettoa,-,destraa,-,<)

(lettoz,-,destraz,-,<)

(destraa,a,ritorno,-,<)

(destraz,z,ritorno,-,<)

(ritorno,a,ritorno,a,<)

(ritorno,z,ritorno,z,<)

(ritorno,-,0,-,>)

<!– @page { margin: 2cm } P { margin-bottom: 0.21cm } –>

L’ invenzione delle matrici ci permette di snellire ancora di + il codice (da notare che ho omesso quello fra i puntini, per ragioni di spazio); snellire il codice è diventata una delle priorità per un buon programmatore.

<!– @page { margin: 2cm } –>

Enigma

La macchina Enigma aveva l’aspetto di una macchina per scrivere con due tastiere: una vera inferiore, e la seconda fatta di lettere luminose che si accendevano ad ogni tasto premuto sulla tastiera: la sequenza delle lettere che si illuminavano dava il messaggio cifrato (o quello in chiaro, se si batteva il testo cifrato).Il suo funzionamento si basava su tre dischi cablati, detti rotori, che avevano 26 contatti per lato (uno per ogni lettera dell’alfabeto tedesco): i cablaggi dei dischi mettevano in comunicazione ciascuna lettera su un lato con una lettera sull’altro lato. I dischi erano collegati insieme da un meccanismo simile ad un odometro: il primo disco ruotava di una lettera ad ogni pressione di tasto, il secondo ruotava di una lettera ogni volta che il primo compiva un giro e il terzo ruotava di una lettera quando il secondo finiva un giro. Il terzo e ultimo rotore era collegato a un riflettore che, cablato come un rotore, scambiava il contatto della lettera del terzo rotore e rispediva indietro il contatto attraverso tutti e tre i rotori: quindi la tensione applicata al contatto della lettera premuta dall’operatore sulla tastiera veniva applicata sul contatto corrispondente del primo rotore e usciva dallo stesso rotore attraverso un altro contatto, diretta stavolta verso una delle lampadine di Enigma. Oltre a questo, Enigma poteva essere regolata con degli spinotti per scambiare fra loro dieci lettere con altre dieci a scelta, per maggior sicurezza; infine i contatti di ogni rotore da una faccia all’altra potevano venire sfalsati a piacere.

http://navigatranqui.altervista.org/img/mdt4.jpg

Bomba

La Bomba, fu una speciale macchina calcolatrice utilizzata dapprima dal controspionaggio polacco ed in seguito da quello inglese per decifrare i messaggi segreti tedeschi codificati con la macchina Enigma, ideata da Arthur Scherbius. Una volta ricostruita la struttura logica di Enigma, Rejewski progettò un dispositivo elettro-meccanico, il “ciclometro”, che permetteva di ricostruire velocemente la posizione iniziale dei rotori; in seguito venne usata anche la tecnica dei “fogli perforati”, ed infine venne costruita la “bomba crittologica”, un rudimentale calcolatore basato sul metodo forza bruta, il cui nome deriva dal sibilo che emetteva quando tutti i suoi rotori giravano alla massima velocità. La “Bomba” era una macchina composta da molti moduli; ciascun modulo consisteva di uno scaffale di ferro largo 2 metri e 10, alto uno e 90, profondo sessanta centimetri, e pesante circa una tonnellata. Ogni modulo metteva in movimento 108 rotori (più tre di controllo) in gruppi di 12 per fila, che eseguivano gradualmente la decodifica dei messaggi.

Tra il 1938 e il 1939 i tedeschi cambiarono le regole di cifratura, aumentando il numero dei rotori della macchina Enigma da 3 a 5, così che il metodo dei polacchi perse gran parte della sua efficacia. In quel periodo la decrittazione di messaggi Enigma da parte dell’ufficio cifra polacco divenne sporadica. In effetti, nel 1940 furono decriptati con l’aiuto della “Bomba” solo 178 messaggi.

La “Bomba” conobbe una nuova fase di sviluppo dopo l’entrata in guerra degli anglo-americani, ad opera del gruppo di matematici inglesi di Bletchley Park, con il contributo di Alan Turing, considerato uno dei padri del computer moderno (per la sua idea della macchina di Turing, ovvero

una macchina logica universale programmabile per mezzo di un algoritmo). Tali studi portarono nel 1944 alla costruzione della “Bomba” inglese, ovvero del calcolatore Colossus.

Facebook assume 500 dipendenti

34 Comments

Il social network Facebook punta ad aumentare il totale dei suoi dipendenti del 50% nel corso del 2009. E’ quanto ha dichiarato l’amministratore delegato della società, Mark Zuckerberg.

L’ obbiettivo è ambizioso.. quadruplicare il numero di utenti, il che è possibilissimo dato che in molte aree del mondo non si è verificata una crescita come in Europa.

I dipendenti di Facebook al momento sono circa mille. Brutte notizie invece per MySpace, principale concorrente di Facebook, che taglierà del 30% sul personale.

Questa è la pagina dove sono raccolte tutte le differenti offerte di lavoro, divise in 12 categorie, ovviamente è tutto in inglese

Last Message – E-mail dal regno dei morti

61 Comments

Un pò macabra come idea ma sicuramente utile, Last Message Club è il servizio nato in Inghilterra che permette a ogni utente di creare al più 100 messaggi da recapitare post-morte.

Non si parla di testamenti quindi, ma più che altro di messaggi d’ addio, custoditi gelosamente da un enorme cervello elettronico, sicuramente molti anziani prima di morire hanno lasciato lettere di questo genere a persone fidate; adesso ciò non sarà + necessario poichè a farlo può essere un computer, di sicuro in modo più discreto.

Possono essere recapitati infatti anche messaggi d’ amore, o confessioni imbarazzanti, o persino auguri di matrimonio a cui sappiamo di non poter fisicamente assistere, insomma se ne possono fare di tutti i colori.

Simon Gilligan, 63 anni, è tra i primi ad aver utilizzato questo sistema preparando messaggi “dall’aldilà” per la moglie, i figli e altri parenti. «Ti costringe a confrontarti con l’idea della morte» – ha dichiarato -, «ma anche a pensare a tanti piccoli dettagli, ad esempio ricordare a qualcuno di annullare il tuo abbonamento dell’autobus»