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 <<sappiamo» già come eseguire l' operazione basilare necessaria di ottenere il resto da una divisione, per due numeri naturali A e B a piacere. Quest'operazione è ancora algoritmica, ed è eseguita col procedimento molto familiare della divisione che abbiamo imparato a scuola. Tale procedimento è in realtà un po' più complicato del resto dell'algoritmo euclideo, ma anche in questo caso si può costruire un diagramma di flusso. La principale complicazione deriva dal fatto che noi useremmo (presumibilmente) la notazione decimale convenzio??aìe per i numeri naturali, cosicché avremmo bisogno di elencare tutte le 58 nostre tavole di moltiplicazione e preoccuparci del riporto ecc. Se, per rappresentare il numero n, usassimo semplicemente una successione di n segni di qualche genere - per esempio • • • • • per rappresentare il cinque - allora la formazione di un resto verrebbe vista come un' operazione algoritmica molto elementare. Per ottenere il resto quando si divide A per B continueremmo semplicemente a togliere la successione di segni che rappresentano B da quella dei segni che rappresentano A fino a quando non rimangono più segni sufficienti per continuare a eseguire l'operazione. L'ultima successione restante di segni fornisce la soluzione richiesta. Per esempio, per ottenere il resto nella divisione di diciassette per cinque, procediamo semplicemente eliminando successioni di • • • • • da • • • • • • • • • • • • • • • • • nel modo seguente: • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • e la soluzione è chiaramente due, giacché a questo punto non si può più ripetere l'operazione. Un diagramma di flusso che trova il resto in una divisione, conseguito con questo mezzo della sottrazione ripetuta, può essere fornito nel modo illustrato a p. 60. Per completare l'intero diagramma di flusso per l'algoritmo euclideo, sostituiamo questo diagramma per formare il resto nel riquadro nel centro a destra nel nostro diagramma originario. Questo tipo di sostituzione di un algoritmo a un altro è una comune procedura di programmazione per computer. L'algoritmo dato qui sopra per trovare un resto è un esempio di su!Jroutine o sottaprogramma, ossia è un algoritmo (normalmente già noto) che viene chiamato e usato dall'algoritmo principale come parte del1a sua operazione. Ovviamente la rappresentazione del numero n semplicemente nella forma di n pa11ini è molto inefficiente quando sono in gioco grandi numeri, ed ecco perché normalmente usiamo notazioni più concise, come il sistema normale (decimale) . Noi qui però non ci preoccuperemo eccessivamente dell' efficienw di operazioni o notazioni. Ci interessa invece il problema di quali operazioni possano in linea di principio essere eseguite algoritmicamente. Quel che è algoritmico se usiamo un tipo di notazione numerica è algoritmico anche se usiamo l'altra. L'unica differenza consiste nei particolari e nella complessità, che sono diversi nei due casi. 59 SAo sctoitnu isBc i No PrendiA dueeB n umeri Ferma il caSlcìo lo e stampa la risposta A L'algoritmo euclideo è solo uno fra i numerosi procedimenti ??goritmici, spesso classici, che si trovano nell' intera matematica. E però forse degno di nota il fatto che, nonostante le antiche origini storiche di esempi specifici di algoritmi, la precisa formulazione del concetto di un algoritmo generale risalga solo a que sto secolo. Di fatto sono state date varie descrizioni alternative di questo concetto, tutte negli anni trenta. La più diretta e convincente, e anche storicamente la più importante, è nei termini del concetto noto come macchina di Turing. Sarà opportuno esaminare queste «macchine>> 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 <<procedimento meccanico>> . Il concetto era estraneo alle normali idee matematiche del tempo. Per affrontarlo, Turing tentò di immaginare come potesse essere formulato il concetto di una <<macchina>> , scomponendone le operazioni in termini elementari. Pare chiaro anche che Turing considerasse un cervello umano come esempio di una <<macchina>> 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 <<Carta da minuta>> 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 <<Carta da minuta>> ) , 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 <<interiorizzi>> 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