e#ledx abalgodelx ritmo euclideo , dividiamo uno dei due numeri per l'altro e prendiamo nota del resto: il 1 365 sta nel 3654 due volte, col resto di 924 ( = 3654 – 2730) . Sostituiamo ora i nostri due numeri di partenza con questo resto, ossia 924, e col numero che abbiamo appena usato come divisore, ossia 1 365, in quest'ordine. Ripetiamo il procedimento, usando però questa nuova coppia di numeri: il 924 sta nel l 365 una volta, col resto di 441 . Otteniamo così una nuova coppia: 44 1 e 924, e dividiamo il 924 per 441 ottenendo il resto di 42 ( = 924 – 882) , e così via di seguito fino a ottenere una divisione senza resto. Disponendo ordinatamente tutti i nostri calcoli in un prospetto, otteniamo: 3654 1 365 dà come resto 924 1 365 924 dà come resto 441 924 441 dà come resto 42 44 1 42 dà come resto 2 1 42 2 1 d à come resto O. L'ultimo numero da noi usato come divisore, ossia 2 1 , è il massimo conun divisore richiesto. L'algoritmo euclideo è il procedimento sistematico per mezzo del quale abbiamo trovato questo massimo comun divisore. Abbiamo applicato questo procedimento a una coppia di numeri particolari, ma il procedimento si applica universalmente , a numeri di qualsiasi grandezza. Per numeri grandissimi potrebbe richiedere molto tempo e quanto più i numeri sono grandi tanto maggiore tende a essere il tempo richiesto. Ma in qualsiasi caso ,\jJecifico il procedimento avrà termine e fornirà una risposta ben definita in un numero finito di passi . A ogni passo è pcrkttamcnte chiaro quale operazione si debba compiere, c anche la decisione circa il rnoml' nto in cui l'intero processo si deve ritenere concluso è pedéttarnente definita. Inoltre la descrizione dell 'intero procedi- 5 7 mento può essere presentata in termini finiti, pur applicandosi a numeri naturali di dimensioni illimitate. (I «numeri naturali>> sono semplicemente i numeri interi comuni non negativi l : O, l , 2, 3, 4, 5, 6, 7, 8, 9, 10, 1 1 , ... ) In effetti, è facile costruire un «diagramma di flusso» (finito) per descrivere l'intera operazione logica dell'algoritmo euclideo. SSoossmtituuiissccii BA con B con C No PrendiA dueeB n umeri meDmivoidrizi zAa p iel rre Bs teo C Sì stFaemrmpaa lail criaslpcooslota e B Si dovrebbe notare che questa procedura non è ancora del tutto scomposta nelle sue parti più elementari, essendosi assunto implicitamente che noi <> nei loro particolari. Una cosa da tenere a mente su una «macchina>> di Turing è che essa è un concetto matematico astratto e non un oggetto fisico. Il concetto fu introdotto nel 1 935-1 936 dal matematico inglese, straordinario decifratore di codici segreti e padre autorevole dell'informatica, Alan Turing ( 1 937) nel tentativo di aff rontare un problema di vasta portata, noto come l' Entscheidungsproblem ( «problema della decisione» ) , posto in parte nel 1 900 dal grande matematico tedesco David Hilbert al Congresso Internazionale 60 dei Matematici a Parigi ( << decimo problema di Hilbert>> ) e riproposto, in modo più completo, al Congresso Internazionale di Bologna nel l 928. Hilbert aveva chiesto niente di meno che un procedimento algoritmico generale per risolvere problemi matematici, o piuttosto per rispondere alla domanda se un tale procedimento possa o meno esistere in linea di principio. Hilbert aveva inoltre concepito un programma per fondare la matematica su basi incrollabilmente sane, con assiomi e regole procedurali che dovevano essere fissati una volta per tutte, ma quando Turing produsse la sua grande opera quel programma aveva già subìto un colpo distruttivo da un teorema dimostrato nel 1931 dal brillante logico austriaco Kurt Godel. Considereremo il teorema di Godel e la sua portata nel capitolo 4. Il problema di Hilbert che interessava a Turing (il problema della decisione) andava oltre ogni particolare formulazione della matematica nei termini di sistemi assiomatici. Il problema era: esiste un qualche procedimento meccanico generale in grado, in linea di principio, di risolvere uno dopo l'altro tutti i problemi della matematica (appartenenti a una qualche classe opportunamente ben definita) ? Un a parte della difficoltà nel rispondere a questa domanda consisteva nel decidere che cosa si dovesse intendere per <> . Il concetto era estraneo alle normali idee matematiche del tempo. Per affrontarlo, Turing tentò di immaginare come potesse essere formulato il concetto di una <> , scomponendone le operazioni in termini elementari. Pare chiaro anche che Turing considerasse un cervello umano come esempio di una <> nel suo senso , così che , quali che fossero le attività che potevano essere svolte dai matematici quando affrontavano i loro problemi di matematica, esse dovessero essere comprese sotto la rubrica di << procedimenti meccaniCI>> . Per quanto questa concezione del pensiero umano possa essere stata preziosa per Turing nello sviluppo del suo importantissimo concetto, non è aflatto necessario che noi aderiamo ad essa. In effetti, precisando che cosa si intenda per procedimento meccanico, Turing mostrò che ci sono operazioni matematiche che non possono essere chiamate meccaniche in alcun senso comune ! C'è forse una qualche ironia nel fatto che questo aspetto dell'opera di Turing può fornirci ora indirettamente un possibile accesso al suo punto di vista sulla natura dei fenomeni mentali. Questa cosa però per il momento non ci in teressa. Prima di tutto dobbiamo stabilire quale sia in realtà il concetto che Turing ha di un procedimento meccanico. 61 Il concetto di Turing Cerchiamo di immaginare una macchina per eseguire una qualche procedura di calcolo (definibile in modo finito) . Quale forma generale dovrebbe assumere una tale macchina? Dobbiamo essere preparati a idealizzare un po' e a non preoccuparci troppo degli aspetti pratici, giacché stiamo occupandoci in realtà di una «macchina>> idealizzata matematicamente. Noi vogliamo che la nostra macchina abbia un insieme discreto di diversi stati possibili, che sono in numero finito (anche se forse molto grande) . Chiamiamo questi stati gli stati interni della macchina. Non vogliamo però limitare le dimensioni dei calcoli che la nostra macchina eseguirà in linea di principio. Ricordiamo l'algoritmo euclideo descritto sopra. Non c'è, in linea di principio, alcun limite alla grandezza dei numeri su cui tale algoritmo può operare . L'algoritmo – o la procedura generale di calcolo – è esattamente lo stesso per quanto grandi possano essere i numeri. Per numeri grandissimi il procedimento potrebbe richiedere in effetti un tempo molto lungo, e una quantità considerevole di <> su cui eseguire i calcoli reali. Ma l' algoritmo è lo stesso insieme finito di istruzioni, per quanto grandi possano essere i numeri. Così, pur avendo un numero finito di stati interni, la nostra macchina dev'essere in grado di occuparsi di un input che non sia di dimensioni limitate. Dobbiamo inoltre permettere alla macchina di utilizzare per i suoi calcoli una quantità esterna illimitata di spazio di memmia (la nostra <> ) , e riconoscerle la possibilità di produrre un output di dimensioni illimitate. Poiché la nostra macchina ha solo un numero finito di stati interni distinti, non ci si può attendere che <> tutti i dati esterni né tutti i risultati dei suoi calcoli. Essa deve invece esaminare solo quelle parti dei dati o dei calcoli precedenti di cui sta occupandosi immediatamente, e poi deve eseguire qualunque operazione le venga chiesto di eseguire su di essi. Essa può annotare, forse nello spazio di memoria esterno, i risultati pertinenti di tale operazione, e poi passare in un ??odo determinato esattamente alla fase di operazione successiva. E la natura illimitata dell' input, dello spazio di calcolo e dell' output a dirci che stiamo considerando solo un'idealizzazione matematica e non qualcosa che potrebbe essere effettivamente cost:Iuito in pratica (vedi la figura 2. 1 ) . Ma è un' idealizzazione molto importante. Le meraviglie della moderna tecnologia dei computer ci hanno fornito dispositivi di memoria elettronici che possono essere trattati, in effetti, come illimitati ai fini della maggior parte degli usi pratici. 62 Figura 2. 1 . Un a macchina di Turing rigorosa richiede un nastro infinito ! Di fatto il tipo di spazio di memoria che nella precedente