रैम मशीन एमुलेटर

रैम मशीन एक अमूर्त ट्यूरिंग कंप्यूटर है जो रजिस्टर मशीनों के वर्ग से संबंधित है। यह एक सार्वभौमिक ट्यूरिंग मशीन के बराबर है, और एल्गोरिदम की शुद्धता को साबित करने के लिए अधिक दृश्य और सुविधाजनक है। इस विषय में मैं आपको बताऊंगा कि यह कैसे व्यवस्थित है और कुछ दिलचस्प उदाहरणों के साथ PAM मशीन एमुलेटर के कार्य कार्यान्वयन के लिए लिंक संलग्न करता है।

रैम मशीन का एक सार मॉडल (RAM: रैंडम एक्सेस मशीन) में रजिस्टरों का एक अनंत सेट शामिल होता है, जिनमें से प्रत्येक किसी भी लम्बाई के पूर्णांक को संग्रहीत करने में सक्षम होता है। रजिस्टर इंडेक्स किसी भी पूर्णांक (ऋणात्मक सहित) हो सकता है। रैम मशीन के लिए एक कार्यक्रम - निर्देशों का एक सीमित सेट जो स्मृति रजिस्टरों को संशोधित करता है; आप इसे एक बहुत ही सरल कोडांतरक के रूप में देख सकते हैं। हम कमांड के एक सेट पर विचार करके मशीन का अध्ययन शुरू करते हैं।

पड़ाव

एक मशीन को उस तक पहुंचने पर निष्पादन को रोकने का निर्देश देने वाला सबसे सरल निर्देश।

पढ़ें

मशीन को I / O का समर्थन करना चाहिए, और READ ऑपरेशन को कीबोर्ड (या किसी अन्य स्ट्रीम) से एक संख्या दर्ज करने के लिए डिज़ाइन किया गया है, हालांकि, यह मत भूलो कि हम एक सार मॉडल के साथ काम कर रहे हैं, जहां मुख्य बात एल्गोरिथ्म के लिए डेटा इनपुट प्रदान करना है ताकि एक बड़ी समस्या हल हो सके)। संख्या रजिस्टर [0] में दर्ज की जाती है, इस रजिस्टर को "विशेष" माना जाता रहेगा।

लिखें

प्रदर्शित करता है (स्क्रीन पर) [0] में संग्रहीत संख्या। और कोई तर्क नहीं।

लोड एक्स / [x] / [[x]]

एक पेचीदा निर्देश - एक मनमाना मूल्य लिखता है [0] । उदाहरण के लिए मान स्थिर सेट किया जा सकता है: LOAD 5 ,। या किसी अन्य सेल से कॉपी किया गया: LOAD [3] - यहां तीसरे रजिस्टर से मूल्य को शून्य पर कॉपी किया गया है। या दोहरे पते की सहायता से: LOAD [[3]] - जिस रजिस्टर से तीसरा रजिस्टर "संदर्भित" होता है वह संख्या "शून्य" तक गिर जाएगी। इस प्रकार, यह देखा जा सकता है कि मशीन अप्रत्यक्ष रूप से संबोधित करने का समर्थन करती है।

स्टोर [x] / [[x]]

एक मान निर्दिष्ट सेल में [0] से लिखता है। या तो प्रत्यक्ष संबोधन उपलब्ध है: STORE [1] या अप्रत्यक्ष संबोधन: STORE [[1]] ।

NEG

एक संख्या का संकेत देता है [0] । तदनुसार, -3 को 3 बदल दिया जाएगा, संकेत में शून्य नहीं है।

LSHIFT x / [x] / [[x]]

निर्दिष्ट तर्क द्वारा [0] पर संख्या की एक बिटवाइड बाईं पारी करता है; उपलब्ध निरंतर, प्रत्यक्ष पता, अप्रत्यक्ष पता। उदाहरण के लिए, LSHFIT [[3]] में संदर्भित मूल्य के रजिस्टर की शक्ति में मूल्य को दो से गुणा करता है [3] ।

RSHIFT x / [x] / [[x]]

एलएसएचआईएफटी के समान एक बिटवाइज़ राइट शिफ्ट, तर्क और अर्थ करता है। क्लासिक मॉडल एलएसएचआईएफटी / आरएसआईआईएफटी के तर्क के रूप में हस्ताक्षरित संख्याओं के उपयोग की अनुमति नहीं देता है।

ADD x / [x] / [[x]]

फ़ंक्शन तर्क द्वारा निर्दिष्ट मान [0] को जोड़ता है। उपलब्ध निरंतर, प्रत्यक्ष संबोधित, अप्रत्यक्ष।

और अंत में, यह साइकिल और परिस्थितियों के आयोजन के लिए उपयोगी है:

JUMP टैग

कोड या लेबल की निर्दिष्ट लाइन पर बिना शर्त कूदना।

JG टैग

निर्दिष्ट लेबल पर जाएं यदि शून्य रजिस्टर में मूल्य सख्ती से सकारात्मक है।

वह सब है!

लेकिन अन्य अंकगणितीय संचालन के बारे में क्या? हां, शास्त्रीय मॉडल निरर्थक निर्देश नहीं देता है, इसलिए उन्हें इसके अलावा लागू करना होगा। एक छोटी पहेली के रूप में, मैं इसे लागू करने का प्रस्ताव देता हूं:

• n से गुणा करना ( O से अधिक (अधिकतम (m, n)) );
• वर्ग मीटर ( O (m) की तुलना में तेज़);
• डिग्री मी ( ओ से अधिक (एम * लॉग (एम)) );
• एक मनमाना डिग्री की जड़ (न्यूटन की विधि को याद करें)।

एक अधिक कठिन कार्य को प्रत्येक पद्धति के कार्यान्वयन की जटिलता और शुद्धता का प्रमाण माना जा सकता है (लेकिन यहां ट्यूरिंग मशीन की तुलना में यह बहुत सरल है)।

मशीन के सबसे सरल गुणों में से एक डेडलॉक स्टेट (स्थिर बेकार अवस्था) का पता लगाने में आसानी होती है: यदि, उसी लेबल पर स्विच करते समय, रजिस्टर मान समान रहे, तो हम "त्रिशंकु" हो गए।

मैं एक साधारण प्रोग्राम का उदाहरण संलग्न कर रहा हूं (मुझे आशा है, स्व-स्पष्ट है) कि कीबोर्ड से एन नंबर दर्ज किए गए हैं (एमुलेटर निष्पादन योग्य फ़ाइल के साथ संग्रह में अन्य उदाहरण):



कुछ प्रकार के लिए (ईमानदारी से, शुरू में, स्कूल में बच्चों को "मनोरंजन" करने के लिए) मैंने ग्राफिक तत्वों को खींचने के लिए कुछ आदिम (डॉट और लाइन) जोड़े हैं जो कुछ मज़ेदार बना सकते हैं। उदाहरण के लिए:



आप इस लिंक द्वारा कार्यान्वयन को डाउनलोड कर सकते हैं, और स्रोत - यहाँ । स्रोत कोड की गुणवत्ता, साथ ही जिस भाषा में वे लिखे गए हैं (हाँ, यह डेल्फी है), बहुत दोषपूर्ण नहीं होना चाहिए, मैंने उन्हें कई साल पहले लिखा था और मुझे खुद आश्चर्य है कि सब कुछ काम करता है। कार्यान्वयन लंबे अंकगणित का समर्थन करता है और एक अनंत संख्या में रजिस्टरों का अनुकरण करता है, हालांकि हम जानते हैं कि भौतिक मशीन की मेमोरी नहीं है :)

सौभाग्य की कोशिश!