ट्यूरिंग मशीन समकक्ष

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

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

ट्यूरिंग मशीन मॉडल के समतुल्य मशीन

ट्यूरिंग तुल्यता

विभिन्न मशीन जिनके विषय में सोचा जा सकता है कि उनमें साधारण सार्वभौमिक ट्यूरिंग मशीन की तुलना में अधिक कम्प्यूटेशनल क्षमता है, उन्हें दिखाया जा सकता है कि उनमें अधिक शक्ति नहीं है। वह संभवतः तेजी से गणना कर सकते हैं या कम मेमोरी का उपयोग कर सकते हैं या उनका निर्देश समुच्चय छोटा हो सकता है, किन्तु वह अधिक शक्तिशाली विधि से गणना नहीं कर सकते (अर्थात अधिक गणितीय कार्य)। (चर्च-ट्यूरिंग थीसिस इसे सत्य मानती है: जो कुछ भी "गणना" किया जा सकता है उसकी गणना कुछ ट्यूरिंग मशीन द्वारा की जा सकती है।)

अनुक्रमिक-मशीन मॉडल'

निम्नलिखित सभी को समानांतर मशीन मॉडल से पृथक करने के लिए अनुक्रमिक मशीन मॉडल कहा जाता है।

टेप-आधारित ट्यूरिंग मशीन

ट्यूरिंग का ए-मशीन मॉडल

ट्यूरिंग की मशीन (जैसा कि उन्होंने इसे कहा था) बाएँ किनारे वाली, दाएँ किनारे वाली इनफिनिट थी। उन्होंने बाएं छोर को चिह्नित करने के लिए əə प्रतीक प्रदान किए थे। टेप प्रतीकों की सीमित संख्या की अनुमति थी। निर्देश (यदि सार्वभौमिक मशीन) और इनपुट और आउट केवल F-स्क्वायर पर लिखे गए थे और मार्कर E-स्क्वायर पर दिखाई देने थे। संक्षेप में उन्होंने अपनी मशीन को दो टेपों में विभाजित किया जो सदैव साथ घूमते थे। निर्देश 5-टुपल्स नामक सारणीबद्ध रूप में प्रकट हुए और क्रमिक रूप से निष्पादित नहीं किए गए थे।

प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीन

यह निम्नलिखित मॉडल एकल टेप ट्यूरिंग मशीन हैं, किन्तु (i) प्रतिबंधित टेप प्रतीकों {चिह्न, रिक्त}, और/या (ii) अनुक्रमिक, कंप्यूटर-जैसे निर्देश, और (iii) पूर्णतः परमाणुकृत मशीन-क्रियाओं से प्रतिबंधित हैं।

पोस्ट का सूत्रीकरण 1 गणना का मॉडल

Further information: पोस्ट-ट्यूरिंग मशीन

एमिल पोस्ट ने कम्प्यूटेशनल प्रक्रिया के स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-पक्षीय इनफिनिट से दाईं ओर इनफिनिट कमरों के समुच्चय में परिवर्तित कर दिया था| जिनमें से प्रत्येक में दोनों दिशाओं में पेपर की शीट थी। इस प्रकार उन्होंने ट्यूरिंग 5-टुपल्स को 4-टुपल्स में विभाजित कर दिया था मोशन निर्देश प्रिंट/इरेज़ निर्देशों से प्रथक चूँकि उनका 1936 मॉडल इस विषय में अस्पष्ट है, पोस्ट के 1947 मॉडल को अनुक्रमिक निर्देश निष्पादन की आवश्यकता नहीं थी।

उनका अत्यधिक सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है और चूँकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से बहुत ही मौलिक प्रोग्राम योग्य कंप्यूटर और संबंधित प्रोग्रामिंग लैंग्वेज का फॉर्मूलेशन है, जिसमें बॉक्स अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं और प्रोग्राम का निर्माण करने वाले निर्देशों का समुच्चय प्रयुक्त होते है।

वांग मशीन

Further information: वांग बी-मशीन

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

{ शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, इरेज-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }

और निर्देश-समुच्चय के साथ उनकी सबसे कठोरता से कम की गई 4-निर्देश वांग बी-मशीन (बेसिक के लिए बी)

{ शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }

जिसमें इरेज-स्क्वायर निर्देश भी नहीं है।

विभिन्न लेखकों ने पश्चात में वांग द्वारा विचार की गई मशीनों के वेरिएंट प्रस्तुत किए:

मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने संस्करण के साथ वांग की धारणा को विकसित किया था| इस प्रकार जो भिन्न-भिन्न सिरों की शिफ्ट-बाएं और शिफ्ट-दाएं गति की अनुमति देता है, किन्तु बिल्कुल भी मुद्रण नहीं करता है। इस स्थिति में टेप बाएं किनारे वाले होंगे, प्रत्येक किनारे पर अंत को संकेत करने के लिए चिन्ह होगा। वह इसे ही टेप तक सीमित करने में सक्षम था, किन्तु अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = इन्क्रीमेंट} के अतिरिक्त गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को प्रयुक्त करने की मूल्य पर प्रयुक्त किया जाता है।

