È un modo per dimostrare che alcuni linguaggi non sono decidibili.

Consideriamo le che calcolano funzioni (input su nastro, calcolo della funzione nell’esecuzione, output su un nastro qualsiasi).

è calcolabile se si ferma con sul nastro.

Un linguaggio è riducibile mediante una funzione al linguaggio (si denota con , sta per mapping) se . Le cardinalità degli insiemi e possono differire perchè la mappa non è biunivoca.