फ्रैक्ट्रान

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

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

Conway 1987 निम्नलिखित FRACTRAN प्रोग्राम देता है, जिसे PRIMEGAME कहा जाता है, जो क्रमिक अभाज्य संख्याएँ पाता है:

$$\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 से शुरू होकर, यह FRACTRAN प्रोग्राम पूर्णांकों के निम्नलिखित अनुक्रम उत्पन्न करता है:

• 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 की प्रधान शक्तियाँ हैं।

एक FRACTRAN कार्यक्रम को समझना

एक FRACTRAN प्रोग्राम को एक प्रकार की रजिस्टर मशीन के रूप में देखा जा सकता है जहाँ रजिस्टरों को तर्क n में प्राइम एक्सपोनेंट्स में संग्रहीत किया जाता है।

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

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

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

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

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

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

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

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

जोड़

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

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

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

FRACTRAN 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)। क्योंकि जब भी परीक्षण किया जाता है तो प्रत्येक संकेतक का उपभोग किया जाता है, हमें वर्तमान स्थिति में जारी रखने के लिए एक द्वितीयक संकेतक की आवश्यकता होती है; इस द्वितीयक संकेतक को अगले निर्देश में प्राथमिक संकेतक पर वापस स्वैप किया जाता है, और लूप जारी रहता है।

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

FRACTRAN 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

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

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

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

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

घटाव और भाग

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

FRACTRAN instruction	Current state	State indicators	Condition	Action	Next state
${\frac {7\cdot 13}{2\cdot 3\cdot 11}},{\frac {11}{13}}$	A	v11, v13	v2 > 0 and v3 > 0	Subtract 1 from v2 Subtract 1 from v3 Add 1 to v7	A
${\frac {1}{3\cdot 11}}$			v2 = 0 and v3 > 0	Subtract 1 from v3	X
${\frac {5\cdot 17}{11}}$			v3 = 0	Add 1 to v5	B
${\frac {3\cdot 19}{7\cdot 17}},{\frac {17}{19}}$	B	v17, v19	v7 > 0	Subtract 1 from v7 Add 1 to v3	B
${\frac {11}{17}}$			v7 = 0	None	A
${\frac {1}{3}}$	X		v3 > 0	Subtract 1 from v3	X
			v3 = 0	Stop

FRACTRAN प्रोग्राम को लिखते हुए, हमारे पास:

$$\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$ एन और का सबसे बड़ा पूर्णांक विभाजक है $\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 की बाद की शक्तियों द्वारा क्रमिक अभाज्य उत्पन्न होते हैं।

अन्य उदाहरण

निम्नलिखित FRACTRAN कार्यक्रम:

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

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

FRACTRAN instruction	Current state	State indicators	Condition	Action	Next state
${\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	None	B
${\frac {2}{3}}$	B	None	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	Stop

यह भी देखें

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

संदर्भ

• 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: "Fractran: A Ridiculous Logical Language"
• "Prime Number Pathology: Fractran"
• Weisstein, Eric W. "FRACTRAN". MathWorld.
• Prime Number Pathology
• FRACTRAN - (Esolang wiki)
• Ruby implementation and example programs
• Project Euler Problem 308
• "Building Fizzbuzz in Fractran from the Bottom Up"
• Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"