موضوع مقاله: ماشین پست-تورینگ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین پست-تورینگ | مقدمه: این نسخهٔ ماشین تورینگ با الهام از مدل ریاضی و ماشین ارائه شده توسط امیل پُست (به انگلیسی: Emel Post) برای محاسبات ساخته و توصیف می‌شود. | ## بخش 1: ماشین پست-تورینگ | یک ماشین پُست-تورینگ همانند ماشین تورینگ از حافظه‌ای دودویی (به انگلیسی: Binary) و از دو طرف نامتناهی برای انجام محاسبات خود استفاده کرده و از یک الفبای دودویی برای ذخیرهٔ داده در این حافظه بهره می‌برد (هر خانهٔ حافظه می‌تواند علامت خورده یا بدون علامت باشد). زبان برنامه‌نویسی این ماشین از اعمالی ابتدایی مانند انتقال به خانهٔ چپ یا راست از یک خانهٔ حافظه و تغییر مقدار ذخیره شده در یک خانهٔ آن پشتیبانی می‌کند. در شروع عملیات پردازش تعدادی متناهی از خانه‌های حافظه علامت خورده و بقیه بدون علامت هستند. ماشین از یکی از خانه‌های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد: بررسی علامت دار بودن یا نبودن خانهٔ فعلی علامت دار کردن خانهٔ فعلی پاک کردن علامت خانهٔ فعلی انتقال به خانهٔ بعد از خانهٔ فعلی انتقال به خانهٔ قبل از خانهٔ فعلی علیرغم شباهت توصیف‌های امیل پُست و آلن تورینگ (به انگلیسی: Alan Touring) از مدل‌های محاسباتی شان، این مدل‌ها مستقل از هم توسعه یافته و هر دو در سال ۱۹۳۶ منتشر شده‌اند. اصطلاحات «ماشین پُست-تورینگ» و «برنامهٔ پُست-تورینگ» توسط مارتین دیویس (به انگلیسی: Martin Davis) استاد دانشگاه نیویورک مورد استفاده قرار گرفته‌اند. مدل پُست امیل پُست در مقاله‌ای که در سال ۱۹۳۶ به نام "ضابطه‌بندی فرایند ترکیبیاتی متناهی - ۱" منتشر کرد مدلی بسیار ساده از محاسبات ارائه کرد و حدس زد این مدل "منطقا معدل مدل بازگشتی" است. مدل پُست با مدل ماشین تورینگ در اعمال پایه‌ای و قوانین اعمال شده بر آن‌ها تفاوت‌هایی دارد. مدل پُست از یک فضای یک بعدی ذخیره‌سازی دودویی (نوار ذخیره‌سازی) از دو طرف نامتناهی استفاده می‌کند و از الفبایی دودویی برای ذخیره‌سازی اطلاعات در هریک از خانه‌های این حافظه بهره می‌برد (هر خانهٔ حافظه می‌تواند علامت خورده یا بی علامت باشد). در شروع عملیات پردازش، تعداد متناهی از خانه‌های حافظه علامت دار و باقی خانه‌ها بدون علامت هستند. ماشین از یکی از خانه‌های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد: بررسی علامت دار بودن یا نبودن خانهٔ فعلی علامت دار کردن خانهٔ فعلی پاک کردن علامت خانهٔ فعلی انتقال به خانهٔ بعد از خانهٔ فعلی انتقال به خانهٔ قبل از خانهٔ فعلی پُست در مقالهٔ خود اشاره می‌کند که مدل ارائه شده «در مرحلهٔ اولیهٔ توسعه» قرار دارد و گزینه‌هایی برای افزایش انعطاف‌پذیری مدل در مرحلهٔ نهایی‌اش پیشنهاد می‌کند: جایگزین کردن تعداد نامتناهی خانه‌های حافظه با الفبایی متنهایی و گسترش پذیر (به عنوان مثال استفاده از واژه‌هایی از حروف الفبای مرجع در هر یک از خانه‌های حافظهٔ ماشین محاسباتی به جای استفاده از تنها یک حرف). استفاده از تعداد متناهی اشاره گر به مکان‌های مختلفی از حافظهی ماشین (ماشین در هر لحظه بتواند در بیشتر از یک مکان حافظه به انجام عملیات مشغول باشد). کاهش صوری از تعریف ۵ مؤلفه‌ای ماشین تورینگ به تعریف ۴ مؤلفه‌ای توسط امیل پُست امیل پُست در سال ۱۹۴۷ مؤلفه‌های ۵ تایی تعریف ماشین تورینگ را به مؤلفه‌هایی ۴ تایی اتمی کاهش داد: مولفه‌های ۴ تایی توصیف پُست در واقع همان مؤلفه‌های ۵ تایی توصیف تورینگ هستند. به این صورت که دستورها استاندارد پُست شامل نوشتن (یا بازنویسی) یا حرکت به سمت چپ یا راست اند در حالی که دستورها استاندارد توصیف تورینگ همواره به صورت ترکیبی از نوشتن و حرکت به سمت چپ یا راست هستند. پاک کردن خانهٔ حافظه در مدل پُست مانند مدل تورینگ، معادل نوشتن علامت تهی (معمولاً '⏘') در آن خانه در نظر گرفته می‌شود. به این صورت مدل پُست تنها سه نوع ۴ تایی را مورد پذیرش قرار می‌دهد: و حالات ماشین تورینگ و و حروف الفبای حافظهٔ ماشین هستند. | ## بخش 2: ماشین پست-تورینگ | مدل وانگ از مدل وانگ (ارائه شده به ACM در سال ۱۹۵۴ و انتشار در سال ۱۹۵۷) معمولاً به عنوان مرجع ضابطه‌بندی برنامه‌های ماشین‌های تورینگ با نوار دودویی شناخته می‌شود. در این مدل بندی دستورها زیر به عنوان دستورها مرجع شناخته می‌شوند: «صفر» را در محل فعلی حافظه بنویس «یک» را در محل فعلی حافظه بنویس روی حافظه به سمت چپ حرکت کن روی حافظه به سمت راست حرکت کن اگر در محل فعلی حافظه «صفر» نوشته شده به دستور i ام پرش کن اگر در محل فعلی حافظه «یک» نوشته شده به دستور j ام پرش کن در این مدل فرض شده دستورها ورودی ماشین به صورت متوالی و پشت سر هم اجرا می‌شوند. همچنین در اینجا "صفر" معادل خانهٔ بدون علامت و "یک" معادل خانهٔ علامت دار در نظر گرفته شده‌است. وانگ در مورد مدل پیشنهادی‌اش این نکات را یادآور می‌شود: از آنجایی که در این مدل دستور جداگانه‌ای برای توقف عملیات وجود ندارد، توقف فرایند زمانی انجام می‌شود که دستورها اجرایی به پایان برسند و ماشین نداند باید در ادامه چه کاری انجام دهد. بر خلاف مدل محاسباتی تورینگ که از یک نوار از یک طرف نامتنناهی استفاده می‌کند، مدل وانگ مانند مدل پُست از یک نوار از دو طرف نامتناهی بهره می‌برد. پرش‌های بدون شرط به سادگی از پرش‌های شرطی بالا قابل ساخت هستند بنابراین به سادگی می‌توانیم پرش‌های غیر شرطی را نیز در برنامه‌ها مورد استفاده قرار دهیم. بنا بر این یک ماشین تورینگ با نوار دودویی به سادگی به یک برنامهٔ وانگ قابل تبدیل است. او مدل محاسباتی را در دوران تدریس در دانشگاه نیویورک و در سال ۱۹۷۳ و ۱۹۷۴ مورد استفاده قرار داد که آن را ماشین پُست-تورینگ نامیده‌است. دستورها زبان پُست-تورینگ به صورت ترتیبی اجرا می‌شوند و این‌گونه هستند: در محل فعلی حافظه '۱' بنویس در محل فعلی حافظه 'B' بنویس در صورتی که در محل فعلی حافظه '۱' نوشته شده بود به آدرس A حافظه پرش کن در صورتی که در محل فعلی حافظه 'B' نوشته شده بود به آدرس A حافظه پرش کن به چپ حرکت کن به راست حرکت کن دقت شود که در این مدل هم دستوری برای توقف روال اجرا وجود ندارد و برنامه زمانی متوقف می‌شود که تمامی دستورها آن اجرا شده باشند. در این مدل حرف '۱' معادل خانهٔ علامت دار مدل پُست و حرف '۰' معادل خانهٔ بدون علامت است. در مدل دوم دیویس ۷ نوع دستور وجود دارد: '۱' را در خانهٔ فعلی بنویس '۰' را در خانهٔ فعلی بنویس روی نوار به سمت راست حرکت کن روی نوار به سمت چپ حرکت کن اگر در خانهٔ فعلی '۰' نوشته شده به دستور i ام برو اگر در خانهٔ فعلی '۱' نوشته شده به دستور i ام برو روال اجرا را متوقف کن تقسیم دستورها پرش به دو نوع دستور، مجموعهٔ دستورها مدل تورینگ-پُست را بزرگتر کرده ولی استفاده از آن را به دلیل سادگی این دستورها آسان‌تر کرده‌است. مدل دیویس-سیگال-وایکر از ویژگی‌های برجستهٔ این مدل می‌توان به این موارد اشاره کرد: این مدل اجازهٔ نوشتن چندین نشانه در یک حرکت بر روی نوار را می‌دهد. این مدل اجازهٔ استفاده از نشانهٔ خالی (به انگلیسی: Blank) را در خانه‌های نوار می‌دهد. مدل‌های معرفی شده همگی به لحاظ قدرت محاسباتی، معادل ماشین تورینگ استاندارد هستند. مثال‌هایی از ماشین پُست-تورینگ یک نویس ۲ حالته یک‌نویس (معادل معنایی انگلیسی: Busy Beaver) وظیفه دارد قبل از اتمام روال اجرایی‌اش بیشترین تعداد '۱' ممکن را در حافظه بنویسد. | ## بخش 3: ماشین پست-تورینگ | جدول حالات ماشین تورینگ یک‌نویس ۲ حالته به این صورت است: نشانهٔ روی نوارحالت ۱ حالت ۲ نشانه‌ای که باید نوشته شود جهت حرکت نوار حالت بعدی نشانه‌ای که باید نوشته شود جهت حرکت نوار حالت بعدی 0 ۱ راست. ۲ ۱ چپ ۱ 1 ۱ چپ ۲ ۱ بدون حرکت توقف دستورها در نسخهٔ معادل پُست-تورینگ ماشین دوحالتهٔ یک‌نویس (دقت شود که دستورها در یک خط و به ترتیب آمده‌اند. این نسخه یک تغییر عمده نسبت به نمایش ماشین تورینگ و معادل آن چیزی است که به آن «برنامهٔ کامپیوتر» می‌گوییم): شمارهٔ دستور ۱ ۲ ۳ ۴۵۶۷۸۹۱۰۱۱۱۲۱۳۱۴۱۵دستور J1 P R J P L J J1 P L J P N J Hمقصد پرش ۵ ۸ ۸ ۱۲ ۱ ۱۵ برچسب متناظر با حالت در ماشین تورینگ A B H منظور از J1 در جدول بالا پرش در صورتی است که در خانهٔ فعلی '۱' نوشته شده باشد. به این صورت که عملوندهای دستورها را بعد از علامت ':' و بعد از نام دستور بنویسیم و دستورها متوالی را با ',' از هم جدا کنیم؛ بنابراین به عنوان مثال رشتهٔ معادل جدول بالا به این صورت است:J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, Hنمودار حالت یک ماشین تورینگ دو حالتهٔ یک‌نویس با تبدیل هر حالت ماشین تورینگ به ۷ دستور معادل به حالت معادل ماشین پُست-تورینگ تبدیل می‌شود. در ابتدای کار حافظهٔ ماشین تنها شامل اعداد a = ۳ و b = ۴ است (یک عدد معادل تعداد علامت‌های روی حافظه منهای یک است). این مثال روال محاسبهٔ حاصل ضرب دو عدد طبیعی را در یک ماشین تک نوارهٔ پُست-تورینگ با الفبای دو تایی '۱' و '⏘' نشان می‌دهد. این ماشین پُست-تورینگ عملیات محاسبهٔ ضرب را به صورت بازگشتی توسط دو حلقه انجام می‌دهد. عملیات از ابتدای سمت چپ نوار و جایی که علائم مربوط به عدد a قرار دارند شروع می‌شود. اشاره‌گر نوار حافظه را به انتهای سمت راست حافظه منتقل می‌کنیم، با قرار دادن یک علامت '⏘' و سپس '۱' متغیر c را تشکیل می‌دهیم. بررسی می‌کنیم که آیا به پایان علائم مربوط به a رسیده‌ایم (باید یک علامت '⏘' ببینیم)؟ اشاره‌گر را یک واحد بیشتر به سمت راست منتقل می‌کنیم تا از ابتدای متغیر b رد شویم. b_loop: اگر اشاره‌گر در انتهای متغیر b قرار داشت (در این حالت یک علامت '⏘' زیر اشاره‌گر قرار دارد) در این صورت اشاره‌گر را به انتهای سمت چپ متغیر a منتقل می‌کنیم. در غیر این صورت: یک نشانهٔ '۱' را پاک می‌کنیم تا یک نشانگر شمارش (یک علامت '⏘') در b ایجاد شود. | ## جمع‌بندی | متغیر c را با اضافه کردن یک علامت '۱' به انتهای سمت راست آن یک واحد اضافه می‌کنیم.