فلسفه ذهن

2. تعریف ماشین تورینگ
الف. توانایی‌های ماشین تورینگ
نوار و پردازشگری داریم. پردازشگر می‌تواند روی نوار حرکت کند و چیزهایی را بخواند و بنویسد. اما با محدودیت‌های زیر مواجه است:
1. نوار از سمت چپ و راست بی‌نهایت امتداد دارد و روی آن خانه‌هایی وجود دارد.
2. در هر نقطه‌ای از زمان، فقط تعدادی متناهی از خانه وجود دارند که خالی نیستند.
3. خانه‌ای که خالی نیست نمادی از لیستِ S1…Sn دارد (می‌توان تصور کرد که در خانه‌های خالی نماد S0 وجود دارد).
4. پردازشگر همیشه فقط یک خانه را در یک زمان خاص می‌خواند.
5. پردازشگر می‌تواند کارهای زیر را انجام دهد:
a. بگو چه چیزی روی خانۀ اسکن شده وجود دارد.
b. هرچه روی آن خانه است را پاک کن.
c. یکی از نمادهای S1…Sn را بنویس.
d. 1 خانه به سمت چپ یا راست حرکت کن.
e. متوقف شو (halt).
6. هر یک از کارهای پردازشگر زمان یکسانی را می‌گیرد (مثلاً 1 ثانیه).
ب. برنامه‌های ماشین تورینگ
وقتی از «ماشین تورینگ» سخن می‌گوییم، معمولاً برنامهای را در نظر داریم. یک برنامه مجموعه‌ای از دستورالعمل‌ها برای پردازشگر است و به پردازشگر می‌گویند که براساس آنچه روی نوار می‌بیند چه کاری باید انجام دهد.
یک برنامه از مجموعه‌ای متناهی از وضعیت‌های q1…qm تشکیل می‌شود، که همان دستورالعمل‌ها هستند. هر وضعیتی مرکب از دو بخش زیر است که به ماشین می‌گویند که وقتی که در آن وضعیت هستند چه کاری باید انجام دهد:
1. تعیین کارهای مختلف براساس آنچه روی نوار است.
2. تعیین وضعیتی که در مرحلۀ بعدی باید وارد آن شود که این هم به آنچه روی نوار هست وابسته است.
به این ترتیب، وقتی ماشین در یک وضعیت قرار دارد، ابتدا نوار را اسکن می‌کند، سپس براساس آنچه روی نوار می‌بیند، کاری که وضعیت کنونی به آن می‌گوید را انجام می‌دهد، سپس وارد هر وضعیت جدیدی می‌شود که وضعیت قبلی مشخص می‌کند که این هم به آنچه روی نوار دیده است بستگی دارد.
برای اینکه کمی انضمامی‌تر سخن بگوییم، یک وضعیت خاص q1 ممکن است این‌گونه باشد:
وضعیت q1:
اگر نوار خالی است، یک مرحله به سمت چپ برو و وارد وضعیت q1 شو
اگر S1 روی نوار است، یک مرحله به سمت چپ برو و وارد وضعیت q1 شو
اگر S2 روی نوار است، S1 را بنویس و متوقف شو
فرض کنید که ماشینی داریم که فقط S1ها و S2ها را اجازه می‌دهد. این وضعیت به سمت چپ حرکت می‌کند تا یک S2 را ببینید که در این صورت، S2 را پاک می‌کند و یک S1 را می‌نویسد و سپس متوقف می‌شود. به این نکته توجه داشته باشید که اگر هیچS2ای در سمت چپ خانه‌ای که ماشین ابتدائاً اسکن می‌کند وجود نداشته باشد، برای همیشه به سمت چپ حرکت می‌کند؛ یعنی «هنگ» می‌کند.
ج. فلودیاگرام
از طریق یک دیاگرام می‌توان این مطالب را شهودی‌تر کرد.

به این نکته توجه کنید که هیچ پیکانی از وضعیت q2 بیرون نمی‌رود. این نشان‌دهندۀ توقف است: وضعیتی که در آن هیچ کار خاصی مشخص نشده است.
د. نمایش چهارتایی
راه دیگر برای نمایش برنامه‌ها که کمتر شهودی است اما به‌لحاظ نظری (برای برخی از اهداف) سودمندتر است، استفاده از چهارتایی‌هاست. یک چهارتایی به این شکل است:
که بدین معناست: «وقتی در وضعیت qi قرار داری، اگر نماد Sj را اسکن کردی، عمل a را انجام بده، سپس وارد وضعیت qkشو».
برنامه‌ای که قبلاً روی فلودیاگرام مثال زدیم، در قالب چهارتایی به صورت زیر خواهد بود:
هـ. مثال‌های ماشین تورینگ
فرض کنید که نمادها فقط ارقام 1,2,3,… هستند، و فرض کنید که جای خالی با 0 نمایش داده می‌شود. فرض کنید که کل نوار بجز «ورودی» خالی است و ما ماشین را از سمت چپ ورودی شروع می‌کنیم و فرض کنید که ماشین پس از اتمام کارش متوقف می‌شود.
1. روی یک نوار خالی سه تا 1 بنویس، سپس متوقف شو

