এখানে আমরা দেখব কিভাবে ভাষা L ={WW |W এর অন্তর্গত {0, 1}} এর জন্য একটি টিউরিং মেশিন তৈরি করা যায়। সুতরাং এটি এক ধরনের ভাষাকে উপস্থাপন করে যেখানে আমরা শুধুমাত্র দুটি অক্ষর 0s এবং 1s ব্যবহার করব। w একটি স্ট্রিং. সুতরাং যদি w =10110 হয়, তাহলে টুরিং মেশিন z =1011010110 স্ট্রিং গ্রহণ করবে।
এটি সমাধান করার জন্য, আমরা এই পদ্ধতি ব্যবহার করব। প্রথম জিনিসটি হল স্ট্রিংটির মধ্যবিন্দু খুঁজে বের করা, আমরা একটি 0 কে x এবং 1 থেকে y রূপান্তর করব। ক্রমাগত এটি করার পরে একটি বিন্দুতে পৌঁছে যায় যখন সমস্ত 0 এবং 1 যথাক্রমে x এবং x এ রূপান্তরিত হয়। এখন, আমরা স্ট্রিং এর মধ্যবিন্দুতে আছি। সুতরাং, আমাদের প্রথম উদ্দেশ্য সম্পন্ন হয়েছে।
এখন, মধ্যবিন্দুর বাম দিকের সমস্ত x এবং y-কে 0 এবং 1-এ রূপান্তর করুন। এখন প্রথম অর্ধেক স্ট্রিংটি 0 এবং 1 আকারে রয়েছে৷ স্ট্রিংয়ের দ্বিতীয়ার্ধটি x এবং y আকারে৷
এখন, আবার স্ট্রিং শুরু থেকে শুরু. যদি আপনার কাছে 0 থাকে তবে এটিকে x এ রূপান্তর করুন এবং দ্বিতীয়ার্ধে পৌঁছানো পর্যন্ত ডানদিকে সরান, এখানে যদি আমরা x পাই তবে এটিকে একটি ফাঁকা(B) এ রূপান্তর করুন। তারপরে একটি x বা একটি x খুঁজে না হওয়া পর্যন্ত পিছনে যান। আমরা এর ডানদিকের 0 বা 1 কে যথাক্রমে x বা y তে রূপান্তর করি এবং অনুরূপভাবে, স্ট্রিং এর দ্বিতীয়ার্ধে এর x বা y কে একটি ফাঁকা(B) তে রূপান্তর করি।
স্ট্রিংয়ের বাম অংশের সমস্ত চিহ্নকে x এবং y এবং স্ট্রিংয়ের ডানদিকের সমস্ত চিহ্নকে ফাঁকা জায়গায় রূপান্তর না করা পর্যন্ত এটি করতে থাকুন। যখন একটি অংশ সম্পূর্ণরূপে রূপান্তরিত হয় কিন্তু তারপরও অন্য অর্ধেকের কিছু চিহ্ন অপরিবর্তিত থাকে তখন স্ট্রিংটি গ্রহণ করা হবে না। যদি আমরা প্রথমার্ধে যথাক্রমে 0 বা 1 এর জন্য দ্বিতীয়ার্ধে একটি x বা y খুঁজে না পাই। তারপরও স্ট্রিং গ্রহণ করা হবে না।
রাষ্ট্রীয় রূপান্তর চিত্র
