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

La gigantesca CEP e il piccolo Tiquit sono molto simili, come calcolatori. 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 macchina e possono quindi eseguire entrambi gli stessi algoritmi.

È possibile dimostrare che:

ogni problema risolubile 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?