2. 1ها را دوبرابر کن
این کار کمی پیچیده‌تر است و با معرفی برخی از شیوه‌های برنامه‌نویسی ماشین‌های تورینگ آغاز می‌شود.
دلیل دشواری بیشتر این تمرین این است که قرار است این برنامه تعداد 1ها را ـ هرتعدادی که در ابتدا هستند ـ دوبرابر کند. این بدان معناست که مثل تمرین قبلی، نمی‌توانیم صرفاً تعداد مشخصی 1 را بنویسیم، بلکه قرار است تعداد متغیری از 1ها را بنابه اینکه در ابتدا چه تعدادی از 1ها وجود دارد بنویسیم.
برای این کار باید سلسله کارهایی را در مورد هر 1ای که در ابتدا روی نوار وجود دارد، انجام دهیم. چطور باید به خاطر بسپاریم که چند بار این کار را کرده‌ایم؟ باید از ستون اولیۀ 1ها به‌عنوان شمارنده استفاده کنیم. هر بار یکی از این 1ها را پاک می‌کنیم و هنگامی که همۀ آنها پاک شدند، برنامه می‌داند که زمان توقف است.
پس کاری که انجام می‌دهیم این است: به طور مکرر، سلسله کارهای زیر را انجام می‌دهیم:
الف) یکی از ستون شمارندۀ 1ها را پاک کن
ب) دو 1 جدید را در محل جدید بنویس
ج) اگر ستون شمارنده تمام شد، کار تمام شده است!
د) در غیر این صورت، باید کار را دوباره از (الف) شروع کنیم
کار آنقدر هم ساده نیست، زیرا چند پیچیدگی کلافه‌کننده وجود دارد. فرض کنید کار را به این شکل انجام می‌دهیم:
1الف) 1 سمت چپ را پاک کن
1ب) به سمت چپ حرکت کن تا به ستونی از 1ها برسی
2) دو 1 را در سمت راست این ستون بنویس
3) سپس به محل ستون اولیۀ 1ها برگرد
3الف) اگر آنجا خالی بود، توقف کن
4) اگر نه، به گام 1الف برگرد.
این برنامه در بدو نظر خوب است، اما مشکلاتی وجود دارد. اول: گام 1ب برای اولین بار جواب نمی‌دهد، زیرا ابتدائاً هیچ ستونی از 1 در سمت چپ ستون اولیۀ 1ها وجود ندارد. دوم: اگر همیشه به سمت راست ستون روبه‌رشد یک‌ها بیفزاییم (آن‌طور که گام 2 می‌گوید)، فضای میان دو ستون تمام خواهد شد. سوم: گام 3 در مرتبۀ پایانی جواب نمی‌دهد. از کجا بدانیم که ستون اولیۀ 1ها کجا بود؟ تنها کاری که می‌توانیم انجام دهیم این است که به سمت راست حرکت کنیم تا به 1 برخورد کنیم، اما در مرتبۀ پایانی آخرین 1 را در گام 1الف پاک کرده‌ایم و در این صورت، برنامه هرگز متوقف نمی‌شود، بلکه برای همیشه به سمت راست حرکت می‌کند.
پس به روش بهتری نیاز داریم. 1ها را از سمت راست ستون اولیه حذف می‌کنیم (تا محل اولیۀ 1 در منتهی‌الیه سمت چپ این ستون ثابت بماند) و 1ها را به سمت چپ ستونِ روبه‌رشد می‌افزاییم:
1الف) به سمت راست ستون شمارندۀ 1ها حرکت کن
1ب) آن را پاک کن
1ج) به 1های باقی‌مانده برگرد
1د) یکی به سمت چپ حرکت کن. اکنون در ابتدای ستون روبه‌رشد قرار داریم (اگر اصلاً چیزی در آنجا وجود داشته باشد)

2الف) به سمت چپ 1های ستون روبه‌رشد حرکت کن
2ب) دو 1 به سمت چپ این ستون اضافه کن
2ج) به سمت راست همۀ 1ها برگرد
2د) یک خانه به سمت راست حرکت کن. اکنون در سمت چپ ستون شمارنده قرار داریم.

3) اگر جای خالی را اسکن می‌کنیم، توقف کن

4) اگر 1 را اسکن می‌کنیم، به گام 1الف بازگرد