डेविस ने वांग द्वारा विचार की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-समुच्चय के साथ मॉडल का उपयोग किया था

{शिफ्ट-बाएं, शिफ्ट-दाएं, इरेज, चिह्नित करें, वर्ग-चिह्नित xxx पर जम्प, xxx पर जम्प, रुकें }

और 2 से बड़े आकार के टेप-अक्षरों वाले वर्जन पर भी विचार किया गया।

बोहम की सैद्धांतिक मशीनी लैंग्वेज पी

Further information: पी"

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

मल्टी-टेप ट्यूरिंग मशीन

Further information: मल्टीटेप ट्यूरिंग मशीन

व्यावहारिक विश्लेषण में विभिन्न प्रकार की मल्टी-टेप ट्यूरिंग मशीनों का अधिकांशतः उपयोग किया जाता है। मल्टी-टेप मशीन सिंगल-टेप मशीनों के समान होती हैं, किन्तु कुछ स्थिर k संख्या में स्वतंत्र टेप होते हैं।

नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीन

Further information: गैर-नियतात्मक ट्यूरिंग मशीन

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

ओब्लिवियस ट्यूरिंग मशीन

ओब्लिवियस ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में पूर्व निर्धारित क्रम होता है, जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। इस प्रकार किसी भी स्टेज पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन स्टेज में की जा सकती है, उसे ओब्लिवियस दो-टेप ट्यूरिंग मशीन द्वारा n स्टेज में किया जा सकता है। $O(n\log n)$ स्टेज ऑब्लिवियस मशीनें कॉम्बिनेशन लॉजिक परिपथ के साथ स्टेज-वार रैखिक फैशन में मेल खाती हैं, जब संक्रमण टेबल की काम्प्लेक्स को स्थिर माना जाता है। इस प्रकार आकार $O(n\log n)$ और डेप्थ $O(n)$ में परिपथ समस्याओं के रूप में गणना करना संभव है (परिपथ काम्प्लेक्स देखें)। यह कुक और लेविन के मूल $O(n^{3})$ परिणाम में सुधार करता है।

रजिस्टर मशीन मॉडल

Further information: रजिस्टर मशीन

पीटर वैन एम्डे बोस इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में सम्मिलित करते हैं। चूँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे मौलिक सदस्य अर्थात काउंटर मशीन को रजिस्टर मशीन भी कहा है और काउंटर मशीन के सबसे मौलिक आगमन को कभी-कभी मिन्स्की मशीन कहा जाता है।

काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है

Further information: काउंटर मशीन

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

मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने पृथक प्रकार की सरल मशीन का निर्माण किया था, इस प्रकार जिसमें पोस्ट-ट्यूरिंग टेप से विभिन्न बाएं छोर वाले टेप काटे गए थे। सभी स्थितियों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।

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

इस मॉडल में सिंगल-एंडेड टेप-एज़-रजिस्टर को काउंटर के रूप में माना जाता है, उनके निर्देश केवल दो तक सीमित होते हैं (या यदि टेस्ट/डिक्रीमेंट निर्देश को परमाणुकृत किया जाता है तब तीन)। दो सामान्य निर्देश समुच्चय निम्नलिखित हैं:

