ماشین های ترنیگ که اولین بار به وسیله آلان ترنیگ توصیف شدند طرح های محاسبه ای ساده حقیقی هستند که به منظور کمک به توسعه ومحدویت های آنچه که می توان محاسبه شود توسعه یافتند . ترنیگ ، که قبلاً اختراع کامپیوترهای دیجیتالی پیشرفته را نوشته بود ، در زمینه این سئوال که آنچه که قابل محاسبه است به چه معناست علاقمند شد . از نظر حسی یک کار قابل محاسبه است اگر افراد بتوانند توالی ساختارهایی را مشخص کنند که هنگامی که دنبال می شود در تکمیل کار وظیفه خواهد داد. چنین مراحل از ساختاری مرحله ...