काउंटर मशीन

काउंटर मशीन एब्स्ट्रेक्ट मशीन है जिसका उपयोग फार्मल लॉजिक और थ्योरेटिकल कंप्यूटर साइंस में गणना के मॉडल के लिए किया जाता है। इस प्रकार यह चार प्रकार की रजिस्टर मशीन में से सबसे मौलिक है। काउंटर मशीन में या अधिक अनबाउंडेड रजिस्टरों का सेट सम्मिलित होता है, जिनमें से प्रत्येक ऋणात्मक पूर्णांक, और मशीन के पालन के लिए (सामान्यतः अनुक्रमिक) अंकगणित और नियंत्रण निर्देशों की सूची रख सकता है। इस प्रकार काउंटर मशीन का उपयोग सामान्यतः पारस्परिक बहिष्करण सिद्धांत के संबंध में समानांतर एल्गोरिदम को डिजाइन करने की प्रक्रिया में किया जाता है। जब इस विधि से उपयोग किया जाता है, जिससे काउंटर मशीन का उपयोग मेमोरी एक्सेस के संबंध में कम्प्यूटेशनल सिस्टम के भिन्न-भिन्न समय-चरणों को मॉडल करने के लिए किया जाता है। इस प्रकार प्रत्येक संबंधित कम्प्यूटेशनल फेज के लिए मेमोरी एक्सेस के संबंध में गणनाओं को मॉडलिंग करके, समान मेमोरी पते पर दो (या अधिक) थ्रेड्स द्वारा साथ लेखन ऑपरेशन, इंटरलॉकिंग से बचने के लिए ऐसे स्थिति में समानांतर एल्गोरिदम डिज़ाइन किया जा सकता है।

मूलभूत सुविधाएँ

किसी दिए गए काउंटर मशीन मॉडल के लिए निर्देश सेट छोटा है केवल से छह या सात निर्देशों तक अधिकांश मॉडलों में कुछ अंकगणितीय ऑपरेशन और कम से कम नियमबद्ध ऑपरेशन होता है (यदि स्थिति सत्य है, तो जम्प करे)। तीन आधार मॉडल, प्रत्येक तीन निर्देशों का उपयोग करते हुए, निम्नलिखित संग्रह से तैयार किए गए हैं। (संक्षिप्ताक्षर अनैतिक हैं।)

• CLR (r): क्लियर रजिस्टर r। (r को शून्य पर सेट करें।)
• INC (r): रजिस्टर r की कंटेंट को बढ़ाएं।
• DEC (r): रजिस्टर r की कंटेंट को घटाएं।
• CPY (r_j, r_k): रजिस्टर r_j की कंटेंट को कॉपी करें r_k पंजीकृत करने के लिए r_j की कंटेंट को छोड़कर बनाये रहते है।
• JZ (r, Z): यदि रजिस्टर r में शून्य है तो निर्देश Z पर जाएं अन्यथा क्रम में जारी रखें।
• JE (r_j, r_k, z): यदि रजिस्टर r_j की कंटेंट रजिस्टर r_k की कंटेंट के समान है फिर निर्देश पर जाएं अन्यथा क्रम से जारी रखें।

इसके अतिरिक्त, मशीन में सामान्यतः HALT निर्देश होता है, जो मशीन को रोक देता है (सामान्यतः परिणाम की गणना के पश्चात्)।

ऊपर उल्लिखित निर्देशों का उपयोग करते हुए, विभिन्न लेखकों ने कुछ काउंटर मशीनों पर चर्चा की है:

• सेट 1: { INC (r), DEC (r), JZ (r, Z) }, (मिन्स्की (1961, 1967), लैम्बेक (1961))
• सेट 2: { CLR (r), INC (r), JE (r)।_j, r_k, z) }, (एर्शोव (1958), पीटर (1958) जैसा कि शेफर्डसन-स्टर्गिस (1964); मिन्स्की (1967); शॉनहेज (1980) द्वारा व्याख्या की गई है)
• सेट 3: {INC (r), CPY (r)।_j, आर_k), JE (r_j, r_k, z) }, (एल्गॉट-रॉबिन्सन (1964), मिन्स्की (1967))

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

वैकल्पिक नाम, वैकल्पिक मॉडल

Main article: काउंटर-मशीन मॉडल

काउंटर मशीन मॉडल अनेक भिन्न-भिन्न नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें भिन्न करने में सहायता कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r रिक्त है या नहीं; यदि ऐसा है तो निर्देश I_z पर जाएँ, अन्यथा यदि नहीं तो r की कंटेंट को घटाएँ जाते है:

• शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने फार्मल रूप से अपने मॉडल को सरलता से सुलभ प्रदर्शनी (1963) में बताया था। इस प्रकार अतिरिक्त सुविधा निर्देशों के साथ संवर्धित अनुदेश सेट (1) का उपयोग करता है (JNZ शून्य नहीं होने पर जंप है, JZ के स्थान पर उपयोग किया जाता है):

  {INC (r), DEC (r), CLR (r), CPY (r)।_j, r_k ), JNZ (r, Z), J (Z)}

• मिन्स्की मशीन, क्योंकि मार्विन मिंस्की (1961) ने मॉडल को फार्मल रूप दिया। सामान्यतः निर्देश सेट (1) का उपयोग करता है, किन्तु निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त मापदंड 'z' INC के पश्चात् अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:

  { INC ( r, z ), JZDEC ( r, z_true, z_false) }

• प्रोग्राम मशीन, प्रोग्राम कंप्यूटर, नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं इस प्रकार जब तक कि नियमबद्ध जम्प सफल नहीं होती है। (सामान्यतः) निर्देश सेट (1) का उपयोग करता है किन्तु इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अधिकांशतः भिन्न कर दिया जाता है:

  { INC ( r ), DEC ( r ), JZ ( r, z_true )}

• अबेकस मशीन, नाम लैम्बेक (1961) ने मेल्ज़ाक (1961) मॉडल के सरलीकरण के लिए दिया था, और बूलोस-बर्गेस-जेफरी (2002) इसे क्या कहते हैं। मिन्स्की (1961) मॉडल के विधि से अगले निर्देश को निर्दिष्ट करने के लिए निर्देश सेट (1) का उपयोग करता है किन्तु अतिरिक्त मापदंड z के साथ;

  { INC ( r, z ), JZDEC (r, z_true, z_false ) }

• लैम्बेक मशीन, वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया था। अगले निर्देश को निर्दिष्ट करने के लिए अतिरिक्त मापदंड के साथ निर्देश सेट (1-कम) का उपयोग करता है:

  { INC ( r, z ), JZDEC ( r, z_true, z_false ) }

• उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से अधिक मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके सूचक मशीन SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है:

  {CLR (r), INC (r), JE (r)।_j, r_k, z ) }

• एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में रिक्त रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।)

  { INC (r), CPY (r_s, r_d ), JE (r_j, r_k, z ) }

• अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से अधिक भिन्न है क्योंकि इसमें 'वृद्धि' और 'घटाना' के अतिरिक्त 'जोड़' और 'घटाना' सम्मिलित है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई K, और डीआईवी K} की आवश्यकता होती है। इस प्रकार मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (किन्तु ट्यूरिंग पूर्णता प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।

फार्मल परिभाषा

एक काउंटर मशीन में निम्न सम्मिलित होते हैं:

1. लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का सीमित (या कुछ मॉडलों में अनंत) सेट r₀... r_n जिनमें से प्रत्येक किसी ऋणात्मक पूर्णांक (0, 1, 2, ... - अर्थात असीमित) को धारण कर सकता है। इस प्रकार रजिस्टर अपना अंकगणित स्वयं करते हैं; या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए रैंडम-एक्सेस मशीन देखें)।
2. एक स्तर रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से भिन्न है; इस प्रकार काउंटर मशीन मॉडल हार्वर्ड आर्किटेक्चर का उदाहरण है
3. लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की सीमित सूची I₀... I_m. प्रोग्राम स्टोर (परिमित स्तर मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। सामान्यतः, किन्तु सदैव नहीं, कंप्यूटर प्रोग्राम की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई जम्प सफल नहीं होती है, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। इस प्रकार सूची में प्रत्येक निर्देश (बहुत) छोटे सेट से है, किन्तु इस सेट में अप्रत्यक्ष सम्मिलित नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:

{वृद्धि (r), कमी (r), स्पष्ट (r); कॉपी (r_j,r_k), यदि r=0 की कंटेंट है तो नियमबद्ध जम्प, यदि r की कंटेंट है तो नियमबद्ध r_j=r_k, नियमबद्ध जम्प, हॉल्ट }

कुछ मॉडलों ने या तो उपरोक्त में से कुछ को बिना-मापदंड निर्देशों में परमाणुकृत कर दिया है, या उन्हें ही निर्देश में जोड़ दिया है जैसे कि नियमबद्ध जम्प-यदि-शून्य JZ (r, Z) से पहले डिक्रीमेंट निर्देशों के परमाणुकरण या सुविधाजनक निर्देशों को सम्मिलित करने से वैचारिक पावर में कोई परिवर्तन नहीं होता है, क्योंकि संस्करण में किसी भी प्रोग्राम को सीधे दूसरे में अनुवादित किया जा सकता है।

पूरक रजिस्टर-मशीन मॉडल में वैकल्पिक निर्देश-सेट पर चर्चा की गई है।

उदाहरण: रजिस्टर #2 से #3 तक गणना कॉपी करें

यह उदाहरण दिखाता है कि तीन और उपयोगी निर्देश कैसे बनाएं: स्पष्ट, नियमबद्ध जंप और कॉपी।

• CLR (J): रजिस्टर r_j की कंटेंट स्पष्ट करें शून्य करने के लिए.
• J (Z): अप्रतिबंध निर्देश I_z पर जाएं.
• CPY (S, d): स्रोत रजिस्टर r_s की कंटेंट की प्रतिलिपि बनाएँ गंतव्य रजिस्टर r_d के लिए. (वन-इंस्ट्रक्शन सेट कंप्यूटर या ट्रांसपोर्ट ट्रिगर आर्किटेक्चर देखें)

पश्चात् में r_s इसमें इसकी मूल गणना सम्मिलित होगी (MOVE के विपरीत जो स्रोत रजिस्टर को रिक्त कर देता है, अर्थात इसे शून्य पर स्पष्ट कर देता है)।

मूल सेट (1) का उपयोग यहां परिभाषित अनुसार किया गया है:

निर्देश	रजिस्टर "j" पर प्रभाव	निर्देश काउंटर रजिस्टर आईसीआर पर प्रभाव	सारांश
INC ( j )	[j] +1 → j	[IC] +1 → IC	रजिस्टर j की कंटेंट में वृद्धि; अगले निर्देश
DEC ( j )	[j] -1 → j	[IC] +1 → IC	रजिस्टर j की घटी हुई कंटेंट; अगले निर्देश
JZ ( j, z)		IF [j] = 0 THEN Iz → IC ELSE [IC] +1 → IC	यदि रजिस्टर की कंटेंट j=0 है तो निर्देश z अन्यथा अगला निर्देश
HALT

प्रारंभिक नियम

प्रारंभ में, रजिस्टर #2 में 2 सम्मिलित है। रजिस्टर #0, #1 और #3 रिक्त हैं (जिनमें 0 है)। रजिस्टर #0 पूरी गणना के समय अपरिवर्तित रहता है क्योंकि इसका उपयोग अप्रतिबंध जम्प के लिए किया जाता है। रजिस्टर #1 स्क्रैच पैड है। प्रोग्राम निर्देश 1 से प्रारंभ होता है।

अंतिम नियम

प्रोग्राम रजिस्टर #2 की कंटेंट को उसकी मूल गणना पर और रजिस्टर #3 की कंटेंट को रजिस्टर #2 की मूल कंटेंट के समान रोक देता है, अर्थात,

[2] = [3]।

प्रोग्राम का उच्च स्तरीय विवरण

प्रोग्राम COPY (#2, #3) के दो भाग हैं। पहले भाग में प्रोग्राम स्रोत रजिस्टर #2 की कंटेंट को स्क्रैच-पैड #1 और गंतव्य रजिस्टर #3 दोनों में ले जाता है; इस प्रकार #1 और #3 दूसरे की और #2 में मूल गणना की प्रतियां होंगी, किन्तु #2 को शून्य तक घटाने की प्रक्रिया में स्पष्ट कर दिया गया है। अप्रतिबंध जम्प J (z) रजिस्टर #0 के परीक्षणों द्वारा की जाती है, जिसमें सदैव संख्या 0 होती है:

[#2] →#3; [#2] →#1; 0 →#2

दूसरे भाग में प्रोग्राम स्क्रैच-पैड #1 की कंटेंट को वापस #2 पर ले जाता है (लौटाता है, पुनर्स्थापित करता है), इस प्रक्रिया में स्क्रैच-पैड #1 को स्पष्ट करता है:

[#1] →#2; 0 →#1

प्रोग्राम

पीले रंग में हाइलाइट किया गया प्रोग्राम ऊपरी दाएँ भाग में बाएँ से दाएँ लिखा हुआ दिखाया गया है।

प्रोग्राम का रन नीचे दिखाया गया है। समय पृष्ठ के नीचे चला जाता है। निर्देश पीले रंग में हैं, रजिस्टर नीले रंग में हैं। प्रोग्राम को 90 डिग्री पर फ़्लिप किया गया है, शीर्ष पर निर्देश संख्या (पते), पतों के नीचे निर्देश निमोनिक्स, और निमोनिक्स के अनुसार निर्देश मापदंड (प्रति सेल एक):

															1	2	3	4	5	6	7	8	9	10	← निर्देश क्रमांक (पता)
															JZ	DEC	INC	INC	JZ	JZ	DEC	INC	JZ	H	← निर्देश
															2	2	3	1	0	1	1	2	0		← संख्या रजिस्टर
															6				1	10			6		← निर्देश संख्या पर जाएं
step		IC	Inst #	reg #	J-addr		reg0	reg1	reg2	reg3	reg4		IC
start							0	0	2	0	0		1												[#2] को #1 और #3 पर ले जाएं:
1		1	JZ	2	6		0	0	2	0	0		1→2		JZ										जंप विफल: रजिस्टर #2 में 2 सम्मिलित है
2		2	DEC	2	0		0	0	2→1	0	0		2→3			DEC									रजिस्टर #2 को 2 से 1 तक घटाएँ
3		3	INC	3	0		0	0	1	0→1	0		3→4				INC								रजिस्टर #3 को 0 से 1 तक बढ़ाएँ
4		4	INC	1	0		0	0→1	1	1	0		4→5					INC							रजिस्टर #1 को 0 से 1 तक बढ़ाएँ
5		5	JZ	0	1		0	1	1	1	0		5→1						JZ						यू-जंप: रजिस्टर #0 रिक्त है
6		1	JZ	2	6		0	1	1	1	0		1→2		JZ										जंप विफल: रजिस्टर #2 में 1 सम्मिलित है
7		2	DEC	2	0		0	1	1→0	1	0		2→3			DEC									रजिस्टर #2 को 1 से 0 तक घटाएँ
8		3	INC	3	0		0	1	0	1→2	0		3→4				INC								रजिस्टर #3 को 1 से 2 तक बढ़ाएँ
9		4	INC	1	0		0	1→2	0	2	0		4→5					INC							रजिस्टर #1 को 1 से 2 तक बढ़ाएँ
10		5	JZ	0	1		0	2	0	2	0		5→1						JZ						यू-जंप: रजिस्टर #0 रिक्त है
11		1	JZ	2	6		0	2	0	2	0		1→6		JZ										जम्प!: रजिस्टर #2 रिक्त है
																									[1] को 2 पर ले जाएँ:
12		6	JZ	1	10		0	2	0	2	0		6→7							JZ					जंप विफल: रजिस्टर #1 में 2 सम्मिलित हैं
13		7	DEC	1	0		0	2→1	0	2	0		7→8								DEC				रजिस्टर #1 को 2 से 1 तक घटाएँ
14		8	INC	2	0		0	1	0→1	2	0		8→9									INC			रजिस्टर #2 को 0 से 1 तक बढ़ाएँ
15		9	JZ	0	6		0	1	1	2	0		9→6										JZ		यू-जंप: रजिस्टर #0 रिक्त है
16		6	JZ	1	10		0	1	1	2	0		6→7							JZ					जंप विफल: रजिस्टर #1 में 1 सम्मिलित है
17		7	DEC	1	0		0	1→0	1	2	0		7→8								DEC				रजिस्टर #1 को 1 से 0 तक घटाएँ
18		8	INC	2	0		0	0	1→2	2	0		8→9									INC			रजिस्टर #2 को 1 से 2 तक बढ़ाएँ
19		9	JZ	0	6		0	0	2	2	0		9→6										JZ		यू-जंप: रजिस्टर #0 रिक्त है
20		6	JZ	1	10		0	0	2	2	0		6→10							JZ					जम्प!: रजिस्टर #1 रिक्त है
21		10	H	0	0		0	0	2	2	0		10→10											H	हाल्ट

आंशिक पुनरावर्ती कार्य: पुनरावर्तन का उपयोग करके सुविधा निर्देश बनाना

उपरोक्त उदाहरण दर्शाता है कि कैसे पहले मूलभूत निर्देश { INC, DEC, JZ } तीन और निर्देश बना सकते हैं अप्रतिबंध जंप J, CLR, CPY। अर्थ में CPY ने CLR और j प्लस बेस सेट दोनों का उपयोग किया था। इस प्रकार यदि रजिस्टर #3 में प्रारंभ में कंटेंट होती, तो #2 और #3 की कंटेंट का योग #3 में समाप्त होता है। इसलिए पुर्णतः स्पष्ट होने के लिए CPY प्रोग्राम को CLR (1) और CLR (3) के साथ आगे बढ़ना चाहिए था।

चूँकि, हम देखते हैं कि ADD सरलता से संभव होता। और वास्तव में निम्नलिखित इस बात का सारांश है कि ADD, MULtiply और EXPonent जैसे मौलिक पुनरावर्ती कार्य कैसे हो सकते हैं (बूलोस-बर्गेस-जेफरी (2002) पृष्ठ 45-51 देखें)।

• आरंभिक निर्देश सेट: {DEC, INC, JZ, H }
• अप्रतिबंध जंप J (z) को JZ (r0, z) के संदर्भ में परिभाषित करें, यह देखते हुए कि r0 में 0 है।

{J, DEC, INC, JZ, H }

• उपरोक्त के संदर्भ में CLeaR (r) को परिभाषित करें:

{CLR, J, DEC, INC, JZ, H }

• सीओपीवाई को परिभाषित करें (r_j, r_k ) r_j की कंटेंट को संरक्षित करते समय उपरोक्त के संदर्भ में:

{ CPY, CLR, J, DEC, INC, JZ, H }

उपरोक्त शेफर्डसन-स्टर्गिस (1963) का निर्देश सेट है।

• ADD (r_j, r_k, r_i ) को परिभाषित करें , (संभवतः r_j, और r_k की कंटेंट को संरक्षित करना), उपरोक्त के उपयोग से:

{ADD, CPY, CLR, J, DEC, INC, JZ, H }

• मल्टीप्लाई (r_j, r_k, r_i) (एमयूएल) को परिभाषित करें (संभवतः r_j, r_k की कंटेंट को संरक्षित करना), उपरोक्त के संदर्भ में:

{MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

• घातांक (r_j, r_k, r_i ) को परिभाषित करें (EXP) (संभवतः r_j, r_k की कंटेंट को संरक्षित करना ) उपरोक्त के संदर्भ में,

{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

सामान्यतः, हम समान विधियों का उपयोग करके, अपनी इच्छानुसार कोई भी आंशिक- या कुल-मौलिक पुनरावर्ती फ़ंक्शन बना सकते हैं। सामान्यतः, मिन्स्की (1967), शेफर्डसन-स्टर्गिस (1963) और बूलोस-बर्गेस-जेफरी (2002) बेस सेट (1) से पांच मौलिक पुनरावर्ती फ़ंक्शन ऑपरेटरों (नीचे 1-5) को बनाने का प्रदर्शन देते हैं।

किन्तु पूर्ण ट्यूरिंग मशीन समकक्ष के बारे में क्या? हमें पूर्ण तुल्यता प्राप्त करने के लिए छठे ऑपरेटर- μ ऑपरेटर को जोड़ने की आवश्यकता है, जो कुल- और आंशिक- रिकर्सन (कंप्यूटर साइंस) बनाने में सक्षम है:

1. शून्य फ़ंक्शन (या स्थिर फ़ंक्शन)
2. उत्तराधिकारी कार्य
3. पहचान फ़ंक्शन
4. रचना फ़ंक्शन
5. मौलिक पुनरावर्तन (प्रेरण)
6. μ ऑपरेटर (अनबाउंड सर्च ऑपरेटर)

लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (1, 2, या 3) के अन्दर सरलता से किया जाता है (एक उदाहरण μ ऑपरेटर पर पाया जा सकता है)। इसका कारण यह है कि किसी भी म्यू रिकर्सिव फ़ंक्शन को काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है, काउंटर मशीन डिज़ाइन के सीमित निर्देश सेट और प्रोग्राम आकार के अतिरिक्त चूँकि, आवश्यक निर्माण प्रति-सहज ज्ञान युक्त हो सकता है, यहां तक ​​कि उन कार्यों के लिए भी जिन्हें रैंडम-एक्सेस मशीन जैसी अधिक सम्मिश्र रजिस्टर मशीनों में परिभाषित करना अपेक्षाकृत आसान है। ऐसा इसलिए है क्योंकि μ ऑपरेटर असीमित संख्या में पुनरावृति कर सकता है, किन्तु कोई भी काउंटर मशीन अपनी निर्देश सूची के सीमित आकार के कारण असीमित संख्या में भिन्न-भिन्न रजिस्टरों को संबोधित नहीं कर सकती है।

उदाहरण के लिए, मौलिक पुनरावर्ती ऑपरेटरों के उपरोक्त पदानुक्रम को नुथ के अप-एरो नोटेशन में उच्च-क्रम वाले तीर संचालन में घातांक से आगे बढ़ाया जा सकता है। किसी भी निश्चित $k$ के लिए , प्रोग्राम $Q(x,y)=x\uparrow ^{k}y$ मौलिक पुनरावर्ती है, और इसे सीधे विधि से काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है। किन्तु फ़ंक्शन $R(n,x,y)=x\uparrow ^{n}y$ मौलिक पुनरावर्ती नहीं है. इस प्रकार किसी को अप-एरो ऑपरेटर को प्रयुक्त करने का लालच हो सकता है इस प्रकार $R$ कॉल स्टैक को कार्यान्वित करके, उपरोक्त उत्तराधिकारी, जोड़, गुणन और घातांक निर्देशों के समान निर्माण का उपयोग करते है, जिससे फ़ंक्शन $n$ को छोटे मानों पर पुनरावर्ती रूप से प्रयुक्त किया जा सकता है . यह विचार इस बात के समान है कि कोई व्यक्ति अनेक प्रोग्रामिंग भाषाओं में फ़ंक्शन को व्यवहार में कैसे प्रयुक्त कर सकता है। चूँकि, काउंटर मशीन अपनी गणना में असीमित संख्या में रजिस्टरों का उपयोग नहीं कर सकती है, जो कॉल स्टैक को प्रयुक्त करने के लिए आवश्यक होगा जो अनैतिक विधि से बड़ा हो सकता है। इस प्रकार अप-एरो ऑपरेशन को अभी भी काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है क्योंकि यह पुनरावर्ती है, चूँकि फ़ंक्शन को सीमित संख्या में रजिस्टरों के अंदर असीमित मात्रा में जानकारी को एन्कोड करके कार्यान्वित किया जाता है, जैसे गोडेल नंबरिंग का उपयोग करके होता है।

काउंटर मशीन मॉडल के साथ समस्याएं

रैंडम-एक्सेस मशीन लेख में समस्याओं पर विस्तार से चर्चा की गई है। समस्याएँ दो प्रमुख वर्गों और तीसरे असुविधा वर्ग में आती हैं:

(1) 'रजिस्टरों की असीमित क्षमताएं बनाम स्तर-मशीन निर्देशों की बंधी हुई क्षमताएं:' मशीन अपनी परिमित स्तर मशीन की क्षमता से बड़े स्थिरांक कैसे बनाएगी?

(2) 'रजिस्टरों की असीमित संख्या बनाम स्तर-मशीन निर्देशों की बंधी हुई संख्या:' मशीन अपनी सीमित स्तर मशीन की पहुंच/क्षमता से परे पता-संख्या वाले रजिस्टरों तक कैसे पहुंच पाएगी?

(3) पुर्णतः कम किए गए मॉडल कष्टकर हैं:

शेफर्डसन और स्टर्गिस (1963) अपने 6-निर्देश सेट के बारे में क्षमाप्रार्थी नहीं हैं। उन्होंने अपनी पसंद प्रोग्रामिंग में सरलता के आधार पर बनाई है... न कि मितव्ययता के आधार पर (पृ. 219 फुटनोट 1)।

शेफर्डसन और स्टर्गिस के निर्देश ([r] रजिस्टर r की कंटेंट को संकेत करता है):

• • वृद्धि (r); [r] +1 → r
  • कमी (r) ; [r] -1 → r
  • स्पष्ट (r) ; 0 → r
  • कॉपी (r_s को r_d ) ; [r_s] → r_d
  • निर्देश I_z पर अप्रतिबंध जम्प
  • यदि [r] =0 हो तो निर्देश I_z पर जम्प

मिन्स्की (1967) ने अपने 2-निर्देश सेट { INC (z), JZDEC (r, I)_z का विस्तार किया)} से { CLR (r), INC (r), JZDEC (r, I_z), j (I_z) } उनके इस प्रमाण से पहले कि यूनिवर्सल प्रोग्राम मशीन केवल दो रजिस्टरों के साथ बनाई जा सकती है (पृष्ठ 255एफएफ)।

दो-काउंटर मशीनें ट्यूरिंग समकक्ष हैं (चेतावनी के साथ)

प्रत्येक ट्यूरिंग मशीन के लिए, 2CM होता है जो इसे अनुकरण करता है, यह देखते हुए कि 2CM का इनपुट और आउटपुट ठीक से एन्कोड किया गया है। यह मिन्स्की की पुस्तक (कंप्यूटेशन, 1967, पृष्ठ 255-258) में सिद्ध हुआ है, और वैकल्पिक प्रमाण नीचे तीन चरणों में दिया गया है। सबसे पहले, ट्यूरिंग मशीन को दो स्टैक से सुसज्जित परिमित-स्तर मशीन (एफएसएम) द्वारा अनुकरण किया जा सकता है। फिर, दो स्टैक को चार काउंटरों द्वारा अनुकरण किया जा सकता है। अंत में, चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।

दो काउंटर मशीनें निर्देश के सेट { INC ( r, z ), JZDEC ( r, z_true, z_false) }. का उपयोग करती हैं

फेज 1: ट्यूरिंग मशीन को दो स्टैक द्वारा अनुकरण किया जा सकता है।

ट्यूरिंग मशीन में एफएसएम और अनंत टेप होता है, जो प्रारंभ में शून्य से भरा होता है, जिस पर मशीन और शून्य लिख सकती है। किसी भी समय, मशीन का रीड/राइट हेड टेप पर सेल की ओर संकेत करता है। उस बिंदु पर इस टेप को संकल्पनात्मक रूप से आधा काटा जा सकता है। टेप के प्रत्येक आधे भाग को स्टैक (डेटा संरचना) के रूप में माना जा सकता है, इस प्रकार जहां शीर्ष रीड/राइट हेड के निकटतम सेल है, और निचला भाग हेड से कुछ दूरी पर है, नीचे से परे टेप पर सभी शून्य हैं। तदनुसार, ट्यूरिंग मशीन को एफएसएम प्लस दो स्टैक द्वारा अनुकरण किया जा सकता है। सिर को बाएँ या दाएँ करके संग्रह से थोड़ा सा उठाकर दूसरे संग्रह पर पुश के समान है। लिखना किसी चीज़ को आगे बढ़ाने से पहले उसे परिवर्तन के समान है।

फेज 2: स्टैक को दो काउंटरों द्वारा अनुकरण किया जा सकता है।

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

फेज 3: चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।

पहले की तरह, काउंटरों में से का उपयोग स्क्रैचपैड के रूप में किया जाता है। दूसरे में पूर्णांक है जिसका अभाज्य संख्या गुणनखंड 2^a3^b5^c7^d है. घातांक a, b, c और d को चार आभासी काउंटरों के रूप में माना जा सकता है जिन्हें (गोडेल नंबरिंग के माध्यम से) ही वास्तविक काउंटर में पैक किया जा रहा है। यदि वास्तविक काउंटर को शून्य पर सेट किया जाता है और फिर बार बढ़ाया जाता है, तो यह सभी वर्चुअल काउंटरों को शून्य पर सेट करने के समान है। यदि वास्तविक काउंटर को दोगुना कर दिया जाता है, तो यह a को बढ़ाने के समान है, और यदि इसे आधा कर दिया जाता है, तो यह a को घटाने के समान है। समान प्रक्रिया द्वारा, इसे 3 से गुणा या विभाजित किया जा सकता है, जो b को बढ़ाने या घटाने के समान है। इसी प्रकार, c और d को बढ़ाया या घटाया जा सकता है। यह जांचने के लिए कि क्या c जैसा वर्चुअल काउंटर शून्य के समान है, बस वास्तविक काउंटर को 5 से विभाजित करें, देखें कि शेष क्या है, फिर 5 से गुणा करें और शेष को वापस ADD इससे वास्तविक काउंटर अपरिवर्तित रहता है। यदि और केवल यदि c शून्य होता तो शेषफल शून्य नहीं होता है।

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

चेतावनी: *यदि* इसके काउंटरों को n और 0 से प्रारंभ किया गया है, तो 2cm 2ⁿ की गणना नहीं कर सकता है

यह परिणाम, n के अन्य कार्यों की सूची के साथ है जो दो-काउंटर मशीन द्वारा गणना योग्य नहीं हैं - जब काउंटर में n और दूसरे में 0 के साथ आरंभ किया जाता है - जैसे कि n², sqrt(N), log₂(n), आदि, श्रोएप्पेल (1972) के पेपर में दिखाई देते हैं। परिणाम आश्चर्यजनक नहीं है, क्योंकि दो-काउंटर मशीन मॉडल (मिन्स्की द्वारा) केवल तभी सार्वभौमिक सिद्ध हुआ था जब तर्क n को ट्यूरिंग मशीन का अनुकरण करने के लिए उचित रूप से एन्कोड किया गया था (गोडेलाइज़ेशन द्वारा) जिसके प्रारंभिक टेप में n यूनरी में एनकोडेड था; इसके अतिरिक्त, दो-काउंटर मशीन का आउटपुट समान रूप से एन्कोड किया जाता है। यह घटना गणना के बहुत छोटे आधारों के लिए विशिष्ट है जिनकी सार्वभौमिकता केवल अनुकरण द्वारा सिद्ध होती है (उदाहरण के लिए, अनेक ट्यूरिंग टारपिट, सबसे छोटी ज्ञात सार्वभौमिक ट्यूरिंग मशीनें, आदि)।

प्रमाण से पहले कुछ रोचक प्रमेय दिए गए हैं:

• प्रमेय: तीन-काउंटर मशीन ट्यूरिंग मशीन का अनुकरण कर सकती है (पृष्ठ 2, सीएफ मिन्स्की 1967:170-174 भी)
• प्रमेय: 3CM [तीन-काउंटर मशीन] वैरीएबल के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकती है। यह तर्क से प्रारंभ होता है [अर्थात्। n] काउंटर में, और (यदि यह रुकता है) उत्तर छोड़ देता है [अर्थात। f(n)] काउंटर में होता है। (पृ. 3)
• प्रमेय: काउंटर मशीन को 2CM [दो-काउंटर मशीन] द्वारा सिम्युलेटेड किया जा सकता है, परंतु इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए [P। 3; अस्पष्ट कोडिंग 2^W3^X5^Y7^Z है: जहां सिम्युलेटेड काउंटर W, X, Y, Z हैं]
• प्रमेय: किसी भी काउंटर मशीन को 2CM द्वारा सिम्युलेटेड किया जा सकता है, परंतु इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए। (पृ. 3)
  • परिणाम: 2CM के लिए हाल्टिंग समस्या हल नहीं हो सकी है।
  • परिणाम: 2CM तर्क के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, परंतु इनपुट को 2^N के रूप में कोडित किया गया हो और आउटपुट (यदि मशीन रुकती है) को 2 के रूप में कोडित किया गया है. (पृ. 3)
• प्रमेय: कोई भी दो काउंटर मशीन नहीं है जो 2ⁿ की गणना करती हो [यदि काउंटर को n से प्रारंभ किया गया है]। (पृ. 11)

दूसरे प्रमेय के संबंध में कि A 3CM किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, लेखक पाठक को कठिन समस्या के साथ चुनौती देता है: केवल तीन काउंटरों का उपयोग करके दो संख्याओं को गुणा करें (पृष्ठ 2)। मुख्य प्रमाण में यह धारणा सम्मिलित है कि दो-काउंटर मशीनें गैर-रेखीय विकास दर (पृष्ठ 15) अर्थात फ़ंक्शन 2^X के साथ अंकगणितीय अनुक्रमों की गणना नहीं कर सकती हैं किसी भी अंकगणितीय प्रगति की तुलना में अधिक तेज़ी से बढ़ता है। (पृ. 11).

गणना द्वारा गणना का व्यावहारिक उदाहरण

फ्रिडेन ईसी-130 कैलकुलेटर में कोई योजक तर्क नहीं था। इसका तर्क अत्यधिक क्रमबद्ध था, गणना द्वारा अंकगणित आंतरिक रूप से, दशमलव अंक मूलांक-1 थे - उदाहरण के लिए, छह को उस अंक के लिए आवंटित समय स्लॉट के अन्दर निरंतर छह दालों द्वारा दर्शाया गया था। प्रत्येक टाइम स्लॉट में अंक होता है, जो पहले सबसे कम महत्वपूर्ण होता है। कैरीज़ ने फ्लिप-फ्लॉप सेट किया जिसके कारण अगले टाइम स्लॉट में अंक में गणना जुड़ गई थी।

जोड़ना अप-काउंटर द्वारा किया गया था, जबकि घटाव डाउन-काउंटर द्वारा उधार से निपटने के लिए समान योजना के साथ किया गया था।

टाइम स्लॉट योजना ने 13 दशमलव अंकों के छह रजिस्टरों को परिभाषित किया था, जिनमें से प्रत्येक में साइन बिट था।

गुणा और भाग मूल रूप से पुनरावृति जोड़ और घटाव द्वारा किया जाता था। इस प्रकार वर्गमूल संस्करण, EC-132, निरंतर विषम पूर्णांकों को प्रभावी विधि से घटाता है, प्रत्येक वृद्धि के लिए निरंतर दो घटाव की आवश्यकता होती है। पहले के पश्चात्, दूसरे घटाव से पहले न्यूनतम में की वृद्धि की गई थी।

यह भी देखें

• पॉइंटर मशीन
• पोस्ट-ट्यूरिंग मशीन
• रैंडम-एक्सेस मशीन
• रजिस्टर मशीन
• वांग बी-मशीन

संदर्भ

• George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
• Arthur Burks, Herman Goldstine, John von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, mcGraw-Hill Book Company, New York. ISBN 0-07-004357-4 .
• Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354–375.
• Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
• Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365–399.
• Fischer, Patrick C.; Meyer, A. R.; Rosenberg, Arnold L. (1968), "Counter machines and counter languages", Mathematical Systems Theory, 2 (3): 265–283, doi:10.1007/bf01694011, MR 0235932, S2CID 13006433. Develops time hierarchy and space hierarchy theorems for counter machines, analogous to the hierarchies for Turing machines.
• J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
• Hopcroft, John; Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation (1st ed.). Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
• Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
• Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
• Joachim Lambek (1961, received 15 June 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295–302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
• Z. A. Melzak (1961, received 15 May 1961), An informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
• Marvin Minsky (1961). "Recursive Unsolvability of Post's Problem of "Tag" and Other Topics in Theory of Turing Machines". Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
• Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
• John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association for Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".
  • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
  • Ershov, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
  • Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
  • Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
• A. Schönhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schönhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc.
• Rich Schroeppel, May 1972, "A Two counter Machine Cannot Calculate 2^N", Massachusetts Institute of Technology, A. I. Laboratory, Artificial Intelligence Memo #257. The author references Minsky 1967 and notes that "Frances Yao independently proved the non-computability using a similar method in April 1971."
• Peter van Emde Boas, Machine Models and Simulations pp. 3–66, appearing in:

Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990.

van Emde Boas' treatment of SMMs appears on pp. 32-35. This treatment clarifies Schōnhage 1980 -- it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.

• Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63–92. Presented at the meeting of the Association, June 23–25, 1954.

बाहरी संबंध

• Weisstein, Eric W. "Register machine". MathWorld.
• Igblan - Minsky Register Machines