असीमित क्षमता की कोशिकाओं के साथ टेप पर ब्रेनफक

एक ऐसी मशीन लें जिसका कमांड सिस्टम ठीक उसी तरह है जैसे ब्रेनफैक भाषा में, लेकिन जो एक टेप पर चलती है, जिसकी कोशिकाओं में आप किसी भी पूर्णांक को रख सकते हैं। अंकगणित संचालन में अतिप्रवाह नहीं होता है, सकारात्मक संख्या पर लागू "+" कमांड हमेशा सकारात्मक परिणाम देगा, आदि। सवाल यह है कि क्या ऐसी मशीन पर काम करना संभव है, क्या समस्याएं पैदा होंगी और उनके आसपास कैसे पहुंचेंगी?

लाभ स्पष्ट हैं: चूंकि कोई अतिप्रवाह नहीं हैं, तो लंबे अंकगणित की आवश्यकता नहीं है, आप किसी भी लंबाई के सरणियों के साथ समान रूप से काम कर सकते हैं, आदि। लेकिन बहुत जल्दी, हम देखते हैं कि एक सेल ("[-]") को खाली करने का हमारा पसंदीदा तरीका काम नहीं करता है: यदि सेल में एक नकारात्मक मूल्य था, तो प्रोग्राम लूप होगा। इसी तरह, हम कॉपी कमांड "[-> + <] का स्वतंत्र रूप से उपयोग नहीं कर सकते हैं - यह केवल गैर-नकारात्मक संख्याओं के लिए भी काम करता है।

यह पता चला है कि प्रोग्रामिंग के दौरान हमें कोशिकाओं की सामग्री के संकेतों को ध्यान से देखने की आवश्यकता है (सबसे आसान तरीका यह है कि नकारात्मक संख्याओं को दिखने से रोका जाए), और यदि कोई संख्या दिखाई देती है जिसका संकेत अज्ञात है, तो उसके साथ एक विशेष तरीके से काम करें।

यहाँ हम दो कार्यों पर विचार करते हैं: सबसे पहले, हम ऑपरेटर को "if (a> b) C; और डी; "जहां ए और बी गैर-नकारात्मक हैं, और सी और डी कुछ क्रियाएं हैं, और दूसरी बात, हम सीखेंगे कि एक मनमानी संख्या के संकेत को शून्य, कॉपी और निर्धारित कैसे करें।

सशर्त कथन।

तो, टेप पर दो गैर-नकारात्मक संख्याएं लिखी गई हैं a और b (जिसमें कोशिकाएं हम खुद को चुनते हैं)। हमें इन नंबरों की तुलना करने और प्रदर्शन करने की आवश्यकता है, परिणाम के आधार पर, उपयोग की जाने वाली क्रियाओं में से एक C या D. सभी सेल (जिनमें ए और बी स्थित थे) को रीसेट किया जाना चाहिए।
हम ऑपरेटर को इस रूप में लिखते हैं:

 एच 1 है;  जबकि (h) {if (a == 0) {D;  a = b = 1;  एच 0 है;  } अगर (b == 0) {C;  a = b = 1;  एच 0 है;  } ए -;  b--;  } 

यदि एक और बी गैर-ऋणात्मक थे, तो ऐसे कार्यक्रम में नकारात्मक संख्या दिखाई नहीं दे सकती है। ऑपरेटर को लागू करने के लिए अगर (a == 0) बी; टेप पर 4 कोशिकाओं "0 0 1 0" का एक ब्लॉक बनाएं और कमांड्स "[>] >> [B>]" पर अमल करें। यदि शुरुआत में गाड़ी ब्लॉक की पहली सेल पर थी, तो अंत में यह किसी भी अवतार में अपने 4 वें सेल पर होगी।

कार्यक्रम इस तरह दिखाई देगा (हम मानते हैं कि गाड़ी और नंबर "a" सेल 0 में हैं, और नंबर "b" सेल 4 में है):

 >> + [
   << [>] >> [C - << + >>>> [-] + <]
   > [<] << [D - >> + <<<< [-] +>]
   <-> >>> - <<]

चर एच के रूप में, ब्लॉक "एक 0 1 0 बी" से एकता का उपयोग किया जाता है - वैसे भी, इसे रीसेट करने के बाद, कोई प्रभावी तुलना नहीं होगी।

आप इसे लिखकर कार्यक्रम को थोड़ा सरल कर सकते हैं

 एच 1 है; 
 जबकि (ए) {
   if (b == 0) {C;  a = b = 1;  एच 0 है;  }
   एक--;  b--;
 }
 if (h) {D;  एच = बी = 0;  }

यह बाहर हो जाएगा

 >>> + <<<
 [> [>] >> [C - << + <-] + >>>>]
   <<< - <-]
 > [-] >> [D-]

प्रोग्राम रनटाइम अधिकतम (ए, बी) से रैखिक है।

अज्ञात हस्ताक्षर संख्या

टेप पर संख्या को लिखे जाने दें, जिसके बारे में हम नहीं जानते कि यह सकारात्मक है या नकारात्मक। हमें इसकी आवश्यकता है: (1) इसे शून्य करें, (2) इसे दूसरे सेल में कॉपी करें, और (3) ए एफ 0 यदि एक्शन एफ करें। हम तीनों समस्याओं को एक साथ हल करेंगे।

उन्हें कैसे हल करें? लगभग उसी तरह जब हम ट्यूरिंग मशीन के टेप पर एक गैर-शून्य सेल की तलाश करते हैं, जब तक हम 1:

 अगर (क) {
   x 1 है;
   जबकि (x) {
     y = 2 * x;
     जबकि (x) {
       एक्स-;  ए ++;  b--;
       if (a == 0) x = y = 0;
     }
     x = 2 * y;
     जबकि (y) {
       y--;  एक--;  बी ++;
       अगर (a == 0) {एफ;  x = y = 0;  }
     }
   }
 }  

चर को b से कॉपी किया जाएगा, और F तभी क्रियाशील होगा, जब किसी का प्रारंभिक मान धनात्मक था। BF में अनुवाद:

 [>> + <<<<< +
   [[- <++ >> + <]>
     [-> -> + [>] >>
       [- <<<< [-] << [-]
       <<<<<]
     << [-> ++> + <<] >>
     [-> +> - [>] >>
       [एफ - <<<< [-] <[-]]
       <<<<<]
     <]]

संचालन समय भी एब्स (ए) से रैखिक है। यहां यह ध्यान दिया जाना चाहिए कि यदि ब्लॉकों में (a == 0) x = y = 0; गाड़ी अपने स्थान से बहुत दूर चली जाती है, और वहाँ यह बनी रहती है। लेकिन यह बहुत महत्वपूर्ण नहीं है, क्योंकि इस समय चक्र समाप्त होता है।
तो क्या? सब कुछ जो 8-बिट BF मशीन पर किया जा सकता है, वह यहां किया जा सकता है? अफसोस। एक कार्य है जो अनंत बिट गहराई वाली कार के लिए बहुत कठिन है। अर्थात्, टेप अनुभाग की सफाई। अगर हमें एक टुकड़ा नहीं दिया जाता है जो शून्य से भरे जाने की गारंटी है, तो हम इसे नहीं बना सकते। हालांकि मैं इसे साबित नहीं कर सकता :(