Computer e problemi

Esistono dei problemi che non possono essere risolti da nessun computer, esistente o futuro?

Malgrado la comune convinzione che con i calcolatori si possa "fare tutto", esistono situazioni che essi non sono in grado di trattare. Ci sono dei problemi che, con sorpresa di molti, i computer non sanno risolvere. Non solo questi problemi non sono risolubili con i calcolatori di oggi: siamo sicuri che ogni computer, anche in futuro, non sarà in grado di affrontarli con successo.

Prima di presentare uno di questi problemi, di seguito e nelle pagine successive, faremo un piccolo viaggio tra altri problemi, computer e metodi di soluzione.

Un solitario di ricoprimento
Consideriamo un gioco ad un solo giocatore, che consiste nel disporre su un piano delle piastrelle secondo certe regole.
Abbiamo a disposizione delle piastrelle quadrate, ciascuna divisa in quattro spicchi dalle due diagonali. Ogni spicchio è colorato e l'assegnazione dei colori agli spicchi è molto varia. Ad esempio, potremmo avere piastrelle di questi tre tipi:

Fig. 1: Tre tipi di piastrelle

Oppure potremmo avere piastrelle di questi altri tipi:

Fig. 2: Altri tre tipi di piastrelle

Fissato l'insieme dei tipi di piastrelle, il gioco consiste nel piastrellare una stanza assegnata (di dimensione e forma fissate, con l'unico vincolo di essere multipli di una piastrella), usando quante piastrelle si vogliano e con qualsiasi orientamento, ma solo dei tipi fissati e con il seguente vincolo:

due piastrelle possono stare una accanto all'altra solo se i colori sul bordo comune coincidono.

La soluzione del gioco consiste nel determinare (SI/NO) se i tipi di piastrelle fissati all'inizio sono in grado di ricoprire correttamente la stanza assegnata.

C'è un metodo concettualmente molto semplice per risolvere il gioco: provare tutte le possibili combinazioni di piastrelle. Possiamo farci aiutare da un computer: anche con esso ci vorrà parecchio tempo (se la stanza ha le dimensioni di qualche centinaio di piastrelle, potrebbero volerci anni, anche con un computer molto veloce), ma, prima o poi, saremo in grado di rispondere SI o NO al problema iniziale.


Fig. 3: Tre ricoprimenti del piano dell'artista M. C. Escher Credit: (M.C. Escher)

The Webweavers: Last modified Mon, 23 Jan 2006 14:09:35 GMT