(1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, अर्थात।

{रजिस्टर #r की कंटेंट में इन्क्रीमेंट; रजिस्टर #r की कंटेंट में कमी ; यदि #r=शून्य की कंटेंट है| तब निर्देश #z पर जाएं}

(2): { CLR ( r ); INC ( r ); JE ( r_i, r_j, z ) }, i.e., अर्थात्।

{रजिस्टर r की स्पष्ट कंटेंट; r की कंटेंट में इन्क्रीमेंट; r_i को r_j की कंटेंट की तुलना करें और यदि समान है| तब निर्देश z पर जाएं}

यद्यपि उनका मॉडल इस सरल विवरण से अधिक सम्मिश्र है, मेल्ज़ाक पेब्बल मॉडल ने बहु-विषयकता की अनुमति देने के लिए काउंटर की इस धारणा को बढ़ाया था। इस स्थिति में पेब्बल जोड़ता और घटाता है।

रैंडम-एक्सेस मशीन (रैम) मॉडल

Further information: रैंडम-एक्सेस मशीन

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

(चूँकि निर्देशों की गोडेल नंबरिंग के साथ मिन्स्की ने प्रमाण प्रस्तुत किया कि ऐसी नंबरिंग के साथ सामान्य रिकर्सन (कंप्यूटर विज्ञान) वास्तव में संभव था| वह प्रमाण प्रस्तुत करता है कि μ रिकर्सन वास्तव में संभव है).

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

वैन एम्डे बोस विभिन्न रैम मॉडल को विभिन्न उप-प्रकारों में विभाजित करता है:

• एसआरएएम, केवल अंकगणितीय निर्देश के साथ सकसेस्सर रैम, सकसेस्सर (इन्क्रीमेंट h) अन्य में क्लियर h और IF समानता-मध्य-रजिस्टर सम्मिलित है, फिर xxx पर जाएं।

• रैम: जोड़ और घटाव के साथ मानक मॉडल
• एमरैम: रैम गुणा और भाग के साथ संवर्धित होती है
• बीरैम एमबीरैम: बीरैम और एमबीरैम के बिटवाइज़ बूलियन वर्जन
• एन****: नाम से पहले N के साथ उपरोक्त में से किसी का गैर-नियतात्मक वर्जन

रैंडम-एक्सेस स्टोर्ड प्रोग्राम (आरएएसपी) मशीन मॉडल

Further information: रैंडम-एक्सेस स्टोर्ड-प्रोग्राम मशीन

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

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

{ INC ( r ), COPY ( r_i, r_j ), JE ( r_i, r_i, z ) }

आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 3 के साथ लोड करें। निर्देश अत्यधिक प्रतिबंधित समुच्चय के हो सकते हैं, जैसे कि हार्टमैनिस के निम्नलिखित 16 निर्देश यह मॉडल संचायक a का उपयोग करता है। निमोनिक्स वह हैं जिनका उपयोग लेखकों ने किया है (उनका सीएलए स्थिर या रजिस्टर से लोड संचायक है; एसटीओ स्टोर संचायक है)। इस प्रकार जंप को छोड़कर, उनका सिंटैक्स निम्नलिखित है: n, <n>, <<n>> तत्काल, प्रत्यक्ष और अप्रत्यक्ष के लिए)। जंप दो ट्रांसफर निर्देशों टीआरए के माध्यम से होते हैं सीधे n या परोक्ष रूप से बिना नियम जंप < n > निर्देश काउंटर, टीआरजेड में रजिस्टर n की कंटेंट को जैमिंग करना (यदि टीआरए के समान ही एक्युमुलेटर शून्य है, तब नियमबद्ध जंप है|):

{ ADD n , ADD < n >, ADD << n >>, SUB n, SUB < n >, SUB << n >>, CLA n, CLA < n >, CLA << n >>, STO < n >, STO << n >>, TRA n, TRA < n >, TRZ n, TRA < n >, HALT }

पॉइंटर मशीन मॉडल

Further information: पॉइंटर मशीन

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

इनपुट और आउटपुट वाली मशीन

उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं, जिन्हें इनपुट λ₀,L₁और आउटपुट β कहा जाता है

ट्रेडिशनल मॉडल के साथ मल्टी-टेप मशीनों पर सबलीनियर स्पेस काम्प्लेक्स का अध्ययन करना कठिन है क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार छोटी डीएसपीएसीई कक्षाओं का अध्ययन करने के लिए हमें पृथक मॉडल का उपयोग करना चाहिए। कुछ अर्थों में यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तब हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तब हम इस स्थान के लिए स्वयं को आवेशित नहीं करना चाहते हैं।

हम इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीन प्रस्तुत करके इस समस्या का समाधान करते हैं। यह साधारण K-स्ट्रिंग ट्यूरिंग मशीन के समान है, अतिरिक्त ट्रांज़िशन फ़ंक्शन के δ प्रतिबंधित है, जिससे इनपुट टेप को कभी भी परिवर्तित नही किया जा सकता है और जिससे आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों के समान ही समय काम्प्लेक्स होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में:

किसी भी k-स्ट्रिंग ट्यूरिंग मशीन M के लिए जो समयबद्ध $f(n)$ के अन्दर कार्य करती है, इनपुट और आउटपुट के साथ $(k+2)$-स्ट्रिंग ट्यूरिंग मशीन M' है, जो समयबद्ध $O(f(n))$ के अन्दर कार्य करती है।

इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीनों का उपयोग काम्प्लेक्स संसाधन डीएसपीएसीई की फॉर्मल परिभाषा में किया जा सकता है।

अन्य समकक्ष मशीन और विधियाँ

• बहुआयामी ट्यूरिंग मशीन: उदाहरण के लिए शॉनहेज का मॉडल चार हेड-मूवमेंट कमांड {उत्तर, दक्षिण, पूर्व, पश्चिम} का उपयोग करता है।
• सिंगल-टेप, मल्टी-हेड ट्यूरिंग मशीन: टैग की समस्या के अनिर्णय प्रमाण में, मिन्स्की और शेफर्डसन और स्टर्गिस ने ही टेप वाली मशीनों का वर्णन किया था| जो हेड के साथ टेप के साथ पढ़ सकती थीं और दूसरे के साथ टेप के साथ आगे लिख सकती थीं।
• मार्कोव एल्गोरिथ्म और उल्लेखनीय सरल कम्प्यूटेशनल मॉडल है, जो ट्यूरिंग मशीनों के समकक्ष स्ट्रिंग पुनर्लेखन पर आधारित है।
• लैम्ब्डा कैलकुलस
• केवे ऑटोमेशन