यहाँ हम देखेंगे कि भाषा L ={WW r . के लिए ट्यूरिंग मशीन कैसे बनाई जाती है |W, {0, 1}} से संबंधित है। तो यह एक प्रकार की भाषा का प्रतिनिधित्व करता है जहाँ हम केवल दो वर्णों 0s और 1s का उपयोग करेंगे। w एक स्ट्रिंग है और w r इसके उलट है। तो अगर w =10110, तो w r 01101 होगा। तो ट्यूरिंग मशीन स्ट्रिंग z =1011001101 को स्वीकार करेगी।
इसे हल करने के लिए, हम इस दृष्टिकोण का उपयोग करेंगे। पहले पहले चिन्ह की जाँच करें, यदि यह 0 है तो इसे y का उपयोग करके बदलें और यदि वह 1 है, तो x का उपयोग करके प्रतिस्थापित करें। फिर स्ट्रिंग के अंत में जाएं। तो अंतिम प्रतीक पहले के समान ही है। हम इसके आधार पर इसे x या y से भी बदल देते हैं। इसके बाद फिर से सिंबल रिप्लेस फ्रॉम स्टार्टिंग के बगल की स्थिति में आ जाएं और वही प्रक्रिया दोहराएं जो ऊपर बताई गई है। हमें यह ध्यान रखना होगा कि चूंकि w r दोनों के w के विपरीत होने पर दोनों के समान संख्या में चिन्ह होंगे। हर बार स्ट्रिंग की शुरुआत से nवें प्रतीक को बदलें, अंत से संबंधित nवें प्रतीक को बदलें।
राज्य संक्रमण आरेख
