काउंटर मशीन

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

बुनियादी सुविधाएँ

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

• सीएलआर (आर): क्लियर रजिस्टर आर। (आर को शून्य पर सेट करें।)
• आईएनसी (आर): रजिस्टर आर की सामग्री को बढ़ाएं।
• डीईसी (आर): रजिस्टर आर की सामग्री को घटाएं।
• सीपीवाई (आर_j, आर_k): रजिस्टर आर की सामग्री को कॉपी करें_jआर पंजीकृत करने के लिए_kआर की सामग्री को छोड़कर_jअखंड।
• जेजेड (आर, जेड): यदि रजिस्टर आर में शून्य है तो निर्देश जेड पर जाएं अन्यथा क्रम में जारी रखें।
• जेई (आर_j, आर_k, z): यदि रजिस्टर आर की सामग्री_jरजिस्टर आर की सामग्री के बराबर है_kफिर निर्देश पर जाएं अन्यथा क्रम से जारी रखें।

इसके अलावा, मशीन में आमतौर पर HALT निर्देश होता है, जो मशीन को रोक देता है (आमतौर पर परिणाम की गणना के बाद)।

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

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

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

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

Main article: Counter-machine model

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

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

  {आईएनसी (आर), डीईसी (आर), सीएलआर (आर), सीपीवाई (आर)।_j, आर_k ), जेएनजेड (आर, जेड), जे (जेड)}

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

  { INC ( r, z ), JZDEC ( r, z_true, साथ_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, साथ_false ) }

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

  { INC ( r, z ), JZDEC ( r, z_true, साथ_false ) }

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

  {सीएलआर (आर), आईएनसी (आर), जेई (आर)।_j, आर_k, z ) }

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

  { आईएनसी (आर), सीपीवाई (आर_s, आर_d ), जेई (आर_j, आर_k, z ) }

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

औपचारिक परिभाषा

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

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

{वृद्धि (आर), कमी (आर), स्पष्ट (आर); कॉपी (आर_j,आर_k), यदि r=0 की सामग्री है तो सशर्त छलांग, यदि r की सामग्री है तो सशर्त छलांग_j=आर_k, बिना शर्त कूदो, रुको }

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

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

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

