फ्रैक्ट्रान

फ्रैक्ट्रान ट्यूरिंग-पूर्ण गूढ़ प्रोग्रामिंग भाषा है, जिसका आविष्कार गणितज्ञ जॉन हॉर्टन कॉनवे ने किया था। फ्रैक्ट्रान कार्यक्रम सकारात्मक अंश (गणित) का प्रारंभिक सकारात्मक पूर्णांक इनपुट 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, ... (sequence A007542 in the OEIS)

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$$

(sequence A034785 in the OEIS) जो 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)$$

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

फ्रैक्ट्रान instruction	Condition	Action
${\frac {3}{2}}$	v2 > 0	Subtract 1 from v2 Add 1 to v3
	v2 = 0	Stop

प्रपत्र के प्रारंभिक इनपुट को देखते हुए $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}$।

Current state	Condition	Action	Next state
A	v7 > 0	Subtract 1 from v7 Add 1 to v3	A
	v7 = 0 and v2 > 0	Subtract 1 from v2	B
	v7 = 0 and v2 = 0 and v3 > 0	Subtract 1 from v3	A
	v7 = 0 and v2 = 0 and v3 = 0	Stop
B	v3 > 0	Subtract 1 from v3 Add 1 to v5 Add 1 to v7	B
	v3 = 0	None	A

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

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

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

फ्रैक्ट्रान instruction	Current state	State indicators	Condition	Action	Next state
${\frac {3}{7}}$	A	None	v7 > 0	Subtract 1 from v7 Add 1 to v3	A
${\frac {11}{2}}$			v7 = 0 and v2 > 0	Subtract 1 from v2	B
${\frac {1}{3}}$			v7 = 0 and v2 = 0 and v3 > 0	Subtract 1 from v3	A
			v7 = 0 and v2 = 0 and v3 = 0	Stop
${\frac {5\cdot 7\cdot 13}{3\cdot 11}},{\frac {11}{13}}$	B	v11, v13	v3 > 0	Subtract 1 from v3 Add 1 to v5 Add 1 to v7	B
${\frac {1}{11}}$			v3 = 0	None	A

जब हम फ्रैक्ट्रान निर्देश लिखते हैं, तो हमें राज्य A निर्देश को अंतिम रखना चाहिए, क्योंकि राज्य A में कोई राज्य संकेतक नहीं है - यदि कोई राज्य संकेतक सेट नहीं है तो यह व्यतिक्रम स्थिति है। तो फ्रैक्ट्रान प्रोग्राम के रूप में, गुणक बन जाता है।

$$(\frac{455}{33},\frac{11}{13},\frac{1}{11},\frac{3}{7},\frac{11}{}$$