मैथमैटिका इटर्ना
खुला एक्सेस

अमूर्त

ट्यूरिंग मशीन संगणनाओं को समझने के तरीके

जॉन निक्सन

यह शोधपत्र ट्यूरिंग मशीन (TM) व्यवहार का वर्णन करने के तरीकों की एक प्रारंभिक जांच है। यह दिखाया गया है कि टेप की एक सीमित लंबाई तक सीमित TM के लिए परिणामों का उपयोग किसी भी TM गणना को गति देने के लिए कैसे किया जा सकता है। ऐसे नियमों के गैर-अनावश्यक सेट को अपरिवर्तनीय नियमित (गणना) नियम (IRR) के रूप में संदर्भित किया जाता है और टेप की एक मनमानी लंबाई के लिए किसी भी TM के लिए उन्हें उत्पन्न करने के लिए एक एल्गोरिथ्म का वर्णन किया गया है। इस एल्गोरिथ्म को C++ में लागू किया गया है क्योंकि यह स्वतंत्र रूप से उपलब्ध है। अध्ययन किए गए उदाहरण दिखाते हैं कि IRR संख्या में परिमित या अनंत हो सकता है। कई TM के लिए जब वे अनंत होते हैं, तो उनके लिए पुनरावर्ती सूत्र पाए गए और यह उम्मीद की जाती है कि यह हमेशा संभव है। ये सूत्र प्रत्येक उदाहरण में IRR की अलग-अलग जांच करके और इसे सही ढंग से अनुमान लगाकर और प्रेरण द्वारा इसे साबित करके पाए गए। एक तालिका जो दिखाती है कि अगले प्रतीक पर निर्भर करते हुए कौन सा IRR दूसरों का अनुसरण करता है, अध्ययन किए गए उदाहरणों के लिए पाया गया और TM व्यवहार पर बहुत जानकारी देता है। यह अनुमान लगाया जा रहा है कि इस तरह से सार्वभौमिक टीएम का विश्लेषण करना संभव होगा, ताकि यह पता लगाया जा सके कि व्याख्या चक्र किस प्रकार काम करता है।