![]() ![]() ![]() Piastrellare una stanza qualsiasiIl nostro viaggio era iniziato con un semplice solitario:
Il gioco non è concettualmente difficile, fissata la stanza. E
non c'è bisogno di un grande ragionamento per convincersi che un
calcolatore Adesso proponiamoci un problema simile, solo più generale.
Fissato l'insieme dei tipi di piastrelle, questi tipi sono sufficienti a
ricoprire una stanza qualsiasi? Mediante una non semplice dimostrazione matematica, ad esempio, si può mostrare che il primo insieme di piastrelle di Fig. 1 non è sufficiente (cioè esistono stanze che non possono esser piastrellate con solo quei tipi di colori), mentre con il secondo insieme di Fig. 2 è possibile ricoprire il pavimento di una qualsiasi stanza. La domanda che ci interessa è se un calcolatore possa risolvere questo problema di ricoprimento generale. Formuliamo la domanda in modo diretto. Esiste un
algoritmo Ebbene, non esiste alcun algoritmo in grado di rispondere a questa domanda. E non per nostra incapacità, ma perché si tratta in un problema intrinsecamente irresolubile per via algoritmica.
The Webweavers: Last modified Mon, 23 Jan 2006 14:09:35 GMT |