फ्रैक्ट्रान

फ्रैक्ट्रान ट्यूरिंग-पूर्ण गूढ़ प्रोग्रामिंग भाषा है, जिसका आविष्कार गणितज्ञ जॉन हॉर्टन कॉनवे ने किया था। फ्रैक्ट्रान कार्यक्रम सकारात्मक अंश (गणित) का प्रारंभिक सकारात्मक पूर्णांक इनपुट 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 मनमाने ढंग से बड़े सकारात्मक पूर्णांक चर की मनमानी संख्या को सांकेतिक शब्दों में बदल सकता है। प्रत्येक चर का मान पूर्णांक के पूर्णांक गुणनखंड में अभाज्य संख्या के घातांक के रूप में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	Subtract 1 from v2	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 7\cdot 13}{3\cdot 11}},{\frac {11}{13}}$	B	v11, v13	v3 > 0	v3 में से 1 घटाएं v5 में 1 जोड़ें v7 में 1 जोड़ें	B
${\frac {1}{11}}$			v3 = 0	कोई नहीं	A

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

$$\left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)$$

इनपुट के साथ 2^ए3^b यह प्रोग्राम आउटपुट 5 उत्पन्न करता है^{अब</सुप>.}

उपरोक्त फ्रैक्ट्रान कार्यक्रम, 3 गुना 2 की गणना (जिससे कि इसका इनपुट है $2^{3}\times 3^{2}=72$ और इसका आउटपुट होना चाहिए $5^{6}$ क्योंकि 3 गुना 2 बराबर 6.

घटाव और भाग

इसी तरह, हम फ्रैक्ट्रान घटाव बना सकते हैं, और बार-बार घटाव हमें भागफल और शेष कलन विधि बनाने की अनुमति देता है।

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

फ्रैक्ट्रान प्रोग्राम को लिखते हुए, हमारे पास।

$$\left({\frac {91}{66}},{\frac {11}{13}},{\frac {1}{33}},{\frac {85}{11}},{\frac {57}{119}},{\frac {17}{19}},{\frac {11}{17}},{\frac {1}{3}}\right)$$

और इनपुट 2^एन3^d11 आउटपुट 5 उत्पन्न करता है^क्ष7^r जहां n = qd + r और 0 ≤ r < d।

कॉनवे का प्रमुख कलन विधि

उपरोक्त कॉनवे का प्रमुख उत्पादन कलन विधि अनिवार्य रूप से दो लूप के भीतर भागफल और शेष कलन विधि है। प्रपत्र का इनपुट दिया गया $2^{n}7^{m}$ जहाँ 0 ≤ m < n, कलन विधि n+1 को प्रत्येक संख्या से n से 1 तक विभाजित करने का प्रयास करता है, जब तक कि यह सबसे बड़ी संख्या k नहीं पाता जो n+1 का भाजक है। यह फिर 2 लौटाता है^एन+1 7^k-1 और दोहराता है। कलन विधि द्वारा उत्पन्न स्थिति संख्याओं का अनुक्रम केवल 2 की शक्ति उत्पन्न करता है जब के 1 होता है जिससे कि 7 का घातांक 0 हो), जो केवल तब होता है जब 2 का घातांक प्राइम होता है। हैविल (2007) में कॉनवे के कलन विधि की चरण-दर-चरण व्याख्या पाई जा सकती है।

इस प्रोग्राम के लिए अभाज्य संख्या 2, 3, 5, 7... तक पहुँचने के लिए क्रमशः 19, 69, 281, 710,... चरणों की आवश्यकता है (sequence A007547 in the OEIS).

कॉनवे के कार्यक्रम का प्रकार भी उपस्थित है, जो उपरोक्त संस्करण से दो अंशों से भिन्न है।

$$\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}{14}},{\frac {15}{2}},{\frac {55}{1}}\right)$$

यह संस्करण थोड़ा तेज़ है। 2, 3, 5, 7... तक पहुँचने में इसे 19, 69, 280, 707... कदम लगते हैं (sequence A007546 in the OEIS). इस कार्यक्रम का एकल पुनरावृत्ति, प्रधानता के लिए विशेष संख्या N की जाँच करते हुए, निम्नलिखित चरणों की संख्या लेता है।

