फ्रैक्ट्रान

फ्रैक्ट्रान ट्यूरिंग-पूर्ण गूढ़ प्रोग्रामिंग भाषा है, जिसका आविष्कार गणितज्ञ जॉन हॉर्टन कॉनवे ने किया था। फ्रैक्ट्रान प्रोग्राम सकारात्मक भिन्न (गणित) का प्रारंभिक पूर्णांक निविष्ट N के साथ अनुक्रम है। प्रोग्राम निम्नानुसार पूर्णांक 'N' को अद्यतन करके चलाया जाता है।

1. पहले भिन्न F के लिए सूची में जिसके लिए NF पूर्णांक है, N को NF से बदलें।
2. इस नियम को तब तक करते रहे, जब तक कि सूची में कोई भी भिन्न N से गुणा करने पर पूर्णांक नहीं बनाता, फिर रुक जाता है।

कोनवे 1987 निम्नलिखित फ्रैक्ट्रान प्रोग्राम देता है, जिसे प्राइमगेम कहा जाता है, जो क्रमिक अभाज्य संख्याएँ पाता है।

$$\left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{2}},{\frac {1}{7}},{\frac {55}{1}}\right)$$

N=2 से प्रारंभ होकर, यह फ्रैक्ट्रान प्रोग्राम पूर्णांकों के निम्नलिखित अनुक्रम उत्पन्न करता है।

• 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, . . .

2 के बाद, इस क्रम में 2 की निम्नलिखित घातांक हैं।

$$2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\dots$$

जो 2 की प्रधान घातांक हैं।

फ्रैक्ट्रान प्रोग्राम को समझना

फ्रैक्ट्रान प्रोग्राम को प्रकार की रजिस्टर मशीन के रूप में देखा जा सकता है, जहाँ रजिस्टरों को तर्क n में प्रमुख घातांक में संग्रहीत किया जाता है।

गोडेल संख्या का उपयोग करते हुए, सकारात्मक पूर्णांक n स्वेच्छया से बड़े सकारात्मक पूर्णांक चर की स्वेच्छा संख्या को सांकेतिक शब्दों में बदल सकता है। प्रत्येक चर का मान पूर्णांक के पूर्णांक गुणनखंड में अभाज्य संख्या के घातांक के रूप में सांकेतिक किया गया है। उदाहरण के लिए, पूर्णांक

$$60=2^{2}\times 3^{1}\times 5^{1}$$

रजिस्टर स्थिति का प्रतिनिधित्व करता है,चर जिसे हम v2 कहेंगे जिसका मान 2 है और दो अन्य चर (v3 और v5) का मान 1 है। अन्य सभी चर का मान 0 है।

फ्रैक्ट्रान प्रोग्राम सकारात्मक भिन्नों की क्रमबद्ध सूची है। प्रत्येक भिन्न निर्देश का प्रतिनिधित्व करता है जो अधिक चर का परीक्षण करता है। जो इसके भाजक के प्रमुख कारकों द्वारा दर्शाया जाता है। उदाहरण के लिए,

$$f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1}}}$$

परीक्षण v2 और v5। यदि $v_{2}\geq 2$ और $v_{5}\geq 1$, फिर यह v2 से 2 और v5 से 1 घटाता है और 1 को v3 और 1 को v7 में जोड़ता है। उदाहरण के लिए,

$$60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3\times 7}{2^{2}\times 5^{1}}}=3^{2}\times 7^{1}$$

चूँकि, फ्रैक्ट्रान प्रोग्राम केवल भिन्नों की सूची है। ये परीक्षण-कमी-वृद्धि निर्देश फ्रैक्ट्रान भाषा में केवल अनुमत निर्देश हैं। इसके अतिरिक्त निम्नलिखित प्रतिबंध लागू होते हैं।

• हर बार निर्देश निष्पादित किया जाता है, परीक्षण किए गए चर भी कम हो जाते हैं।
• चर को निर्देश में घटाया और बढ़ाया नहीं जा सकता हैं। अन्यथा उस निर्देश का प्रतिनिधित्व करने वाला भिन्न अपने निम्नतम शब्दों में नहीं होगा। इसलिए प्रत्येक फ्रैक्ट्रान निर्देश चर का उपभोग करता है क्योंकि यह उनका परीक्षण करता है।
• यदि चर 0 है, तो फ्रैक्ट्रान निर्देश के लिए सीधे परीक्षण करना संभव नहीं है। चूंकि, अप्रत्यक्ष परीक्षण को व्यतिक्रम निर्देश बनाकर लागू किया जा सकता है जो किसी विशेष चर का परीक्षण करने वाले अन्य निर्देशों के बाद रखा जाता है।