• सीएलआर (जे): रजिस्टर आर की सामग्री साफ़ करें_jशून्य करने के लिए.
• जे (जेड): बिना शर्त निर्देश I पर जाएं_z.
• सीपीवाई (एस, डी): स्रोत रजिस्टर आर की सामग्री की प्रतिलिपि बनाएँ_sगंतव्य रजिस्टर आर के लिए_d. (वन-इंस्ट्रक्शन सेट कंप्यूटर#ट्रांसपोर्ट ट्रिगर आर्किटेक्चर देखें)

बाद में आर_sइसमें इसकी मूल गणना शामिल होगी (MOVE के विपरीत जो स्रोत रजिस्टर को खाली कर देता है, यानी इसे शून्य पर साफ़ कर देता है)।

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

Instruction	Effect on register "j"	Effect on Instruction Counter Register ICR	Summary
INC ( j )	[j] +1 → j	[IC] +1 → IC	Increment contents of register j; next instruction
DEC ( j )	[j] -1 → j	[IC] +1 → IC	Decrement contents of register j; next instruction
JZ ( j, z)		IF [j] = 0 THEN Iz → IC ELSE [IC] +1 → IC	If contents of register j=0 then instruction z else next instruction
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	← Instruction number (address)
															JZ	DEC	INC	INC	JZ	JZ	DEC	INC	JZ	H	← Instruction
															2	2	3	1	0	1	1	2	0		← Register number
															6				1	10			6		← Jump-to instruction number
step		IC	Inst #	reg #	J-addr		reg0	reg1	reg2	reg3	reg4		IC
start							0	0	2	0	0		1												move [#2] to #1 and #3:
1		1	JZ	2	6		0	0	2	0	0		1→2		JZ										Jump fails: register #2 contains 2
2		2	DEC	2	0		0	0	2→1	0	0		2→3			DEC									Decrement register #2 from 2 to 1
3		3	INC	3	0		0	0	1	0→1	0		3→4				INC								Increment register #3 from 0 to 1
4		4	INC	1	0		0	0→1	1	1	0		4→5					INC							Increment register #1 from 0 to 1
5		5	JZ	0	1		0	1	1	1	0		5→1						JZ						U-Jump: register #0 is empty
6		1	JZ	2	6		0	1	1	1	0		1→2		JZ										Jump fails: register #2 contains 1
7		2	DEC	2	0		0	1	1→0	1	0		2→3			DEC									Decrement register #2 from 1 to 0
8		3	INC	3	0		0	1	0	1→2	0		3→4				INC								Increment register #3 from 1 to 2
9		4	INC	1	0		0	1→2	0	2	0		4→5					INC							Increment register #1 from 1 to 2
10		5	JZ	0	1		0	2	0	2	0		5→1						JZ						U-Jump: register #0 is empty
11		1	JZ	2	6		0	2	0	2	0		1→6		JZ										Jump !: register #2 is empty
																									move [1] to 2:
12		6	JZ	1	10		0	2	0	2	0		6→7							JZ					Jump fails: register #1 contains 2
13		7	DEC	1	0		0	2→1	0	2	0		7→8								DEC				Decrement register #1 from 2 to 1
14		8	INC	2	0		0	1	0→1	2	0		8→9									INC			Increment register #2 from 0 to 1
15		9	JZ	0	6		0	1	1	2	0		9→6										JZ		U-Jump: register #0 is empty
16		6	JZ	1	10		0	1	1	2	0		6→7							JZ					Jump fails: register #1 contains 1
17		7	DEC	1	0		0	1→0	1	2	0		7→8								DEC				Decrement register #1 from 1 to 0
18		8	INC	2	0		0	0	1→2	2	0		8→9									INC			Increment register #2 from 1 to 2
19		9	JZ	0	6		0	0	2	2	0		9→6										JZ		U-Jump: register #0 is empty
20		6	JZ	1	10		0	0	2	2	0		6→10							JZ					Jump !: register #1 is empty
21		10	H	0	0		0	0	2	2	0		10→10											H	HALT

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

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

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

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

{जे, दिसंबर, इंक, जेजेड, एच }

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

{सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }

• सीओपीवाई को परिभाषित करें (आर_j, आर_k ) आर की सामग्री को संरक्षित करते समय_j उपरोक्त के संदर्भ में:

{ सीपीवाई, सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }

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

• ADD को परिभाषित करें (r_j, आर_k, आर_i ) , (शायद आर की सामग्री को संरक्षित करना_j, और आर_k ), उपरोक्त के उपयोग से:

{जोड़ें, सीपीवाई, सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }

• मल्टीप्लाई को परिभाषित करें (आर_j, आर_k, आर_i ) (एमयूएल) (शायद आर की सामग्री को संरक्षित करना_j, आर_k), उपरोक्त के संदर्भ में:

{एमयूएल, एडीडी, सीपीवाई, सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }

• घातांक को परिभाषित करें (r_j, आर_k, आर_i ) (EXP) (शायद आर की सामग्री को संरक्षित करना_j, आर_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)।

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

• • वेतन वृद्धि (आर); [आर] +1 → आर
  • कमी (आर) ; [आर] -1 → आर
  • साफ़ (आर) ; 0 → आर
  • कॉपी (आर_s आर को_d ) ; [आर_s] → आर_d
  • निर्देश I पर बिना शर्त कूदें_z
  • यदि [r] =0 हो तो निर्देश I पर कूदें_z

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

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

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

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

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

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

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

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

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

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

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

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

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

• प्रमेय: तीन-काउंटर मशीन ट्यूरिंग मशीन का अनुकरण कर सकती है (पृष्ठ 2, सीएफ मिन्स्की 1967:170-174 भी)
• प्रमेय: 3CM [तीन-काउंटर मशीन] चर के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकती है। यह तर्क से शुरू होता है [अर्थात्। एन] काउंटर में, और (यदि यह रुकता है) उत्तर छोड़ देता है [यानी। एफ(एन)] काउंटर में। (पृ. 3)
• प्रमेय: काउंटर मशीन को 2CM [दो-काउंटर मशीन] द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए [पी। 3; अस्पष्ट कोडिंग है: 2^{डब्ल्यू}3^एक्स5^तथा7^Z जहां सिम्युलेटेड काउंटर W, X, Y, Z हैं]
• प्रमेय: किसी भी काउंटर मशीन को 2CM द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए। (पृ. 3)
  • परिणाम: 2CM के लिए रुकने की समस्या हल नहीं हो सकी है।
  • परिणाम: 2CM तर्क के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, बशर्ते इनपुट को 2 के रूप में कोडित किया गया हो^N और आउटपुट (यदि मशीन रुकती है) को 2 के रूप में कोडित किया गया है^{उत्तर}. (पृ. 3)
• प्रमेय: कोई भी दो काउंटर मशीन नहीं है जो 2 की गणना करती हो^एन [यदि काउंटर को एन से प्रारंभ किया गया है]। (पृ. 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