TecaLibri: David Harel: Computer a responsabilità limitata

| << | < | > | >> |

Pagina 44

In definitiva, la macchina piú potente a noi nota, dotata dei linguaggi di programmazione piú avanzati, non sa fare nulla piú di quanto sappia fare un piccolo computer portatile con un linguaggio elementare; peggio: non piú di quanto sia in grado di fare il non plus ultra della semplicità e della rozzezza, la macchina di Turing. I problemi non computabili (o indecidibili) come quello del ricoprimento non possono essere comunque risolti, né dal supercomputer né dalla macchina di Turing; quelli computabili (o decidibili), come l'ordinamento di parole o il test sui numeri primi, sono risolubili da parte di qualsiasi macchina. Tutto ciò, badate bene, a condizione che il tempo e la memoria a disposizione non siano un problema, cioè siano virtualmente illimitati.

Questo significa che la classe dei problemi algoritmici computabili, effettivamente risolubili o decidibili è in realtà molto ben definita, perché non dipende dal tipo di computer, dal sistema operativo, dal linguaggio di programmazione, dai metodi di sviluppo del software e cosí via. Chi vuole spingere per l'adozione di una particolare architettura hardware o di un software deve avere ottime ragioni per farlo, che vanno oltre le potenzialità di calcolo, perché tutto ciò che si può fare con il nuovo sistema si può fare con altri, anche con le primitive macchine di Turing o con i formalismi di Church, Post, Kleene e altri ancora.

Il fatto che tutti questi ricercatori, armati di diversi strumenti concettuali, siano arrivati alla stessa idea (aggiungerei: molto prima della costruzione materiale del primo computer!) è un segnale di quanto questa tesi sia profonda. Erano tutti a caccia dello stesso risultato e ci sono arrivati con soluzioni diverse ma equivalenti: questo ci giustifica nell'estendere l'equivalenza anche alla nozione intuitiva di calcolabilità effettiva. Da qui la tesi di Church-Turing.

Se per il momento tralasciamo il problema dell'efficienza, cioè non ci curiamo di quanto tempo e spazio siano effettivamente necessari a un algoritmo, possiamo giustificare pienamente la netta separazione delineata nella figura 2.1. Nel prosieguo, visto ciò che abbiamo mostrato, possiamo tranquillamente riferirci al nostro computer preferito (il Comp di prima), dotato del linguaggio che piú ci piace (il Lang), come modello per la risoluzione dei problemi algoritmici: tanto non c'è nessuna differenza con gli altri! Comunque, è intellettualmente stimolante pensare che anche il piú semplice di tutti questi modelli, la macchina di Turing, sa fare esattamente ciò che fanno gli altri.

| << | < | > | >> |

Pagina 56

Concludendo, abbiamo visto che il mondo dei problemi algoritmici si divide in due grandi categorie: quelli decidibili (o computabili) e quelli indecidibili (o non computabili), e che all'interno della seconda classe esistono vari livelli di intrattabilità. Abbiamo anche visto che questa classificazione è estremamente ben posta e fondata: le linee di confine nella figura 2.9 sono ben nette, matematicamente definite e indifferenti all'uso di vari modelli computazionali, linguaggi di programmazione, hardware o software.

Quindi i sogni di onnipotenza dei computer vanno in frantumi. Ora sappiamo che le macchine non sono in grado di risolvere tutti i problemi algoritmici, anche fornendo loro risorse illimitate di tempo e di memoria.

Potremmo finire qui, visto che queste sono le pessime notizie a cui alludevo nella Prefazione. O c'è dell'altro?

| << | < | > | >> |

Pagina 107

Capitolo quinto

Cure palliative

Le cattive notizie che arrivano dal mondo dei computer hanno spinto gli esperti a investigare in varie direzioni alla ricerca di modi per alleviare il dolore. In questo capitolo affronteremo le scoperte piú interessanti nel settore: il calcolo parallelo (o concorrente), la randomizzazione, la computazione quantistica e il calcolo molecolare. I primi due settori di ricerca si basano su paradigmi algoritmici del tutto nuovi, ottenuti mettendo in dubbio alcuni fatti che il calcolo tradizionale dà per scontati; il terzo trasferisce il processo di computazione all'interno dello strano mondo della meccanica quantistica, mentre il quarto cerca addirittura di usare le molecole come calcolatori.

| << | < | > | >> |

Pagina 108

Per quel che riguarda la randomizzazione, possiamo fare un'analogia con la roulette russa. Anche se c'è chi pensa che le probabilità di essere uccisi in questo «gioco» siano basse, la maggior parte di noi non accetterebbe mai di parteciparvi. Bene, ma proviamo a immaginare di avere una pistola con 2^200 pallottole invece delle solite sei. Con un semplice calcolo si può verificare che, in termini di rischio, questa versione del gioco è equivalente a 77 versioni standard: in altre parole, la probabilità di venire uccisi con la pistola dalle 2^200 pallottole è uguale a quella di venire colpiti 77 volte di seguito con la normale pistola da 6 pallottole. È una probabilità minuscola, molto piu piccola di quella di morire accidentalmente dopo aver bevuto un bicchiere d'acqua o aver fatto un respiro profondo. Se per qualche motivo siete costretti a giocare a una roulette russa con 2^200 pallottole, non dovete preoccuparvi: la possibilità di una catastrofe è indicibilmente bassa.

Con la randomizzazione permettiamo agli algoritmi di affidarsi al caso lanciando una monetina (o premendo un grilletto, se preferite) di tanto in tanto durante l'esecuzione del programma. Le conseguenze di questa tecnica sono sorprendenti: invece di portare al caos e all'imprevedibile, l'introduzione della casualità può essere molto utile e può condurre velocemente a soluzioni che si trovano in modo assai meno efficiente con metodi convenzionali. Il prezzo da pagare è la possibilità di errore, ma è una evenienza che può essere tranquillamente ignorata, come per la roulette russa nel caso esteso.

La computazione quantistica è un campo di ricerca nuovo di zecca, che si basa su quella straordinaria e paradossale invenzione del XX secolo che è la meccanica quantistica. A oggi, sono stati scoperti alcuni algoritmi sorprendentemente efficienti per casi intrattabili in senso classico; il problema è che la loro effettiva implementazione richiederebbe la costruzione di un computer quantistico, impresa per ora lontana dall'essere compiuta.

Infine, con la computazione molecolare (altra scoperta molto recente) si è riusciti a sfruttare un particolare solvente molecolare per risolvere alcune istanze di problemi NP-completi, il che ha fatto intravedere nuovi interessanti sviluppi.

In questo capitolo parleremo di tutto ciò con vari livelli di approfondimento. Visto, però, che ci stiamo concentrando sulle cattive notizie, cercheremo soprattutto di capire se questi modi cosi disinvolti di risolvere i problemi ci facciano superare i limiti intrinseci visti finora.

| << | < | > | >> |

Indice

| << | < | > | >> |

Pagina 44

| << | < | > | >> |

Pagina 56

| << | < | > | >> |

Pagina 107

| << | < | > | >> |

Pagina 108

| << | < |