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

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