algoritmi,programmi,calcolatori indice: il computer è onnipotente? piastrellare una stanza qualsiasi

Cosa hanno in comune la CEP e Tiquit?

 

Fig. 1: L'elefante (CEP) e il topolino (Tiquit).

 

La gigantesca CEPDizionario e il piccolo TiquitDizionario sono molto simili, come calcolatoriDizionario. L'una era lenta e pesante, mentre l'altro è leggero e velocissimo. Ma entrambi hanno la stessa struttura logica: sono in grado di compiere le principali operazioni aritmetiche e di organizzarle in una successione controllata da determinate condizioni. Entrambi eseguono programmi scritti nel relativo linguaggio macchinaDizionario e possono quindi eseguire entrambi gli stessi algoritmiDizionario.

È possibile dimostrare che:

ogni problema risolubileDizionario dalla CEP è risolubile anche da Tiquit e viceversa. Cambia il tempo di calcolo, ma non la capacità risolutiva dei due calcolatori. Lo stesso accade per ogni calcolatore esistente (ed anche futuro, almeno per come li conosciamo).

Possiamo allora dire che un problema è C-risolubile se esiste un programma (per qualche calcolatore) che lo risolve.

Ci domandiamo dunque:

  • quali problemi sono C-risolubili?
     
  • esistono problemi non C-risolubili?

 

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