फ्रैक्ट्रान

फ्रैक्ट्रान ट्यूरिंग-पूर्ण गूढ़ प्रोग्रामिंग भाषा है, जिसका आविष्कार गणितज्ञ जॉन हॉर्टन कॉनवे ने किया था। फ्रैक्ट्रान प्रोग्राम सकारात्मक भिन्न (गणित) का प्रारंभिक पूर्णांक निविष्ट 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}^{}$