در نظریه محاسبات ماشین های همیشه متوقف (به انگلیسی: total Turing machine) که به عنوان های تصمیم گیرنده (decider) یا ماشین تورینگ کامل (به انگلیسی: total Turing machine) نیز شناخته می شوند، ماشینی است که با هر ورودی متوقف می شود. به دلیل توقف مداوم، این ماشین قادر است تصمیم بگیرد که آیا رشته داده شده مربوط به زبان فرمال است یا خیر. آن دسته از زبان هایی که توسط این ماشین ها تصمیم پذیر هستند، مجموعه زبان های بازگشتی می باشند. اگرچه با توجه به مسئله توقف تعیین اینکه ماشین تورینگ اختیاری به ازای جمیع داده ها متوقف شود، خود یک مسئله تصمیم ناپذیر است.
برهان: توابع محاسبه پذیر جزئی تورینگی وجود دارد که به توابع محاسبه پذیر کلی تورینگ بسط داده نمی شوند. بطور خاص، تابع جزئی f تعریف می شود و داریم f(m)=n اگر و تنها اگر ماشین تورینگی که با شاخصn، ضمن ورود داده صفر با خروجی m متوقف می شود، تعمیمی به تابع محاسبه پذیر کلی نداشته باشد.
در عمل، اغلب توابع مربوط به بهره و سود، با ماشین های همیشه متوقف محاسبه می شوند. می توان ماشینی که فقط از حافظه متناهی برای هر ورودی خاص استفاده می کند را با محدود کردن روند کنترل، متوقف کرد و به این ترتیب دیگر هیچ داده ای باعث نمی شود که ماشین در حلقه بینهایت وارد شود. به عنوان یک مثال جزیی می توان ماشینی را نام برد که درخت تصمیم گیری محدودی را اجرا می کند. علی رغم تضمین توقف، نیازی نیست که ماشین حتماً فاقد قابلیت های حلقه باشد. اگر ما حلقه ها را برای رسیدن به اندازه ای متناهی و قابل پیش بینی محدود کنیم (نه برعکس حلقه FOR در بیسیک)، می توانیم توابع بازگشتی اولیه را بیان کنیم. مثالی از چنین ماشین هایی را ماشین های برنامه نویسی زبان اسباب بازی ارائه می دهند.
بعلاوه می توانیم زبان برنامه نویسی تعریف کنیم که نشان دهد حتی توابع پیچیده تر نیز همیشه می توانند متوقف شوند. برای مثال، توابع اکرمن که تابع بازگشتی اولیه نیستند، با این حال به وسیلهٔ سیستم جملات بازنویسی شده و با روند کاهشی آرگومان ها تابعی محاسبه پذیر می باشند.
با وجود مثال های بالا از زبان های برنامه نویسی که پایان برنامه را تضمین می کند، هیچ زبان برنامه نویسی دیگری وجود ندارد که توابع بازگشتی را در بر بگیرد، برای مثال توابعی که با ماشین های تورینگ همیشه متوقف محاسبه می شوند. این بخاطر این واقعیت است که وجود چنین زبان های برنامه نویسی با نیمه تصمیم ناپذیر مسایل در تناقض است اگرچه ماشین های تورینگ با هر ورودی متوقف می شود.
برهان: توابع محاسبه پذیر جزئی تورینگی وجود دارد که به توابع محاسبه پذیر کلی تورینگ بسط داده نمی شوند. بطور خاص، تابع جزئی f تعریف می شود و داریم f(m)=n اگر و تنها اگر ماشین تورینگی که با شاخصn، ضمن ورود داده صفر با خروجی m متوقف می شود، تعمیمی به تابع محاسبه پذیر کلی نداشته باشد.
در عمل، اغلب توابع مربوط به بهره و سود، با ماشین های همیشه متوقف محاسبه می شوند. می توان ماشینی که فقط از حافظه متناهی برای هر ورودی خاص استفاده می کند را با محدود کردن روند کنترل، متوقف کرد و به این ترتیب دیگر هیچ داده ای باعث نمی شود که ماشین در حلقه بینهایت وارد شود. به عنوان یک مثال جزیی می توان ماشینی را نام برد که درخت تصمیم گیری محدودی را اجرا می کند. علی رغم تضمین توقف، نیازی نیست که ماشین حتماً فاقد قابلیت های حلقه باشد. اگر ما حلقه ها را برای رسیدن به اندازه ای متناهی و قابل پیش بینی محدود کنیم (نه برعکس حلقه FOR در بیسیک)، می توانیم توابع بازگشتی اولیه را بیان کنیم. مثالی از چنین ماشین هایی را ماشین های برنامه نویسی زبان اسباب بازی ارائه می دهند.
بعلاوه می توانیم زبان برنامه نویسی تعریف کنیم که نشان دهد حتی توابع پیچیده تر نیز همیشه می توانند متوقف شوند. برای مثال، توابع اکرمن که تابع بازگشتی اولیه نیستند، با این حال به وسیلهٔ سیستم جملات بازنویسی شده و با روند کاهشی آرگومان ها تابعی محاسبه پذیر می باشند.
با وجود مثال های بالا از زبان های برنامه نویسی که پایان برنامه را تضمین می کند، هیچ زبان برنامه نویسی دیگری وجود ندارد که توابع بازگشتی را در بر بگیرد، برای مثال توابعی که با ماشین های تورینگ همیشه متوقف محاسبه می شوند. این بخاطر این واقعیت است که وجود چنین زبان های برنامه نویسی با نیمه تصمیم ناپذیر مسایل در تناقض است اگرچه ماشین های تورینگ با هر ورودی متوقف می شود.
wiki: ماشین تورینگ کامل