ภาษาที่ไม่สามารถตัดสินใจได้

สำหรับภาษาที่ไม่สามารถตัดสินใจได้จะไม่มี Turing Machine ที่ยอมรับภาษาและทำการตัดสินใจสำหรับทุกสตริงอินพุต w(TM สามารถตัดสินใจสำหรับสตริงอินพุตบางตัวได้) ปัญหาในการตัดสินใจP เรียกว่า "ไม่สามารถตัดสินใจได้" หากเป็นภาษา L จากทุกกรณีที่ใช่ Pไม่สามารถตัดสินใจได้ ภาษาที่ไม่สามารถตัดสินใจได้ไม่ใช่ภาษาที่เรียกซ้ำได้ แต่ในบางครั้งอาจเป็นภาษาที่นับซ้ำได้

ตัวอย่าง

• ปัญหาการหยุดชะงักของเครื่องทัวริง
• ปัญหาการตาย
• ปัญหาเมทริกซ์มรรตัย
• ปัญหาการโพสต์การติดต่อ ฯลฯ