Complessità
algoritmica e dintorni
Daniele Mundici
Dipartimento di Matematica “Ulisse Dini”
Università di Firenze
[email protected]
§1
Antefatto:
settembre 2000
www.clay.org
Statement from the Directors and Scientific
Advisory Board
In order to celebrate mathematics in the new millennium, The Clay
Mathematics Institute of Cambridge, Massachusetts (CMI) has
named seven “Millennium Prize Problems.” The Scientific Advisory
Board of CMI selected these problems, focusing on important classic
questions that have resisted solution over the years.
The Board of Directors of CMI have designated a $7 million prize
fund for the solution to these problems, with $1 million allocated to
each.
I sette problemi per il III millennio
P versus NP
The Hodge Conjecture
The PoincarŽConjecture
The Riemann Hypo thesis
Yang-Mills Existence and Mass Gap
Navier-Stokes Existence and Smoothness
The Birch and Swinnerton-Dyer Conjecture
cento anni prima, a Parigi, Hilbert
aveva presentato i suoi famosi problemi...
Wir müssen wissen,
wir werden wissen
Epitaffio
David Hilbert 1862-1943
il problema della completezza di Hilbert
•
le regole che da
tremila anni si
applicano per fare un
ragionamento
rigoroso, sono in
grado di dimostrare
tutte le verità ?
•
oppure qualche regola
è ancora da scoprire ?
teorema di completezza di Gödel, 1930
(il suo primo grande teorema)
•
nessun genio futuro potrà
scoprire nuove regole logiche:
quelle già note sono complete
•
ma allora come si spiega
l’incapacità di provare
logicamente il postulato delle
parallele ?
•
si spiega col fatto che ci sono
geometrie in cui valgono gli
altri assiomi, ma non quello
delle parallele
Il sogno di Hilbert
dopo gli scossoni causati dalle geometrie
non euclidee e poi dai paradossi...
dare fondamenta solide alla Matematica
trovando una procedura per decidere ogni
problema matematico
in un numero finito di passi
Il sogno di Hilbert
•
•
•
•
La procedura deve essere in grado di
scoprire tutti i fatti matematici veri
La procedura deve produrre solo
dimostrazioni corrette
La procedura dovrebbe essere in grado di
dimostrare che produce solo dimostrazioni
corrette
ad es., dimostrare che 0=1 non verrà
prodotto dalla procedura stessa (guai !)
ma come definire numero finito di passi?
•
da tempo l’umanità sa costruire figure geometriche, ma
solo nel 1801 Gauss trovò una condizione necessaria e
sufficiente su n affinché l’n-gono regolare sia costruibile
con riga e compasso. Per questo risultato non basta
saper costruire: occorre definire la “non costruibilità”
•
analogamente, benché da millenni sia chiaro che funzioni
come l’addizione e la moltiplicazione sono effettivamente
calcolabili, solo a partire dagli anni 30 del XX secolo fu
fatto il salto concettuale per porre il problema di che cosa
non è calcolabile
ma come definire numero finito di passi?
•
il problema di definire che cosa non è calcolabile,
apparentemente futile, diviene ineludibile quando si
sospetti la non esistenza (von Neumann, 1929) di una
procedura meccanica come quella sognata di Hilbert.
•
Se la procedura esistesse, una verifica diretta ci
convincerebbe che lavora in un numero finito di passi, e
non avremmo bisogno di definire “numero di passo”
•
Ma per dimostrare che la procedura non esiste, ci vuole
una definizione assolutamente nuova...
•
come ora vedremo, la ricerca di una dimostrazione di un
risultato negativo ha prodotto una delle cose più positive
di cui disponiamo oggi
§2
il passo di
calcolo
Alan Turing 1912-1954
Enigma
la MACCHINA
DI TURING
uno stato
un altro stato
cervello con un
numero finito di
stati
un altro ancora
quaderni ad libitum
insieme finito di
simboli A, B, ..., Z
COME PROCEDE UNA MACCHINA DI TURING
T
A
C
A
G
C
T
C
G
1
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
G
C
T
C
G
1
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
G
C
T
C
G
1
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
G
C
T
C
G
1
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
G
C
T
C
G
2
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
G
C
T
C
G
2
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
G
C
T
C
G
3
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
G
C
T
C
G
3
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
T
C
T
C
G
4
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
T
C
T
C
G
4
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
T
A
C
A
T
A
T
C
G
1
-
A
C
G
T
0
HALT
HALT
HALT
HALT
HALT
1
-,<=,0
A,=>,1
C,=>,1
G,=>,2
T,=>,1
2
-,<=,0
A,=>,1
C,<=,3
G,=>,2
T,=>,1
3
4
T,=>,4
A,=>,1
questa macchina sostituisce GC con TA
parole chiave
•
finitezza: degli stati, dei simboli, del tipo di azioni, della
porzione di nastro rilevante durante il calcolo
•
località: ad ogni passo viene modificata solo la porzione
di nastro oggetto della scansione del lettore
•
infinità potenziale dell’input, del tempo e dello spazio a
disposizione, proprio come la retta, che Euclide non
descrive come entità infinita, ma come arbitrariamente
estendibile
•
•
antropomorfismo: occhi, mano, cervello, simbolo, passo
macroscopicità: quello che avviene in un calcolo è
verbalizzabile passo dopo passo, come in un processo
una macchina, un algoritmo, ma
•
in quello stesso articolo Turing descrive una macchina
U con il suo programma finito, che è in grado di
simlulare ogni macchina
•
•
è nata, matematicamente, la macchina universale
•
COMPUTER
che pochi anni dopo nascerà anche fisicamente, col
nome di
l’impatto della teoria della calcolabilità
•
il problema di Hilbert: decidere ogni problema matematico in
un numero finito di passi
•
•
•
Turing 1936: “numero finito di passi” è un concetto matematico
•
•
ma la materializzazione di U ha un effetto positivo:
•
vedremo che esiste una buona definizione di “efficiente”
esiste una macchina U capace di simularle tutte
contemplando U si ottiene una risposta negativa al problema
della decisione di Hilbert,
il computer, e quindi l’importanza di algoritmi efficienti (non
tanto “cosa possiamo calcolare” quanto “cosa possiamo
calcolare in modo efficiente”)
last, but not least,
qui abbiamo una rivoluzione
matematica
• stare a contare il numero di
“passi” nei
calcoli e nei ragionamenti
• cozza col principio
Bourbakista che tale
attività ha solo valore pratico
§3
P e NP
Ecco qui 200 numeri tra uno e un
milione, generati a caso dal computer
651789, 106737 , 549047 , 590588 , 189111 , 334832 , 664168 , 81364 , 624419 ,
737973, 873545 , 559792 , 643004 , 820024 , 461744 , 865331 , 510367 ,
675227, 353689 , 256245 , 953389 , 924572 , 525925 , 986892 , 395998 ,
802914, 453642 , 57974 , 755766 , 257215 , 977252 , 943634 , 960154 , 62604 ,
112900, 711544 , 962059 , 865516 , 624106 , 390715 , 479251 , 956418 ,
494787, 427643 , 237209 , 195559 , 712266 , 936699 , 741422 , 180394 ,
270653, 636106 , 34453 , 268619 , 154640 , 215232 , 694682 , 997579 , 160255 ,
603540, 685489 , 311714 , 503197 , 543597 , 925731 , 130972 , 81364 , 980960 ,
246087, 757874 , 113785 , 251885 , 310348 , 911910 , 14202 , 507086 , 958763 ,
521543, 747215 , 825884 , 247586 , 31167 , 87149 , 896038 , 696722 , 128184 ,
500851, 960796 , 747612 , 309093 , 530278 , 548056 , 929428 , 579874 ,
407458, 976429 , 856543 , 527658 , 31403 , 442276 , 726631 , 495074 , 65420 ,
869822, 38929 , 855607 , 761661 , 46068 , 253922 , 333916 ,
364426, 94574 , 104329 , 864189 , 829905 , 975230 , 543589 , 228939 , 119623 ,
414781, 180070 , 31044 , 751512 , 916063 , 119692 , 586026 , 964607 , 262675 ,
927807, 678508 , 866942 , 239677 , 889715 , 44069 , 400565 , 403182 , 20896 ,
897446, 791287 , 325602 , 698195 , 760643 , 4533, 375022 , 70172 , 278585 ,
434374, 439845 , 361287 , 227234 , 42067 , 716457 , 284318 , 920152 , 342427 ,
219109, 489634 , 566960 , 190650 , 625899 , 586313 , 851322 , 349578 ,
458325, 513274 , 458413 , 54285 , 155256 , 264543 , 935403 , 771700 , 795635 ,
86881, 623206 , 692723 , 817266 , 412336 , 147342 , 691355 , 438272 , 323100 ,
262429, 204178 , 824438 , 964016 , 265764 , 865808 , 655728 , 569467 ,
577996, 574447 , 382042 , 929291 , 479344 , 980752 , 386127 , 689869 ,
988139, 511037 , 139324
In un attimo il computer dà la loro somma
102443688
... il loro prodotto
381761392174366339646102372814807095012846084890740453
477505948699578076029466466860209475037663795771908685
823155493346260882729242879539830745705498194911160817
877935949924083066474283125702767433007364012013794524
930131805924827946323237421626104847383405418284097300
664285736754864813013388261791801741342161168031484852
447369462680550003611080185542210518044866284543542896
328337969412992584022030447104848065168772901232705058
027459473384011727537172971706970882752739514240358734
496443859866446039027264539271637090881719306189103372
824349021200116770425634383659079648206673424421904259
487691530535472950755612406251413388764190630548014686
685717147074196079956133388870136958788526032949314266
960122379565318227301818865654711207387929877430854521
900300497711635752380501076740715903525831450195757872
505299756182277476217106448992291841129958779170672354
194650464692161108458000959302713628461928856400394636
514002482790905213926846860206803689175712881345537908
762916694516217772347555855068177161715790159570311630
195541229502136442597487291213399976309517090553856000
000000000000000000000000000000000000
... il loro minimo comune multiplo
775411562345633118884011825279727809041947048263406633
371827088854666480491200623157399948134263471508442383
878276784487320972242032026284160746057644333275189460
902018419903148373686648347323754423487958549146783406
677446261861958729596734835420459653208469181692602894
610044782886750162031643029315735009183564028776433718
916181036909411554961087385219988961778179175453343103
102930420397909805111491496976267873779846965639944631
538092736904360691453295561868427868889149871789543098
171582898856898030823605905938673133291508218838803751
821218979892739106520639396870149779289825794237542836
591707574297713571086273497417517323960102453489279607
930643795330770260660125247766610410262407179353364463
1065344794530197318391006434719532335691345612800
...e riconosce i composti (C) e i primi (P)
C, C, C, C, C, C, C, C, P, C, C, C, C, C, C, C, C, C, C, C, C, C, C,
C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,
C, C, C, C, P, C, C, C, C, C, C, C, C, C, C, C, P, C, C, C, C, C, C,
C, C, C, C, C, C, C, C, C, C, C, C, C, P, C, C, C, C, C, C, C, C, C,
C, C, C, C, C, C, C, C, C, C, C, C, C, P, C, C, C, C, C, C, C, C, C,
C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,
C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,
C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,
C, C, C, C, C, C, C, C, C, C, C, C, P, C, C, C
sempre con questi 200 numeri
•
Vediamo se il computer risolve in fretta quest’altro
problema:
•
trova un sottinsieme di questi numeri la cui somma
faccia cento milioni
•
se i numeri rappresentano valori di francobolli, il
problema chiede:
•
un’opportuna scelta di alcuni tra questi francobolli
permette di fare un’affrancatura di cento milioni ?
•
problema KNAPSACK
perebor = ricerca esaustiva
•
non è istruttivo mettersi a tentare tutte le possibili scelte
di francobolli
•
esse sono in numero proibitivo, quanti i sottinsiemi di un
insieme con 200 elementi
•
eppure finora nessuno ha trovato alternative alla ricerca
esaustiva, per questo problema
•
qualcuno ha scoperto dei casi facili (quando i valori dei
francobolli crescono esponenzialmente, tipo 1, 10, 100,
1000, 10000,..., 10200)
•
e ha anche trovato applicazioni di questo knapsack
superincreasing, nella crittografia a chiave pubblica
•
ma il KNAPSACK resiste ad ogni attacco
Il Problema del Commesso Viaggiatore
PROBLEMA:
costruire un
algoritmo che trovi il
TOUR più breve
o, in altre parole,
scrivere un
programma che trovi
il TOUR più breve
Il Problema del Commesso Viaggiatore
Il Problema del Commesso Viaggiatore
Il Problema del Commesso Viaggiatore
Tra tutti i tour
possibili, trovare il
più corto
Il Problema del Commesso Viaggiatore: perebor
Algoritmo (ricerca esaustiva, perebor)
•Genera tutti i possibili percorsi, uno dopo
l’altro
•Via via ricorda il più corto finora ottenuto
Il Problema del Commesso Viaggiatore
Dato un input di n punti, l’algoritmo proposto
richiede di enumerare
(n-1)!
permutazioni, un numero fuori della portata di
qualsiasi calcolatore, passato, presente, o
futuro, terrestre o extra-terrestre..
We are pleased to announce the solution
of a traveling salesman problem through
15,112 cities in Germany. This is the
largest TSPLIB instance that has been
solved to date, exceeding the 13,509-city
tour through the United States that was
solved in 1998. The computation was
carried out on a network of 110
processors located at Rice University and
at Princeton University. The total
computer time used in the computation
was 22.6 years, scaled to a Compaq EV6
Alpha processor running at 500 MHz.
The optimal tour has length 1,573,084 in
the units used in TSPLIB; this translates
to a trip of approximately 66,000
kilometers through Germany.
§4
P = NP ?
definizione di P (polytime)
•
•
•
•
A un insieme finito di simboli
•
la classe di problemi polytime P, cattura la nozione di
“problema di calcolo risolvibile praticamente”
A* le possibili tuple (stringhe) di simboli di A
L un sottinsieme di A*
L è polytime se c’è una macchina T e un polinomio q
tale che per ogni x in A*, T decide entro q(|x|) passi
se x appartiene a L
esempi di algoritmi polytime
• l’addizione (linear time)
• la moltiplicazione (tempo quadratico,
migliorabile)
• trovare
il massimo comun divisore (Euclide,
tempo cubico)
• risolvere un sistema di equazioni lineari a
coefficienti e incognite razionali (Khachian)
• decidere se un numero è primo (AKS)
NP (nondeterministic polytime)
•
L è in NP se c’è un problema M in P tale che x sta in
L sse x è la metà iniziale di una tupla xy in M
•
per vedere se x sta in L dovremo faticare non poco
per indovinare un y tale che xy stia in M
•
•
ma una volta indovinato y, la verifica diviene banale
la classe di problemi NP cattura la nozione di
“problema facile da controllare, difficile da certificare”
esempi di problemi in NP
•
decidere se un numero è composto (sembrerebbe
che ci fosse da indovinare un divisore, cosa a tutt’oggi
difficilissima, ma abbiamo visto che è in P)
•
decidere se due grafi sono isomorfi (dobbiamo
indovinare un isomorfismo)
•
decidere se un sistema di equazioni lineari a
coefficienti interi ha soluzione nelle incognite 0,1
(dobbiamo indovinare una soluzione)
due importanti fatti sperimentali
•
1. I problemi in NP sono numerosissimi in tutti i campi di
applicazione
•
2. Tra questi, assai numerosi sono i problemi universali (NPcompleti), aventi la seguente proprietà
•
se un problema universale è polinomialmente risolubile,
ogni problema lo è. Viceversa, se un problema universale
non è polinomialmente risolubile, nessun problema
universale lo è.
•
(...è come se ci fosse un solo problema universale)
esempi di problemi NP-completi
• COLORABILITY: decidere se un grafo è
colorabile con k colori
• INTEGER PROGRAMMING: risolvere un
sistema di equazioni lineari a coefficienti e incognite
interi
• SATISFIABILITY: data una formula booleana
esiste un’assegnazione di valori Vero e
Falso che renda vera la formula?
F(x1, x2, ..., xn)
TRAVELING SALESMAN
input: città 1,2,...,u; lunghezza X
domanda: esiste un percorso che visiti tutte le città
in meno di X chilometri?
KNAPSACK: il problema dell’affrancatura
ET CETERA: La lista potrebbe continuare con centinaia
di problemi di economia, finanza, chimica, fisica, biologia,
ingegneria, informatica, logistica, medicina, algebra,
geometria, logica, ecc.
complessità algoritmica e tecnologia
•
•
Algoritmo = Macchina di Turing = programma
•
NOTA: quando un algoritmo A è esponenziale, l’
ordine di grandezza L(A) dei più difficili problemi
affrontabili da A esponenziale è sostanzialmente
indifferente agli sviluppi tecnologici:
•
uno speed-up di 1000 si traduce in un incremento
irrisorio del tipo L(A) —> L(A)+ 15
•
•
pensiamo al problema di fattorizzare un numero...
Costo di un algoritmo = Tempo di esecuzione del
programma, al variare della lunghezza dell’input
non così per i problemi polytime
nel 1957 Gödel chiede
a von Neumann se P=NP
ciò che non avremo mai (Turing-Church, 1936)
A1&...&An—>B
sì
programma che
decide
se esiste una
dimostrazione
di B dalle premesse Ai no
ciò che abbiamo (Gödel, 1930)
A1&...&An—>B
sì
programma che
decide
se esiste una
dimostrazione corta
di B dalle premesse Ai no
ciò che chiede il problema P/NP
A1&...&An—>B
sì
programma che
decide velocemente
se esiste una
dimostrazione corta
di B dalle premesse Ai no
l’importanza del problema P vs. NP
•
Un algoritmo efficiente per risolvere il problema
(mostrando che P=NP) avrebbe impressionanti
conseguenze pratiche di natura positiva,
•
e non solo perché si risolverebbero efficientemente
molti problemi importanti per l’industria.
•
La matematica stessa verrebbe trasformata,
permettendo al computer di trovare una prova di ogni
teorema avente una dimostrazione di lunghezza
ragionevole.
•
e questo perché le dimostrazioni formali possono
essere velocemente riconosciute
§5
Computabilità
e Fisica
(spigolature)
dettagli costruttivi
•
Finora non abbiamo accennato ai dettagli costruttivi fisici delle
macchine di Turing---se si eccettua l'osservazione che in ogni
singolo passo si ha interazione tra casella e scanner.
•
Ora, il punto di partenza di Turing era stata l'analisi del
"comportamento meccanico" di un calculator umano operante
su uno spazio finito di configurazioni.
•
Questo comportamento si presta ad una descrizione diretta e
pienamente aderente ai requisiti del rigore matematico.
•
Ma ci richiede un passo preliminare, che consiste nel sostituire
gli stati mentali con una contropartita fisica ben definita. A
questo proposito vedremo gli "stati mentali" in un'ottica diversa,
pensando ad essi non come una proprietà del calculator in
azione, ma come una porzione della configurazione su cui egli
sta operando.
sentiamo Turing nella sezione 9, III del suo lavoro classico
"On computable numbers":
E' sempre possibile per il computer interrompere il
suo lavoro, allontanarsi e scordarselo del tutto,
per poi successivamente riprenderlo. Per fare ciò
egli deve lasciare una nota di istruzioni (scritta in
qualche forma standardizzata) che spieghi come
il lavoro deve essere proseguito. Questa nota è la
controparte dello "stato della mente". Noi
supporremo che il computer lavori in modo così
saltuario da non fare più di un passo di calcolo
per sessione. La nota delle istruzioni gli deve
permettere di fare un passo di calcolo e scrivere
anche la nota di istruzioni successiva.
•
Supponiamo che la macchina operi su configurazioni
contenenti z "simboli" distinti, ognuno dei quali sia
fisicamente rappresentato, o codificato, da almeno un
atomo—un' ipotesi tutto sommato ragionevole.
•
Ci vorranno almeno z regioni disgiunte per contenere tali
codici (dei simboli). Altrimenti, per il principio di
indistinguibilità di Pauli, le nuvole elettroniche di due codici
potrebbero sovrapporsi, rendendo indistinguibili gli elettroni e i
codici stessi, e portando così letteralmente la macchina in uno
stato di "confusione mentale".
•
•
•
•
Sia c la velocità della luce;
sia a il raggio di Bohr dell'atomo di idrogeno
Sappiamo che a/c = 0,176 x 10-18 secondi.
Sappiamo che che i segnali non viaggiano più velocemente
della velocità della luce
•
Allora per contenere questi codici occorre un volume V di
almeno (4/3)πza3 metri cubi, il che comporta un diametro di
almeno 2az1/3 metri, ove diametro significa massima
distanza tra due codici in questo volume.
•
Detta f la frequenza della macchina, e notato che 1/f è il
tempo a disposizione per ciascun passo di calcolo, dal fatto
che un passo di calcolo chiama in causa l'intera
configurazione, segue che f è minore di c/(2az1/3) passi al
secondo, e dunque la quantità fz1/3 sarà minore di 2,828 x
1018 passi al secondo.
•
Questo mette in luce un'incompatibilità fondamentale tra
grandezza della memoria (=numero di codici per gli stati) e
velocità di calcolo.
•
frequenza x (memoria)1/3 < 3 x 1018 passi al secondo
•
Descrizione di una macchina di Turing G che, in meno di 60
minuti decide se una formula F con 990 variabili sia
soddisfacibile:
•
(1) G sistematicamente prova tutte le possibili n = 2990
assegnazioni di valori di verità: se trova un’assegnazione che
soddisfa F ci avvisa suonando un campanello, e poi si ferma.
•
(2) E' facile scrivere le istruzioni per G in modo che, per ogni
singola assegnazione, G decide in meno di mezz'ora se tale
assegnazione soddisfi F
•
(3) Dopo aver pensato al software, ora acceleriamo il nastro
di G, come nei vecchi film comici, in modo che la seconda
assegnazione sia esaminata in un quarto d'ora, la terza in un
ottavo d'ora,...,la n-esima in un 2n-esimo d' ora.
•
(4) E così, senza colpo ferire, G risolve il problema entro il
termine prescritto di un'ora.
G e la Fisica
Cosa c' è che non va nella macchina G ?
Supponiamo che G cali nel mondo dei sistemi
fisici reali, e come tale soddisfi queste due
condizioni:
(i) (irreversibilità temporale) il tempo non è
riciclato, ossia nessuna frazione del tempo usato
per un passo di calcolo può essere riusata per un
altro passo---questa è semplicemente una
riformulazione della sequenzialità;
(ii) (irreversibilità energetica) l'energia non è
riciclata, ossia, nessuna parte dell'energia usata
per un passo di calcolo è riusabile per un altro
passo.
G e la Fisica
•
•
Allora, detta f la frequenza di G, ossia il numero di
passi eseguiti da G in un secondo, e detta W la
potenza, misurata in watt, spesa da G (potenza =
energia al secondo), G soddisferà la diseguaglianza:
f 2 ≤ 2πW/h
•
dove h è la costante di Planck.
•
Ciò implica che la potenza assorbita da G cresce
almeno come il quadrato della frequenza.
G e la Fisica
•
•
Per vedere questo, si può ragionare così:
•
Dunque, per la diseguaglianza di Heisenberg, l'incertezza
dell'energia ∂E della casella del nastro di G deve essere
almeno eguale a h/(2π ∂t), ove ∂t = 1/f è il tempo
necessario per un passo. L'energia usata per un passo deve
esser più grande di ∂E, e la diseguaglianza segue da (i) e (ii).
•
Per quanto piccolo, il fattore h si fa sentire (ogni computer ha i
suoi ventilatori), e il limite quadratico per W può essere un
argomento contro la praticabilità di (3) per la macchina G.
La porzione di nastro sottoposta all'azione dello scanner di G
durante un singolo passo di calcolo modifica le sue proprietà
fisiche in maniera macroscopica.
l’inizio della quantum computation
• a queste considerazioni si può obiettare che
• i computer paralleli sono fatti per aggirare il
vincolo (i), e
• con
una progettazione attenta al riciclaggio
energetico si può anche aggirare
parzialmente il vincolo (ii).
• inoltre,
il principio di Heisenberg non implica
necessariamente che una quantità di energia
venga di fatto "usata" durante un passo di
calcolo—se questo passo non comporta
modificazioni “macroscopiche” del sistema
•
D. M., con W. Sieg, Computability, voce nella
Routledge Encyclopedia of Philosophy.
•
D.M. (a cura di) La Scienza dei Calcolatori, Le
Scienze Quaderni (Edizione italiana di Scientific
American) vol. 56, ottobre 1990. (Contributi di
Bennett, Landauer, Feynman, Wolfram, Rota, e altri)
•
E. Fredkin, Digital mechanics, Physica D 45 (1990)
pp. 254-270.
•
D. M., Irreversibility, Uncertainty, Relativity and
Computer Limitations, Il Nuovo Cimento, Europhysics
Journal, 61 B, n.2 (1981) pp. 297-305.
•
D.M., Natural limitations of decision procedures for
arithmetic with bounded quantifiers, Archiv für math.
Logik und Grundlagenforschung, 23 (1983) pp. 37-54.