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
con un 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
Nessun commento:
Posta un commento