Bahasa yang tidak dapat diputuskan

Untuk bahasa yang tidak dapat diputuskan, tidak ada Mesin Turing yang menerima bahasa tersebut dan membuat keputusan untuk setiap string input w(TM dapat membuat keputusan untuk beberapa string input). Masalah keputusanP disebut "tidak dapat diputuskan" jika bahasa tersebut L dari semua contoh ya untuk Ptidak bisa diputuskan. Bahasa yang tidak dapat diputuskan bukanlah bahasa rekursif, tetapi terkadang, mereka mungkin merupakan bahasa yang dapat dihitung secara rekursif.

Contoh

• Masalah terputusnya mesin Turing
• Masalah kematian
• Masalah matriks fana
• Masalah Post korespondensi, dll.