गैर-नियतात्मक ट्यूरिंग मशीन
एक गैर-नियतात्मक ट्यूरिंग मशीन में, प्रत्येक राज्य और प्रतीक के लिए, टीएम हो सकने वाली क्रियाओं का एक समूह होता है। तो, यहाँ संक्रमण निर्धारक नहीं हैं। गैर-नियतात्मक ट्यूरिंग मशीन की गणना विन्यास का एक पेड़ है जिसे प्रारंभ कॉन्फ़िगरेशन से पहुँचा जा सकता है।
एक इनपुट को स्वीकार किया जाता है यदि पेड़ का कम से कम एक नोड होता है जो एक कॉन्फ़िगरेशन स्वीकार करता है, अन्यथा यह स्वीकार नहीं किया जाता है। यदि कम्प्यूटेशनल ट्री की सभी शाखाओं को सभी इनपुट पर रोक दिया जाता है, तो गैर-निर्धारक ट्यूरिंग मशीन को कहा जाता हैDecider और अगर कुछ इनपुट के लिए, सभी शाखाओं को अस्वीकार कर दिया जाता है, तो इनपुट भी खारिज कर दिया जाता है।
एक गैर-नियतात्मक ट्यूरिंग मशीन को औपचारिक रूप से 6-ट्यूपल (Q, X, δ,,, q 0 , B, F) के रूप में परिभाषित किया जा सकता है , जहां -
Q राज्यों का एक समुच्चय है
X टेप वर्णमाला है
∑ इनपुट वर्णमाला है
δ एक संक्रमण समारोह है;
X: Q × X → P (Q × X × {Left_shift, Right_shift})।
q0 प्रारंभिक अवस्था है
B रिक्त प्रतीक है
F अंतिम राज्यों का सेट है