सरल प्रोग्राम बनाना

जोड़

सबसे सरल फ्रैक्ट्रान प्रोग्राम एकल निर्देश है जैसे

$$\left({\frac {3}{2}}\right)$$

इस प्रोग्राम को निम्नानुसार बहुत सरल कलन विधि के रूप में दर्शाया जा सकता है।

फ्रैक्ट्रान निर्देश	परिस्थिति	क्रिया
${\frac {3}{2}}$	v2 > 0	v2 में से 1 घटाएं v3 में 1 जोड़ें
	v2 = 0	रुकना

प्रपत्र के प्रारंभिक निविष्ट को देखते हुए $2^{a}3^{b}$, यह प्रोग्राम अनुक्रम की गणना करेगा $2^{a-1}3^{b+1}$, $2^{a-2}3^{b+2}$, आदि, अंततः, के बाद तक $a$ चरण, 2 का कोई कारक नहीं रहता है और उत्पाद के साथ ${\frac {3}{2}}$ अब कोई पूर्णांक नहीं देता है। मशीन तब के अंतिम आउटपुट के साथ बंद हो जाती है $3^{a+b}$. इसलिए यह दो पूर्णांकों को साथ जोड़ता है।

गुणा

हम योजक के माध्यम से लूप करके गुणक बना सकते हैं। ऐसा करने के लिए हमें अपने कलन विधि में स्थिति (कंप्यूटर विज्ञान) प्रस्तुत करने की आवश्यकता है। यह कलन विधि संख्या लेगा $2^{a}3^{b}$ और उत्पादन $5^{ab}$ है।

वर्तमान स्थिति	परिस्थिति	क्रिया	आगे की स्थिति
A	v7 > 0	v7 में से 1 घटाएं v3 में 1 जोड़ें	A
	v7 = 0 and v2 > 0	v2 में से 1 घटाएं	B
	v7 = 0 and v2 = 0 and v3 > 0	v3 में से 1 घटाएं	A
	v7 = 0 and v2 = 0 and v3 = 0	रुकना
B	v3 > 0	v3 में से 1 घटाएं v5 में 1 जोड़ें v7 में 1 जोड़ें	B
	v3 = 0	कोई नहीं	A

स्थिति B लूप है जो v3 को v5 में जोड़ता है और v3 को v7 में भी ले जाता है, और स्थिति A बाहरी नियंत्रण लूप है जो लूप को स्थिति B v2 बार दोहराता है। स्थिति B में लूप पूरा होने के बाद स्थिति A भी v7 ​​से v3 के मान को पुनर्स्थापित करता है।

हम स्थिति संकेतकों के रूप में नए चरों का उपयोग करके स्थितियों को लागू कर सकते हैं। स्थिति B के लिए स्थिति संकेतक v11 और v13 होंगे। ध्यान दें कि हमें लूप के लिए दो स्थिति नियंत्रण संकेतकों की आवश्यकता होती है। प्राथमिक ध्वज (v11) और द्वितीयक ध्वज (v13)। क्योंकि जब भी परीक्षण किया जाता है, तो प्रत्येक संकेतक का उपभोग किया जाता है। हमें वर्तमान स्थिति में जारी रखने के लिए द्वितीयक संकेतक की आवश्यकता होती है। इस द्वितीयक संकेतक को अगले निर्देश में प्राथमिक संकेतक पर वापस बदलना किया जाता है और लूप जारी रहता है।

गुणन कलन विधि तालिका में फ्रैक्ट्रान स्थिति संकेतक और निर्देश जोड़ना, हमारे पास है।

फ्रैक्ट्रान निर्देश	वर्तमान स्थिति	राज्य संकेतक	परिस्थिति	क्रिया	आगे की स्थिति
${\frac {3}{7}}$	A	कोई नहीं	v7 > 0	v7 में से 1 घटाएं v3 में 1 जोड़ें	A
${\frac {11}{2}}$			v7 = 0 and v2 > 0	स्थितियोंv2 में से 1 घटाएं	B
${\frac {1}{3}}$			v7 = 0 and v2 = 0 and v3 > 0	v3 में से 1 घटाएं	A
			v7 = 0 and v2 = 0 and v3 = 0	रुकना
$\frac{5\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->13}{}$