Ngôn ngữ không thể quyết định

Đối với một ngôn ngữ không thể quyết định, không có Máy Turing nào chấp nhận ngôn ngữ đó và đưa ra quyết định cho mọi chuỗi đầu vào w(TM có thể đưa ra quyết định cho một số chuỗi đầu vào). Một vấn đề quyết địnhP được gọi là "không thể quyết định" nếu ngôn ngữ L trong số tất cả các trường hợp có cho Pkhông phải là quyết định. Các ngôn ngữ không thể quyết định không phải là ngôn ngữ đệ quy, nhưng đôi khi, chúng có thể là ngôn ngữ có thể liệt kê một cách đệ quy.

Thí dụ

• Sự cố dừng của máy Turing
• Vấn đề tử vong
• Bài toán ma trận sinh tử
• Vấn đề về thư từ, v.v.