काउंटर मशीन

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

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

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

• 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 से विभाजित करने के समान है, जहां शेष वह बिट है जिसे पॉप किया गया था। दो काउंटर इस स्टैक का अनुकरण कर सकते हैं, जिसमें से काउंटर में संख्या होती है जिसका बाइनरी प्रतिनिधित्व स्टैक पर बिट्स का प्रतिनिधित्व करता है, और दूसरे काउंटर का उपयोग स्क्रैचपैड के रूप में किया जाता है। पहले काउंटर में संख्या को दोगुना करने के लिए, एफएसएम दूसरे काउंटर को शून्य से प्रारंभ कर सकता है, फिर पहले काउंटर को पुनरावृति बार घटा सकता है और दूसरे काउंटर को दो बार बढ़ा सकता है। यह तब तक जारी रहता है जब तक पहला काउंटर शून्य तक नहीं पहुंच जाता है। उस समय, दूसरा काउंटर दोगुनी संख्या रहता है। काउंटर को दो बार घटाकर और दूसरे को बार बढ़ाकर, और तब तक दोहराते हुए जब तक कि पहला काउंटर शून्य तक न पहुंच जाए, हॉल्टिंग की जाती है। शेष को इस बात से निर्धारित किया जा सकता है कि क्या यह सम या विषम संख्या में चरणों के पश्चात् शून्य पर पहुंच गया है, जहां चरणों की संख्या की समता एफएसएम की स्थिति में एन्कोड की गई है।