अनिर्दिष्ट भाषाएँ

एक अपरिहार्य भाषा के लिए, कोई ट्यूरिंग मशीन नहीं है जो भाषा को स्वीकार करती है और हर इनपुट स्ट्रिंग के लिए निर्णय लेती है w(TM हालांकि कुछ इनपुट स्ट्रिंग के लिए निर्णय ले सकता है)। एक निर्णय समस्याP अगर भाषा को "अनिर्वचनीय" कहा जाता है L के सभी हाँ उदाहरण के लिए Pपर्णपाती नहीं है। अनिर्दिष्ट भाषाएं पुनरावर्ती भाषा नहीं हैं, लेकिन कभी-कभी, वे पुनरावर्ती भाषाएं हो सकती हैं।