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

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

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

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

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

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

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

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

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

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

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

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

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

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

Further information: Post–Turing machine

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

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

वांग मशीनें

Further information: Wang B-machine

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

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

और निर्देश-सेट के साथ उनकी सबसे गंभीर रूप से कम की गई 4-निर्देश वांग बी-मशीन (बेसिक के लिए बी)

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

जिसमें ERASE-SQUARE निर्देश भी नहीं है।

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

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

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

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

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

बोहम की सैद्धांतिक मशीनी भाषा पी

Further information: P"

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

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

Further information: Multitape Turing machine

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

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

Further information: non-deterministic Turing machine

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

विस्मृत ट्यूरिंग मशीनें

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

मशीन मॉडल पंजीकृत करें

Further information: Register machine

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

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

Further information: Counter machine

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

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

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

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

(1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, यानी।

{रजिस्टर #r की सामग्री में वृद्धि; रजिस्टर #r की कमी सामग्री; यदि #r=शून्य की सामग्री है तो निर्देश पर जाएं #z}

(2): {सीएलआर (आर); इंक (आर); जेई (आर_i, आर_j, z ) }, अर्थात्।

{रजिस्टर आर की स्पष्ट सामग्री; आर की सामग्री में वृद्धि; आर की सामग्री की तुलना करें_i आर को_j और यदि समान है तो निर्देश z पर जाएं}

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

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

Further information: Random-access machine

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

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

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

वैन एम्डे बोस विभिन्न रैम मॉडल को कई उप-प्रकारों में विभाजित करता है:* SRAM, केवल एक अंकगणितीय निर्देश के साथ उत्तराधिकारी RAM, उत्तराधिकारी (वृद्धि h)। अन्य में CLEAR h और एक IF समानता-बीच-रजिस्टर शामिल है, फिर xxx पर जाएं।

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

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

Further information: Random-access stored-program machine

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

{ INC ( r ), कॉपी ( r )_i, आर_j ), जेई (आर_i, आर_i, z ) }

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

{ n जोड़ें, जोड़ें < n >, जोड़ें << 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 >, रुकें }

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

Further information: Pointer machine

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

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

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

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

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

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

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

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

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