सशर्त शाखाओं को ट्यूरिंग-पूर्णता की आवश्यकता है?

Question

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

जर्मन Z3 और ENIAC के बारे में पढ़ना, विकिपीडिया का कहना है:

जर्मन जेड 3 (मई 1941 में काम कर दिखाया गया है) कोनराड झूस द्वारा डिजाइन किया गया था। यह पहला सामान्य उद्देश्य डिजिटल कंप्यूटर था, लेकिन यह इलेक्ट्रोमेकनिकल था, इलेक्ट्रॉनिक के बजाय, क्योंकि यह सभी फ़ंक्शंस के लिए रिले का उपयोग करता था। यह बाइनरी गणित का उपयोग करके तार्किक रूप से गणना की गई। यह पेंच टेप द्वारा प्रोग्राम करने योग्य था, लेकिन सशर्त शाखा की कमी थी। ट्यूरिंग-पूर्णता के लिए डिज़ाइन नहीं किया गया है, यह गलती से था, क्योंकि यह 1 99 8 में पाया गया था (लेकिन टूरिंग-पूर्णता, जटिल, चालाक हैक्स आवश्यक थे) का फायदा उठाने के लिए।

क्या जटिल, चालाक हैक्स, बिल्कुल?

एक 1998 कागज सार आर रोजास से भी कहा गया है (ध्यान दें कि मैं इस पत्र नहीं पढ़ा है, यह आईईईई से सिर्फ एक टुकड़ा है।):

कंप्यूटिंग मशीन जेड 3, कोनराड झूस द्वारा बनाया गया 1 9 38 और 1 9 41 के बीच, फ्लोटिंग पॉइंट अंकगणितीय परिचालन (अतिरिक्त, घटाव, गुणा, विभाजन, और वर्ग रूट) के केवल निश्चित अनुक्रमों को निष्पादित कर सकता है) एक पेंच टेप में कोडित। पूछने के लिए दिलचस्प सवाल, कंप्यूटिंग के इतिहास के दृष्टिकोण, यह है कि ये ऑपरेशन सार्वभौमिक गणना के लिए पर्याप्त हैं या नहीं। पेपर दिखाता है कि, वास्तव में, इन अंकगणितीय निर्देश वाले एकल प्रोग्राम लूप किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है जिसका टेप का सीमित आकार दिया गया है। यह द्वारा सशर्त शाखाकरण अनुकरण और अप्रत्यक्ष पते अंकगणितीय माध्यमों द्वारा किया जाता है। ज़्यूज़ का Z3 है, कम से कम सिद्धांत में, आज के कंप्यूटर के रूप में सार्वभौमिक है कि में एक बाध्य संबोधित स्थान है।

संक्षेप में, सॉर्स, ट्यूरिंग-पूर्णता के लिए किस प्रकार की शाखाओं की आवश्यकता है? असीमित स्मृति मानते हुए, केवल goto या jmp शाखा निर्माण के साथ एक भाषा (कोई if या jnz संरचनाएं) ट्यूरिंग-पूर्ण माना जा सकता है?

Answer 1

मूल रोजास पेपर here पाया जा सकता है। मूल विचार यह है कि Z3 केवल एक बिना शर्त एकल लूप का समर्थन करता है (निर्देश टेप के सिरों को एक साथ जोड़कर)। आप सभी कोड अनुभागों को लूप में एक के बाद एक करके डालकर सशर्त निष्पादन बनाते हैं, और एक वेरिएबल जेड रखते हैं जो निर्धारित करता है कि कौन से सेक्शन को निष्पादित करना है। खंड जे की शुरुआत में, आप

if (z==j) then t=0 else t=1 

सेट करें और फिर इस खंड में प्रत्येक असाइनमेंट a = b op c

a = a*t + (b op c)*(1-t) 

पढ़ कर (अर्थात् प्रत्येक असाइनमेंट नो-सेशन, सक्रिय खंड को छोड़कर) है। अब, इसमें अभी भी एक सशर्त असाइनमेंट शामिल है: z == j की तुलना कैसे करें? उन्होंने कहा कि इस उत्पाद को 1 हो जाएगा j (c1..cm) का नकार द्विआधारी प्रतिनिधित्व के साथ जेड (z1..zm) की बाइनरी प्रतिनिधित्व उपयोग करने के लिए, और उसके बाद की गणना

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm)) 

का प्रस्ताव केवल तभी सी और z सभी बिट्स में भिन्न होता है, जो केवल तभी होगा जब z == j। जेड (जो अनिवार्य रूप से अप्रत्यक्ष कूद है) को असाइनमेंट भी z1..zm को असाइन करना होगा।

रोजजा ने Conditional Branching is not Necessary for Universal Computation in von Neumann Computers भी लिखा है। वहां वह स्व-संशोधित कोड और रिश्तेदार पते के साथ एक मशीन का प्रस्ताव करता है, ताकि आप स्मृति से ट्यूरिंग निर्देश पढ़ सकें और प्रोग्राम को तदनुसार कूदने के लिए संशोधित कर सकें। एक विकल्प के रूप में, वह उपरोक्त दृष्टिकोण (Z3 के लिए) का प्रस्ताव करता है, जो एक संस्करण में केवल लोड (ए), स्टोर (ए), आईएनसी और डीईसी का उपयोग करता है।

Answer 2

