ماشین پست-تورینگ
ماشین پُست-تورینگ (به انگلیسی: Post-Touring Machine) نام رده‌ای خاص از توصیف برنامه‌های محاسباتی است که بر اساس نسخه‌ای ساده از ماشین تورینگ تعریف می‌شود. این نسخهٔ ماشین تورینگ با الهام از مدل ریاضی و ماشین ارائه شده توسط امیل پُست (به انگلیسی: Emel Post) برای محاسبات ساخته و توصیف می‌شود.
یک ماشین پُست-تورینگ همانند ماشین تورینگ از حافظه‌ای دودویی (به انگلیسی: Binary) و از دو طرف نامتناهی برای انجام محاسبات خود استفاده کرده و از یک الفبای دودویی برای ذخیرهٔ داده در این حافظه بهره می‌برد (هر خانهٔ حافظه می‌تواند علامت خورده یا بدون علامت باشد). زبان برنامه‌نویسی این ماشین از اعمالی ابتدایی مانند انتقال به خانهٔ چپ یا راست از یک خانهٔ حافظه و تغییر مقدار ذخیره شده در یک خانهٔ آن پشتیبانی می‌کند. در شروع عملیات پردازش تعدادی متناهی از خانه‌های حافظه علامت خورده و بقیه بدون علامت هستند. ماشین از یکی از خانه‌های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد: علیرغم شباهت توصیف‌های امیل پُست و آلن تورینگ (به انگلیسی: Alan Touring) از مدل‌های محاسباتی شان، این مدل‌ها مستقل از هم توسعه یافته و هر دو در سال ۱۹۳۶ منتشر شده‌اند. اصطلاحات «ماشین پُست-تورینگ» و «برنامهٔ پُست-تورینگ» توسط مارتین دیویس (به انگلیسی: Martin Davis) استاد دانشگاه نیویورک مورد استفاده قرار گرفته‌اند.
امیل پُست در مقاله‌ای که در سال ۱۹۳۶ به نام "ضابطه‌بندی فرایند ترکیبیاتی متناهی - ۱" منتشر کرد مدلی بسیار ساده از محاسبات ارائه کرد و حدس زد این مدل "منطقا معدل مدل بازگشتی" است. درستی این فرض بعداً اثبات شد.
مدل پُست با مدل ماشین تورینگ در اعمال پایه‌ای و قوانین اعمال شده بر آن‌ها تفاوت‌هایی دارد.
مدل پُست از یک فضای یک بعدی ذخیره‌سازی دودویی (نوار ذخیره‌سازی) از دو طرف نامتناهی استفاده می‌کند و از الفبایی دودویی برای ذخیره‌سازی اطلاعات در هریک از خانه‌های این حافظه بهره می‌برد (هر خانهٔ حافظه می‌تواند علامت خورده یا بی علامت باشد).
در شروع عملیات پردازش، تعداد متناهی از خانه‌های حافظه علامت دار و باقی خانه‌ها بدون علامت هستند.
ماشین از یکی از خانه‌های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می‌دهد:
پُست در مقالهٔ خود اشاره می‌کند که مدل ارائه شده «در مرحلهٔ اولیهٔ توسعه» قرار دارد و گزینه‌هایی برای افزایش انعطاف‌پذیری مدل در مرحلهٔ نهایی‌اش پیشنهاد می‌کند:
امیل پُست در سال ۱۹۴۷ مؤلفه‌های ۵ تایی تعریف ماشین تورینگ را به مؤلفه‌هایی ۴ تایی اتمی کاهش داد:
مولفه‌های ۴ تایی توصیف پُست در واقع همان مؤلفه‌های ۵ تایی توصیف تورینگ هستند. به این صورت که دستورها استاندارد پُست شامل نوشتن (یا بازنویسی) یا حرکت به سمت چپ یا راست اند در حالی که دستورها استاندارد توصیف تورینگ همواره به صورت ترکیبی از نوشتن و حرکت به سمت چپ یا راست هستند.
پاک کردن خانهٔ حافظه در مدل پُست مانند مدل تورینگ، معادل نوشتن علامت تهی (معمولاً '⏘') در آن خانه در نظر گرفته می‌شود.
به این صورت مدل پُست تنها سه نوع ۴ تایی را مورد پذیرش قرار می‌دهد:
formula_1
formula_2
formula_3
formula_4و formula_4حالات ماشین تورینگ و formula_6و formula_7حروف الفبای حافظهٔ ماشین هستند. formula_8بیانگر حرکت به سمت چپ و formula_9بیانگر حرکت به سمت راست روی حافظه است.
از مدل وانگ (ارائه شده به ACM در سال ۱۹۵۴ و انتشار در سال ۱۹۵۷) معمولاً به عنوان مرجع ضابطه‌بندی برنامه‌های ماشین‌های تورینگ با نوار دودویی شناخته می‌شود.
در این مدل بندی دستورها زیر به عنوان دستورها مرجع شناخته می‌شوند: در این مدل فرض شده دستورها ورودی ماشین به صورت متوالی و پشت سر هم اجرا می‌شوند.
همچنین در اینجا "صفر" معادل خانهٔ بدون علامت و "یک" معادل خانهٔ علامت دار در نظر گرفته شده‌است.
وانگ در مورد مدل پیشنهادی‌اش این نکات را یادآور می‌شود: بنا بر این یک ماشین تورینگ با نوار دودویی به سادگی به یک برنامهٔ وانگ قابل تبدیل است.
مارتین دیویس یکی از دانشجویان کارشناسی امیل پُست بود. او به همراه استیون کول کلینی، دکترای خود را زیر نظر آلونزو چرچ به پایان رساند.
او مدل محاسباتی را در دوران تدریس در دانشگاه نیویورک و در سال ۱۹۷۳ و ۱۹۷۴ مورد استفاده قرار داد که آن را ماشین پُست-تورینگ نامیده‌است. دستورها زبان پُست-تورینگ به صورت ترتیبی اجرا می‌شوند و این‌گونه هستند: دقت شود که در این مدل هم دستوری برای توقف روال اجرا وجود ندارد و برنامه زمانی متوقف می‌شود که تمامی دستورها آن اجرا شده باشند.
در سال ۱۹۷۸ دیویس دومین مدل خود را در قالب مقالهٔ "محاسبات چیست" (به انگلیسی: "what is computation") به نام ماشین تورینگ-پُست ارائه کرد.
در این مدل حرف '۱' معادل خانهٔ علامت دار مدل پُست و حرف '۰' معادل خانهٔ بدون علامت است.
در مدل دوم دیویس ۷ نوع دستور وجود دارد: تقسیم دستورها پرش به دو نوع دستور، مجموعهٔ دستورها مدل تورینگ-پُست را بزرگتر کرده ولی استفاده از آن را به دلیل سادگی این دستورها آسان‌تر کرده‌است.
از ویژگی‌های برجستهٔ این مدل می‌توان به این موارد اشاره کرد: دستورها پایه‌ای در این ماشین عبارتند از: در این مدل تفاوتی بین دستورها پرش شرطی و غیر شرطی وجود ندارد.
مدل‌های معرفی شده همگی به لحاظ قدرت محاسباتی، معادل ماشین تورینگ استاندارد هستند.
یک‌نویس (معادل معنایی انگلیسی: Busy Beaver) وظیفه دارد قبل از اتمام روال اجرایی‌اش بیشترین تعداد '۱' ممکن را در حافظه بنویسد. دستور print یا (P) حرف '۱' و دستور Erase یا 'E' حرف '۰' را در موقعیت فعلی بر روی نوار می‌نویسد. دستور Left یا (L) نوار را به سمت چپ و دستور Right یا (R) نوار را به سمت راست حرکت می‌دهد.
جدول حالات ماشین تورینگ یک‌نویس ۲ حالته به این صورت است:
دستورها در نسخهٔ معادل پُست-تورینگ ماشین دوحالتهٔ یک‌نویس (دقت شود که دستورها در یک خط و به ترتیب آمده‌اند. این نسخه یک تغییر عمده نسبت به نمایش ماشین تورینگ و معادل آن چیزی است که به آن «برنامهٔ کامپیوتر» می‌گوییم):
منظور از J1 در جدول بالا پرش در صورتی است که در خانهٔ فعلی '۱' نوشته شده باشد.
به صورت معادل می‌توانیم این جدول را به صورت یک رشته نمایش دهیم. به این صورت که عملوندهای دستورها را بعد از علامت ':' و بعد از نام دستور بنویسیم و دستورها متوالی را با ',' از هم جدا کنیم؛ بنابراین به عنوان مثال رشتهٔ معادل جدول بالا به این صورت است: J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H نمودار حالت یک ماشین تورینگ دو حالتهٔ یک‌نویس با تبدیل هر حالت ماشین تورینگ به ۷ دستور معادل به حالت معادل ماشین پُست-تورینگ تبدیل می‌شود. حالت توقف هم باید به عنوان یک حالت جداگانه در نظر گرفته شود.
در شکل زیر روال اجرای ماشین پُست-تورینگ یک‌نویس با تمام حالات میانی نمایش داده شده‌است:
این مثال روال محاسبهٔ حاصل ضرب دو عدد طبیعی را در یک ماشین تک نوارهٔ پُست-تورینگ با الفبای دو تایی '۱' و '⏘' نشان می‌دهد.
این ماشین پُست-تورینگ عملیات محاسبهٔ ضرب را به صورت بازگشتی توسط دو حلقه انجام می‌دهد.
عملیات از ابتدای سمت چپ نوار و جایی که علائم مربوط به عدد a قرار دارند شروع می‌شود.