ماشین پست-تورینگ

ماشین پست-تورینگ (به انگلیسی: Post-Touring Machine) نام رده‌ای خاص از توصیف برنامه‌های محاسباتی است که بر اساس نسخه‌ای ساده از ماشین تورینگ تعریف می‌شود. این نسخه ماشین تورینگ با الهام از مدل ریاضی و ماشین ارائه شده توسط امیل پست (به انگلیسی: Emel Post) برای محاسبات ساخته و توصیف می‌شود.
یک ماشین پست-تورینگ همانند ماشین تورینگ از حافظه‌ای دودویی (به انگلیسی: Binary) و از دو طرف نامتناهی برای انجام محاسبات خود استفاده کرده و از یک الفبای دودویی برای ذخیره داده در این حافظه بهره می‌برد (هر خانه حافظه می‌تواند علامت خورده یا بدون علامت باشد). زبان برنامه‌نویسی این ماشین از اعمالی ابتدایی مانند انتقال به خانه چپ یا راست از یک خانه حافظه و تغییر مقدار ذخیره شده در یک خانه آن پشتیبانی می‌کند.
در شروع عملیات پردازش تعدادی متناهی از خانه‌های حافظه علامت خورده و بقیه بدون علامت هستند. ماشین از یکی از خانه‌های حافظه که به عنوان «خانه آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد:
بررسی علامت دار بودن یا نبودن خانه فعلی
علامت دار کردن خانه فعلی
پاک کردن علامت خانه فعلی
انتقال به خانه بعد از خانه فعلی
انتقال به خانه قبل از خانه فعلی
علیرغم شباهت توصیف‌های امیل پست و آلن تورینگ (به انگلیسی: Alan Touring) از مدل‌های محاسباتی شان، این مدل‌ها مستقل از هم توسعه یافته و هر دو در سال ۱۹۳۶ منتشر شده‌اند. اصطلاحات «ماشین پست-تورینگ» و «برنامه پست-تورینگ» توسط مارتین دیویس (به انگلیسی: Martin Davis) استاد دانشگاه نیویورک مورد استفاده قرار گرفته‌اند.
مدل پست
امیل پست در مقاله‌ای که در سال ۱۹۳۶ به نام "ضابطه‌بندی فرایند ترکیبیاتی متناهی - ۱" منتشر کرد مدلی بسیار ساده از محاسبات ارائه کرد و حدس زد این مدل "منطقا معدل مدل بازگشتی" است. درستی این فرض بعدا اثبات شد.
مدل پست با مدل ماشین تورینگ در اعمال پایه‌ای و قوانین اعمال شده بر آن‌ها تفاوت‌هایی دارد.
مدل پست از یک فضای یک بعدی ذخیره‌سازی دودویی (نوار ذخیره‌سازی) از دو طرف نامتناهی استفاده می‌کند و از الفبایی دودویی برای ذخیره‌سازی اطلاعات در هریک از خانه‌های این حافظه بهره می‌برد (هر خانه حافظه می‌تواند علامت خورده یا بی‌علامت باشد).
در شروع عملیات پردازش، تعداد متناهی از خانه‌های حافظه علامت دار و باقی خانه‌ها بدون علامت هستند.
ماشین از یکی از خانه‌های حافظه که به عنوان «خانه آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد:
بررسی علامت دار بودن یا نبودن خانه فعلی
علامت دار کردن خانه فعلی
پاک کردن علامت خانه فعلی
انتقال به خانه بعد از خانه فعلی
انتقال به خانه قبل از خانه فعلی
پست در مقاله خود اشاره می‌کند که مدل ارائه شده «در مرحله اولیه توسعه» قرار دارد و گزینه‌هایی برای افزایش انعطاف‌پذیری مدل در مرحله نهایی‌اش پیشنهاد می‌کند:
جایگزین کردن تعداد نامتناهی خانه‌های حافظه با الفبایی متنهایی و گسترش پذیر (به عنوان مثال استفاده از واژه‌هایی از حروف الفبای مرجع در هر یک از خانه‌های حافظه ماشین محاسباتی به جای استفاده از تنها یک حرف).
استفاده از تعداد متناهی اشاره گر به مکان‌های مختلفی از حافظه‌ی ماشین (ماشین در هر لحظه بتواند در بیشتر از یک مکان حافظه به انجام عملیات مشغول باشد).
استفاده از تعداد متناهی حافظه دودویی از دو طرف نامتناهی (به جای یک حافظه).
کاهش صوری از تعریف ۵ مولفه‌ای ماشین تورینگ به تعریف ۴ مولفه‌ای توسط امیل پست
امیل پست در سال ۱۹۴۷ مولفه‌های ۵ تایی تعریف ماشین تورینگ را به مولفه‌هایی ۴ تایی اتمی کاهش داد:
مولفه‌های ۴ تایی توصیف پست در واقع همان مولفه‌های ۵ تایی توصیف تورینگ هستند. به این صورت که دستورات استاندارد پست شامل نوشتن (یا بازنویسی) یا حرکت به سمت چپ یا راست اند در حالی که دستورات استاندارد توصیف تورینگ همواره به صورت ترکیبی از نوشتن و حرکت به سمت چپ یا راست هستند.
پاک کردن خانه حافظه در مدل پست مانند مدل تورینگ، معادل نوشتن علامت تهی (معمولا ⏘) در آن خانه در نظر گرفته می‌شود.
به این صورت مدل پست تنها سه نوع ۴ تایی را مورد پذیرش قرار می‌دهد:
و حالات ماشین تورینگ و و حروف الفبای حافظه ماشین هستند. بیانگر حرکت به سمت چپ و بیانگر حرکت به سمت راست روی حافظه است.
مدل وانگ
از مدل وانگ (ارائه شده به ACM در سال ۱۹۵۴ و انتشار در سال ۱۹۵۷) معمولا به عنوان مرجع ضابطه‌بندی برنامه‌های ماشین‌های تورینگ با نوار دودویی شناخته می‌شود.
در این مدل بندی دستورات زیر به عنوان دستورات مرجع شناخته می‌شوند:
«صفر» را در محل فعلی حافظه بنویس
«یک» را در محل فعلی حافظه بنویس
روی حافظه به سمت چپ حرکت کن
روی حافظه به سمت راست حرکت کن
اگر در محل فعلی حافظه «صفر» نوشته شده به دستور i ام پرش کن
اگر در محل فعلی حافظه «یک» نوشته شده به دستور j ام پرش کن
در این مدل فرض شده دستورات ورودی ماشین به صورت متوالی و پشت سر هم اجرا می‌شوند.
همچنین در اینجا " صفر " معادل خانه بدون علامت و " یک " معادل خانه علامت دار در نظر گرفته شده‌است.
وانگ در مورد مدل پیشنهادی‌اش این نکات را یادآور می‌شود:
از آنجایی که در این مدل دستور جداگانه‌ای برای توقف عملیات وجود ندارد، توقف فرایند زمانی انجام می‌شود که دستورات اجرایی به پایان برسند و ماشین نداند باید در ادامه چه کاری انجام دهد.
بر خلاف مدل محاسباتی تورینگ که از یک نوار از یک طرف نامتنناهی استفاده می‌کند، مدل وانگ مانند مدل پست از یک نوار از دو طرف نامتناهی بهره می‌برد.
پرش‌های بدون شرط به سادگی از پرش‌های شرطی بالا قابل ساخت هستند بنابراین به سادگی می‌توانیم پرش‌های غیر شرطی را نیز در برنامه‌ها مورد استفاده قرار دهیم.
بنا بر این یک ماشین تورینگ با نوار دودویی به سادگی به یک برنامه وانگ قابل تبدیل است.
اولین مدل دیویس
مارتین دیویس یکی از دانشجویان کارشناسی امیل پست بود. او به همراه استیون کول کلینی، دکترای خود را زیر نظر آلونزو چرچ به پایان رساند.
او مدل محاسباتی را در دوران تدریس در دانشگاه نیویورک و در سال ۱۹۷۳ و ۱۹۷۴ مورد استفاده قرار داد که آن را ماشین پست-تورینگ نامیده‌است. دستورات زبان پست-تورینگ به صورت ترتیبی اجرا می‌شوند و این‌گونه هستند:
در محل فعلی حافظه ۱ بنویس
در محل فعلی حافظه B بنویس
در صورتی که در محل فعلی حافظه ۱ نوشته شده بود به آدرس A حافظه پرش کن
در صورتی که در محل فعلی حافظه B نوشته شده بود به آدرس A حافظه پرش کن
به چپ حرکت کن
به راست حرکت کن
دقت شود که در این مدل هم دستوری برای توقف روال اجرا وجود ندارد و برنامه زمانی متوقف می‌شود که تمامی دستورات آن اجرا شده باشند.
دومین مدل دیویس
در سال ۱۹۷۸ دیویس دومین مدل خود را در قالب مقاله "محاسبات چیست" (به انگلیسی: "what is computation") به نام ماشین تورینگ-پست ارائه کرد.
در این مدل حرف ۱ معادل خانه علامت دار مدل پست و حرف ۰ معادل خانه بدون علامت است.
در مدل دوم دیویس ۷ نوع دستور وجود دارد:
۱ را در خانه فعلی بنویس
۰ را در خانه فعلی بنویس
روی نوار به سمت راست حرکت کن
روی نوار به سمت چپ حرکت کن
اگر در خانه فعلی ۰ نوشته شده به دستور i ام برو
اگر در خانه فعلی ۱ نوشته شده به دستور i ام برو
روال اجرا را متوقف کن
تقسیم دستورات پرش به دو نوع دستور، مجموعه دستورات مدل تورینگ-پست را بزرگتر کرده ولی استفاده از آن را به دلیل سادگی این دستورات آسان‌تر کرده‌است.
مدل دیویس-سیگال-وایکر
از ویژگی‌های برجسته این مدل می‌توان به این موارد اشاره کرد:
این مدل اجازه نوشتن چندین نشانه در یک حرکت بر روی نوار را می‌دهد.
این مدل اجازه استفاده از نشانه خالی (به انگلیسی: Blank) را در خانه‌های نوار می‌دهد.
نوار ماشین در این مدل از دو طرف نامتناهی‌است.
دستورات پایه‌ای در این ماشین عبارتند از:
PRINT str: عبارت str را در خانه فعلی حافظه می‌نویسد.
IF cond GOTO label: در صورتی که شرط cond برقرار باشد، به اولین دستوری که برچسب label دارد می‌رود.
RIGHT: به اولین خانه سمت راست خانه فعلی برو و آن را بخوان.
LEFT: به اولین خانه سمت چپ خانه فعلی برو و آن را بخوان.
در این مدل تفاوتی بین دستورات پرش شرطی و غیر شرطی وجود ندارد.
مدل‌های معرفی شده همگی به لحاظ قدرت محاسباتی، معادل ماشین تورینگ استاندارد هستند.
مثال‌هایی از ماشین پست-تورینگ
یک نویس ۲ حالته
یک نویس (معادل معنایی انگلیسی: Busy Beaver) وظیفه دارد قبل از اتمام روال اجرایی‌اش بیشترین تعداد ۱ ممکن را در حافظه بنویسد. دستور print یا (P) حرف ۱ و دستور Erase یا E حرف ۰ را در موقعیت فعلی بر روی نوار می‌نویسد. دستور Left یا (L) نوار را به سمت چپ و دستور Right یا (R) نوار را به سمت راست حرکت می‌دهد.
جدول حالات ماشین تورینگ یک نویس ۲ حالته به این صورت است:
نشانه روی نوار
حالت ۱
حالت ۲
نشانه‌ای که باید نوشته شود
جهت حرکت نوار
حالت بعدی
نشانه‌ای که باید نوشته شود
جهت حرکت نوار
حالت بعدی
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
نمودار حالت یک ماشین تورینگ دو حالته یک نویس با تبدیل هر حالت ماشین تورینگ به ۷ دستور معادل به حالت معادل ماشین پست-تورینگ تبدیل می‌شود. حالت توقف هم باید به عنوان یک حالت جداگانه در نظر گرفته شود.
2-state Busy Beaver run on a P–T machine
در شکل زیر روال اجرای ماشین پست-تورینگ یک نویس با تمام حالات میانی نمایش داده شده‌است:
2-state Busy Beaver run on a P–T machine
ضرب با ماشین پست-تورینگ
مثالی از ضرب a × b = c در یک ماشین پست-تورینگ. در ابتدای کار حافظه ماشین تنها شامل اعداد a = ۳ و b = ۴ است (یک عدد معادل تعداد علامت‌های روی حافظه منهای یک است). پس از پایان محاسبات، نتیجه c = ۱۲ سمت راست b روی نوار نوشته شده‌است.
این مثال روال محاسبه حاصل ضرب دو عدد طبیعی را در یک ماشین تک نواره پست-تورینگ با الفبای دو تایی ۱ و ⏘ نشان می‌دهد.
این ماشین پست-تورینگ عملیات محاسبه ضرب را به صورت بازگشتی توسط دو حلقه انجام می‌دهد.
عملیات از ابتدای سمت چپ نوار و جایی که علائم مربوط به عدد a قرار دارند شروع می‌شود.
اشاره‌گر نوار حافظه را به انتهای سمت راست حافظه منتقل می‌کنیم، با قرار دادن یک علامت ⏘ و سپس ۱ متغیر c را تشکیل می‌دهیم.
a_loop : اشاره گر را یک واحد به سمت راست انتقال می‌دهیم. بررسی می‌کنیم که آیا به پایان علائم مربوط به a رسیده‌ایم (باید یک علامت ⏘ ببینیم)؟ اگر رسیده بودیم عملیات به پایان رسیده‌است . در غیر این صورت علامت ۱ زیر اشاره‌گر را پاک می‌کنیم.
اشاره گر را به سمت راست و به ابتدای b منتقل می‌کنیم. اشاره‌گر را یک واحد بیشتر به سمت راست منتقل می‌کنیم تا از ابتدای متغیر b رد شویم.
b_loop : اگر اشاره‌گر در انتهای متغیر b قرار داشت (در این حالت یک علامت ⏘ زیر اشاره‌گر قرار دارد) در این صورت اشاره‌گر را به انتهای سمت چپ متغیر a منتقل می‌کنیم. در غیر این صورت:
یک نشانه ۱ را پاک می‌کنیم تا یک نشانگر شمارش (یک علامت ⏘) در b ایجاد شود.
متغیر c را با اضافه کردن یک علامت ۱ به انتهای سمت راست آن یک واحد اضافه می‌کنیم.
اشاره‌گر را به سمت چپ منتقل می‌کنیم تا به نشانگر شمارش داخل b برسیم.
نشانگر شمارش را با نوشتن علامت ۱ درون آن از بین می‌بریم.
حاصل b - count را با یک واحد به راست بردن اشاره‌گر یک واحد کم می‌کنیم.