3. همۀ 1های سمت راست را پاک کن
در اینجا باید دربارۀ نحوۀ بیان کار دقت کنیم. مقصود ما می‌تواند یکی از این دو کار باشد:
الف) برای هر خانه در سمت راست محل اولیه، در نقطه‌ای از زمان آن خانه پاک می‌شود و پس از آن پاک می‌ماند

ناممکن بودن کار دوم را می‌توان با بیان دقیق‌تر کاری که باید انجام شود اثبات کرد:
خواستۀ ما ماشین Mای است که به ازای هر نوار T، وقتی M روی T آغاز می‌کند، نهایتاً متوقف می‌شود و هنگام توقف، T از همۀ 1ها در سمت راست نقطه‌ای که M اسکن خود را از آن آغاز کرده است خالی است.
به عنوان فرض خلف تصور کنید که چنین ماشینی وجود دارد و T را هرگونه نواری در نظر بگیرید. M را روی T در هر خانۀS شروع کنید. طبق فرض، M پس از مدت زمانی متناهی متوقف خواهد شد و پس از آن کل خانه‌های سمت راستِ S خالی خواهند بود. اما اکنون نوار دیگر T’ را در نظر بگیرید که دقیقاً شبیه T است بجز اینکه در خانه‌های سمت راست S، 1هایی دارد که M در طول حرکتش روی نوار T آنها را اسکن نمی‌کند (باید چنین خانه‌هایی وجود داشته باشند، زیرا M پس از مدت زمانی متناهی متوقف شده است). حال M را روی این نوار جدید T حرکت دهید و از خانۀ S شروع کنید. ماشین باید همان کاری را انجام دهد که ابتدائاً انجام داده بود: باید دقیقاً همان خانه‌ها را اسکن کند؛ نه کمتر و نه بیشتر، زیرا تنها چیزی که بر رفتار ماشین تورینگ تأثیر می‌گذارد چیزی است که می‌بیند. بنابراین، M بدون اینکه 1های جدید را پاک کند متوقف خواهد شد. اما قرار بود Mخواستۀ ما را در هر نوار ممکنی برقرار کند؛ در اینجا M نتوانست خانه‌های سمت راست نوار جدید T’ را پاک کند. وهوالمطلوب.
البته هیچ تناقضی در این فرض وجود ندارد که یک ماشین حقه‌ای را برای برخی از نوارها انجام دهد. برای مثال، می‌توانیم ماشینی را طراحی کنیم که 1.000.000 خانه را در سمت راست پاک کند، سپس متوقف شود. این ماشین در مورد هر نواری که هیچ 1ای بیشتر از 1.000.000 خانه ندارد، کار می‌کند. به‌علاوه، می‌توانیم ماشین دیگری طراحی کنیم که 1.000.000 خانه را در سمت راست پاک کند. این ماشین هم در مورد هر نواری که هیچ 1ای بیشتر از 1.000.000 خانه ندارد کار می‌کند، و همین‌طور. کاری که نمی‌توانیم انجام دهیم این است که فقط یک ماشین داشته باشیم که روی هر نواری کار می‌کند.
4. 1 سمت راست را پیدا کن، سپس توقف کن
کاری که می‌توانیم انجام دهیم طراحی ماشینی است که،
اگر 1ای در سمت راست خانۀ اولیه وجود داشته باشد، ماشین نهایتاً آن را پیدا می‌کند و سپس متوقف می‌شود.
اما کاری که نمی‌توانیم انجام دهیم طراحی ماشینی است که،
اگر 1ای در سمت راست خانۀ اولیه وجود داشته باشد، ماشین نهایتاً آن را پیدا می‌کند و سپس با اسکن کردن آن متوقف می‌شود، اما اگر هیچ 1ای در سمت راست ماشین نباشد، ماشین نهایتاً با اسکن کردن 0 متوقف می‌شود.
نکته روشن است: هیچ راهی وجود ندارد که ماشین بداند که چه زمانی باید دست از وارسی کردن بردارد. این موضوع تمایز مهمی را روشن می‌کند. ما می‌توانیم ماشینی داشته باشیم که پاسخی ایجابی را (در صورت وجود) بیابد، بدون اینکه لزوماً ماشینی داشته باشیم که به ما بگوید که آیا اصلاً پاسخی وجود دارد یا نه.
همچنین این موضوع نشان می‌دهد که در تعیین آنچه ماشین‌های ما برآورده می‌کنند چه اندازه باید دقیق باشیم، پیش از آنکه بگوییم ماشین‌ها چه کاری را می‌توانند یا نمی‌توانند انجام دهند. کار اول چیزی است که انجام شدنی است. توجه داشته باشید که هیچ زمانی وجود ندارد که در آن، بتوانیم مطمئن باشیم که ماشین 1 را می‌یابد. همۀ آنچه می‌توانیم انجام دهیم این است که اگر 1ای برای یافتن وجود داشته باشد، ماشین نهایتاً آن را خواهد یافت.