जेड 3 केवल एक सार बिंदु से पूर्ण ट्यूरिंग था। आप एक मनमाने ढंग से लंबे कार्यक्रम टेप कर सकते हैं और बस यह हर सशर्त शाखा के दोनों पक्षों की गणना करें। दूसरे शब्दों में, प्रत्येक शाखा के लिए, यह दोनों उत्तरों की गणना करेगा और आपको बताएगा कि कौन सा अनदेखा करना है।जाहिर है, यह आपके पास हर सशर्त शाखा के लिए तेजी से बड़े कार्यक्रम तैयार करता है, ताकि आप कभी भी इस मशीन को ट्यूरिंग-पूर्ण तरीके से उपयोग न कर सकें।

Answer 3

आपको कुछ ऐसी चीज चाहिए जो इनपुट (परिणाम से) इनपुट के आधार पर शाखा कर सके।

सशर्त शाखाओं को अनुकरण करने का एक तरीका स्व-संशोधित कोड के साथ है - आप एक गणना करते हैं जो इसके परिणाम को निष्पादित किए जा रहे निर्देशों की धारा में जमा करता है। आप निर्देश स्ट्रीम में बिना शर्त कूद के लिए ओप-कोड डाल सकते हैं, और इनपुट के लिए शर्तों के कुछ सेट के आधार पर उस कूद के लिए सही लक्ष्य बनाने के लिए इनपुट पर गणित कर सकते हैं। उदाहरण के लिए, वाई से एक्स घटाएं, अगर यह सकारात्मक था, तो 0-भरने के लिए सही स्थानांतरित करें, या 1-भरना अगर यह नकारात्मक था, तो आधार पता जोड़ें, और जेएमपी ओप-कोड के तुरंत बाद उस परिणाम को स्टोर करें। जब आप उस jmp पर जाते हैं, तो आप x == y, और दूसरा अगर x! = Y पर एक पते पर जाएंगे।

Answer 4

यदि आपके पास केवल अंकगणितीय अभिव्यक्तियां हैं तो आप अंकगणितीय परिचालनों के कुछ गुणों का उपयोग कर सकते हैं। उदा।, A कुछ शर्त (जिसे पहले गणना की गई है) के आधार पर 0 या 1 है, तो A*B+(1-A)*C अभिव्यक्ति if A then B else C की गणना करता है।

Answer 5

यदि आप अपने goto या jmp के लिए पता गणना कर सकते हैं, तो आप आर्बेटरी सशर्त अनुकरण कर सकते हैं। मैंने कभी-कभी ज़ेडएक्स बेसिक में "ऑन एक्स गोटो ए, बी, सी" अनुकरण करने के लिए इसका इस्तेमाल किया।

हैं "सही" संख्यात्मक मूल्य 1 और "गलत" है 0 है, तो एक निर्माण की तरह:

goto C+(B-C)*A 

तो, हाँ, के साथ एक "अभिकलन:

if A then goto B else goto C 

समान है गोटो "या स्वयं संशोधित करने की क्षमता, एक गोटो या जेएम सशर्त के रूप में कार्य कर सकते हैं।

Answer 6

आप एक ट्यूरिंग-पूर्ण मशीन का निर्माण करने की शाखाओं में सशर्त की जरूरत नहीं है, लेकिन निश्चित रूप से किसी भी ट्यूरिंग-पूर्ण मशीन एक मुख्य सुविधा के रूप में सशर्त शाखाओं में प्रदान करेगा।

यह साबित कर दिया था कि सिस्टम Rule 110 Cellular Automaton के रूप में सरल रूप में एक ट्यूरिंग मशीन लागू करने के लिए इस्तेमाल किया जा सकता। आपको निश्चित रूप से बिट बाल्टी से ऐसी प्रणाली खींचने के लिए सशर्त शाखा की आवश्यकता नहीं है। असल में कोई भी a bunch of rocks का उपयोग कर सकता है।

मुद्दा यह है कि एक ट्यूरिंग मशीन सशर्त शाखाओं में प्रदान करेगा, तो क्या आप को साबित करने ट्यूरिंग पूर्णता कुछ हद तक सशर्त शाखाओं में लागू कर रहा है द्वारा वैसे भी कर रहे हैं। आपको किसी बिंदु पर सशर्त शाखाओं के बिना ऐसा करना है, चाहे वह अर्ध-कंडक्टर में चट्टानों या पीएन-जंक्शन हों।

Answer 7

यदि कोई मशीन शाखा कर सकती है, तो हाँ इसकी ट्यूरिंग पूर्ण हो जाती है।

होवर भी ऐसी मशीनें हैं जो शाखा को कूद नहीं सकती हैं या यहां तक ​​कि अगर भी अभी भी ट्यूरिंग पूरी हो रही हैं।

सशर्त-शाखा होने का कारण स्वचालित रूप से किसी भी कंप्यूटर को ट्यूरिंग पूर्ण बनाता है।

प्रसंस्करण आउटपुट का चयन करने के लिए इनपुट इन-ऑर्डर की पहचान करने की प्रक्रिया है।

शाखाओं में बंटी एक तरह से इस प्रक्रिया को mentalize है, कूद की हालत क्या, आदानों वर्गीकृत कर सकते हैं जगह आप शाखा भी है कि निवेश के लिए सही उत्पादन संग्रहीत करता है।

तो अंत में स्पष्ट करने के लिए; यदि आपके कंप्यूटर को सशर्त शाखा बनाना आवश्यक है तो यह कम्प्यूटेशनल रूप से समकक्ष है। हालांकि, कंप्यूटर पूर्णता प्राप्त करने के लिए कई अन्य तरीके हैं। (लैम्ब्डा, आईएफ, सीएल)