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

ماشین پُست - تورینگ ( به انگلیسی: Post - Touring Machine ) نام رده ای خاص از توصیف برنامه های محاسباتی است که بر اساس نسخه ای ساده از ماشین تورینگ تعریف می شود. این نسخهٔ ماشین تورینگ با الهام از مدل ریاضی و ماشین ارائه شده توسط امیل پُست ( به انگلیسی: Emel Post ) برای محاسبات ساخته و توصیف می شود.
یک ماشین پُست - تورینگ همانند ماشین تورینگ از حافظه ای دودویی ( به انگلیسی: Binary ) و از دو طرف نامتناهی برای انجام محاسبات خود استفاده کرده و از یک الفبای دودویی برای ذخیرهٔ داده در این حافظه بهره می برد ( هر خانهٔ حافظه می تواند علامت خورده یا بدون علامت باشد ) . زبان برنامه نویسی این ماشین از اعمالی ابتدایی مانند انتقال به خانهٔ چپ یا راست از یک خانهٔ حافظه و تغییر مقدار ذخیره شده در یک خانهٔ آن پشتیبانی می کند. در شروع عملیات پردازش تعدادی متناهی از خانه های حافظه علامت خورده و بقیه بدون علامت هستند. ماشین از یکی از خانه های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می دهد:
• بررسی علامت دار بودن یا نبودن خانهٔ فعلی
• علامت دار کردن خانهٔ فعلی
• پاک کردن علامت خانهٔ فعلی
• انتقال به خانهٔ بعد از خانهٔ فعلی
• انتقال به خانهٔ قبل از خانهٔ فعلی
علیرغم شباهت توصیف های امیل پُست و آلن تورینگ ( به انگلیسی: Alan Touring ) از مدل های محاسباتی شان، این مدل ها مستقل از هم توسعه یافته و هر دو در سال ۱۹۳۶ منتشر شده اند. اصطلاحات «ماشین پُست - تورینگ» و «برنامهٔ پُست - تورینگ» توسط مارتین دیویس ( به انگلیسی: Martin Davis ) استاد دانشگاه نیویورک مورد استفاده قرار گرفته اند.
امیل پُست در مقاله ای که در سال ۱۹۳۶ به نام "ضابطه بندی فرایند ترکیبیاتی متناهی - ۱" منتشر کرد مدلی بسیار ساده از محاسبات ارائه کرد و حدس زد این مدل "منطقا معدل مدل بازگشتی" است. درستی این فرض بعداً اثبات شد.
مدل پُست با مدل ماشین تورینگ در اعمال پایه ای و قوانین اعمال شده بر آن ها تفاوت هایی دارد.
مدل پُست از یک فضای یک بعدی ذخیره سازی دودویی ( نوار ذخیره سازی ) از دو طرف نامتناهی استفاده می کند و از الفبایی دودویی برای ذخیره سازی اطلاعات در هریک از خانه های این حافظه بهره می برد ( هر خانهٔ حافظه می تواند علامت خورده یا بی علامت باشد ) .