Il nostro viaggio era iniziato con un semplice solitario:

• Abbiamo a disposizione quante piastrelle vogliamo, ma tutte di una serie di tipi fissati, per esempio:

Fig. 1: Tre tipi di piastrelle

oppure:

Fig. 2: Altri tre tipi di piastrelle

• Fissato l'insieme dei tipi di piastrelle, il gioco consiste nel ricoprire una stanza assegnata (di dimensione e forma fissate, ma arbitrarie), usando quante piastrelle si vogliano e con qualsiasi orientamento, ma solo dei tipi fissati e con il vincolo che due piastrelle possono stare una accanto all'altra solo se i colori sul bordo comune coincidono.

Il gioco non è concettualmente difficile, fissata la stanza. E non c'è bisogno di un grande ragionamento per convincersi che un calcolatore (o anche ciascuno di noi) è in grado di risolverlo, avendo abbastanza tempo e provando tutte le combinazioni. Si tratta dunque di un problema C-risolubile.

Adesso proponiamoci un problema simile, solo più generale.

	Fig. 3: Oggetti impossibili: risolvere con un calcolatore un problema non C-risolubile è impossibile quanto realizzare uno di questi oggetti.

Fissato l'insieme dei tipi di piastrelle, questi tipi sono sufficienti a ricoprire una stanza qualsiasi?
Ora il procedimento di forza bruta, che prova tutti i casi, non è più possibile, perché esistono infinite stanze, di infinite forme e dimensioni.

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 che, presi come dati iniziali i tipi di piastrelle ammesse, dopo un certo tempo si ferma rispondendo SI nel caso in cui quei tipi di piastrelle siano sufficienti a piastrellare una stanza qualsiasi, oppure si ferma rispondendo NO nel caso in cui esista una stanza che non è possibile ricoprire con quei tipi di piastrelle?

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.