काउंटर मशीन

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

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

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

सीएलआर (आर): क्लियर रजिस्टर आर। (आर को शून्य पर सेट करें।)
आईएनसी (आर): रजिस्टर आर की सामग्री को बढ़ाएं।
डीईसी (आर): रजिस्टर आर की सामग्री को घटाएं।
सीपीवाई (आर_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))

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

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

काउंटर मशीन मॉडल कई अलग-अलग नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें अलग करने में मदद कर सकते हैं। निम्नलिखित निर्देश में 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 में भी प्रदर्शित किया गया है)।

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

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

लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का सीमित (या कुछ मॉडलों में अनंत) सेट आर₀... आर_n जिनमें से प्रत्येक किसी गैर-नकारात्मक पूर्णांक (0, 1, 2, ... - यानी असीमित) को धारण कर सकता है। रजिस्टर अपना अंकगणित स्वयं करते हैं; या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए रैंडम-एक्सेस मशीन देखें)।
एक राज्य रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से अलग है; इस प्रकार काउंटर मशीन मॉडल हार्वर्ड वास्तुकला का उदाहरण है
लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की सीमित सूची 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 I_z → 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) के भीतर आसानी से किया जाता है (एक उदाहरण μ ऑपरेटर पर पाया जा सकता है)। इसका मतलब यह है कि किसी भी म्यू रिकर्सिव फ़ंक्शन को काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है,^[1] काउंटर मशीन डिज़ाइन के सीमित निर्देश सेट और प्रोग्राम आकार के बावजूद। हालाँकि, आवश्यक निर्माण प्रति-सहज ज्ञान युक्त हो सकता है, यहां तक कि उन कार्यों के लिए भी जिन्हें रैंडम-एक्सेस मशीन जैसी अधिक जटिल रजिस्टर मशीनों में परिभाषित करना अपेक्षाकृत आसान है। ऐसा इसलिए है क्योंकि μ ऑपरेटर असीमित संख्या में बार-बार पुनरावृति कर सकता है, लेकिन कोई भी काउंटर मशीन अपनी निर्देश सूची के सीमित आकार के कारण असीमित संख्या में अलग-अलग रजिस्टरों को संबोधित नहीं कर सकती है।

उदाहरण के लिए, आदिम पुनरावर्ती ऑपरेटरों के उपरोक्त पदानुक्रम को नुथ के अप-एरो नोटेशन में उच्च-क्रम वाले तीर संचालन में घातांक से आगे बढ़ाया जा सकता है। किसी भी निश्चित के लिए $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: चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।

पहले की तरह, काउंटरों में से का उपयोग स्क्रैचपैड के रूप में किया जाता है। दूसरे में पूर्णांक है जिसका

[1]

Anonymous

Search