ट्यूरिंग मशीन हाल्टिंग की समस्या

Input - एक ट्यूरिंग मशीन और एक इनपुट स्ट्रिंग w।

Problem - क्या ट्यूरिंग मशीन स्ट्रिंग की कंप्यूटिंग खत्म कर देती है wचरणों की एक सीमित संख्या में? इसका उत्तर हां या ना में होना चाहिए।

Proof- सबसे पहले, हम मानेंगे कि इस समस्या को हल करने के लिए इस तरह की एक ट्यूरिंग मशीन मौजूद है और फिर हम दिखाएंगे कि यह खुद के विपरीत है। हम इस ट्यूरिंग मशीन को ए कहेंगेHalting machineजो एक परिमित मात्रा में 'हां' या 'नहीं' का निर्माण करता है। यदि रुकने की मशीन एक निश्चित समय में खत्म हो जाती है, तो आउटपुट 'हां' के रूप में आता है, अन्यथा 'नहीं' के रूप में। हॉल्टिंग मशीन का ब्लॉक डायग्राम निम्नलिखित है -

अब हम एक डिजाइन करेंगे inverted halting machine (HM)’ के रूप में -

• अगर H यस लौटाता है, तो हमेशा के लिए लूप।

• अगर H NO लौटाता है, फिर रुक जाता है।

'इनवर्टेड हॉल्टिंग मशीन' का ब्लॉक डायग्राम निम्नलिखित है -

आगे, एक मशीन (HM)₂ किस इनपुट का निर्माण निम्न प्रकार से किया जाता है -

• यदि (एचएम) इनपुट पर ₂ स्टॉप, लूप हमेशा के लिए।
• एल्स, हाल्ट।

यहां, हमें एक विरोधाभास मिला है। इसलिए, रोकने की समस्या हैundecidable।