حل تمرین نظریه محاسبات/فصل سوم/حل تمرین ۳-۱۱

اگر M را معادل ماشین تورینگ عادی بگیریم و D را یک ماشین تورینگ با نوار از دو طرف نامحدود بگیریم. به منظور نشان دادن معادل بودن D و M ابتدا باید نشان دهیم که هر زبان L می‌تواند به وسیله M تشخیص داده شود همانطور که به وسیله D تشخیص داده شود. که این کار با شبیه سازی اینکه D مانند M رفتار می‌کند و برعکس انجام می‌دهیم.
در قسمت اول شبیه سازی M به وسیله D ساده‌است. طرف چپ نوار را به عنوان انتهای ورودی D علامت می‌زنیم و از حرکت هد آن به سمت چپ جلوگیری می‌کنیم. برای نمایش مورد دیگر، که می‌توانیم D را با M شبیه سازی کنیم نیز می‌توانیم به دو روش عمل کنیم:
a) انتهای ورودی M را با یک علامت مخصوص علامتگذاری می‌کنیم، و با نوار سمت راست این علامت مانند نوار سمت چپ ورودی D رفتار می‌شود. وقتی D به سمت چپ ورودی می‌رود، M به سمت راست علامت حرکت می‌کند. وقتی D در سمت راست ورودی می‌نویسد، محتویات نوار M را یک خانه به سمت راست شیفت می‌دهیم.
b) ماشین M از دو نوار استفاده می‌کند. اولی ورودی و قسمتی از نوار D در سمت راست ورودی را نمایش می‌دهد. و نوار دوم قسمتی از D را که به سمت چپ است نمایش می‌دهد. وقتی D روی سمت چپ ورودی می‌نویسد، M روی نوار دوم می‌نویسد و وقتی D روی قسمت ورودی یا سمت راست ورودی می‌نویسد، M روی نوار اول می‌نویسد. قسمتی از D که در سمت چپ ورودی است به صورت برعکس روی نوار دوم ظاهر می‌شود. در نتیجه ماشین تورینگ دو نواره معادل ماشین تورینگ یک نواره‌است.