$$N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor ,$$

जहाँ पे $b<N$N और का सबसे बड़ा पूर्णांक विभाजक है $\lfloor x\rfloor$ फ्लोर फंक्शन है। 1999 में, डेविन किल्मिंस्टर ने छोटे, दस-निर्देश कार्यक्रम का प्रदर्शन किया।

$$\left({\frac {7}{3}},{\frac {99}{98}},{\frac {13}{49}},{\frac {39}{35}},{\frac {36}{91}},{\frac {10}{143}},{\frac {49}{13}},{\frac {7}{11}},{\frac {1}{2}},{\frac {91}{1}}\right).$$

प्रारंभिक इनपुट n = 10 के लिए 10 की बाद की शक्तियों द्वारा क्रमिक अभाज्य उत्पन्न होते हैं।

अन्य उदाहरण

निम्नलिखित फ्रैक्ट्रान कार्यक्रम।

$$\left({\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}},{\frac {13}{2\cdot 5}},{\frac {1}{5}},{\frac {2}{3}},{\frac {2\cdot 5}{7}},{\frac {7}{2}}\right)$$

A के बाइनरी विस्तार के हैमिंग वजन H (A) की गणना करता है अर्थात Aके बाइनरी विस्तार में 1 एस की संख्या। दिया गया इनपुट 2^a, इसका आउटपुट 13 है^एच(क)। कार्यक्रम का विश्लेषण इस प्रकार किया जा सकता है।

फ्रैक्ट्रान निर्देश	वर्तमान स्थिति	State indicators	परि स्थिति	क्रिया	आगे की स्थिति
${\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}}$	A	v5, v11	v2 > 1	Subtract 2 from v2 Add 1 to v3	A
${\frac {13}{2\cdot 5}}$			v2 = 1	Subtract 1 from v2 Add 1 to v13	B
${\frac {1}{5}}$			v2 = 0	कोई नहीं	B
${\frac {2}{3}}$	B	कोई नहीं	v3 > 0	Subtract 1 from v3 Add 1 to v2	B
${\frac {2\cdot 5}{7}}$			v3 = 0 and v7 > 0	Subtract 1 from v7 Add 1 to v2	A
${\frac {7}{2}}$			v3 = 0 and v7 = 0 and v2 > 0	Subtract 1 from v2 add 1 to v7	B
			v2 = 0 and v3 = 0 and v7 = 0	रुकना

यह भी देखें

• निर्देश स्थिर करना कंप्यूटर

संदर्भ

• Guy, Richard K. (1983). "Conway's Prime Producing Machine". Mathematics Magazine. Taylor & Francis. 56 (1): 26–33. doi:10.1080/0025570X.1983.11977011.
• Conway, John H. (1987). "FRACTRAN: A simple universal programming language for arithmetic". Open Problems in Communication and Computation. Springer-Verlag New York, Inc.: 4–26. doi:10.1007/978-1-4612-4808-8_2. ISBN 978-1-4612-9162-6.
• Conway, John H.; Guy, Richard K. (1996). The Book of Numbers. Springer-Verlag New York, Inc. ISBN 0-387-97993-X.
• Havil, Julian (2007). Nonplussed!. Princeton University Press. ISBN 978-0-691-12056-0.
• Roberts, Siobhan (2015). "Criteria of virtue". Genius At Play - The Curious Mind of John Horton Conway. Bloomsbury. pp. 115–119. ISBN 978-1-62040-593-2.

बाहरी कड़ियाँ

• Lecture from John Conway। "फ्रैक्ट्रान। A Ridiculous Logical Language"
• "Prime Number Pathology। फ्रैक्ट्रान"
• Weisstein, Eric W. "FRACTRAN". MathWorld.
• Prime Number Pathology
• फ्रैक्ट्रान - (Esolang wiki)
• Ruby implementation and example programs
• Project Euler Problem 308
• "Building Fizzbuzz in फ्रैक्ट्रान from the Bottom Up"
• Chris Lomont, "A Universal फ्रैक्ट्रान Interpreter in फ्रैक्ट्रान"