ماشین های تورینگ

هر ماشين تورينگ يک تابع ثابت قابل محاسبه معين را از روي رشته ورودي الفبايش محاسبه مي کند. از اين جهت مانند يک کامپيوتر با يک برنامه ثابت رفتار مي کند. بهر حال ما قادريم که جدول عمليات هر ماشين تورينگي را در يک رشته کدگذاري کنيم. بنابراين مي توانيم يک ماشين تورينگ را که درانتظار يک رشته شرح دهنده ي جدول عمليات و بدنبالش يک رشته شرح دهنده نوار ورودي است را ايجاد کنيم , تا نواري که ماشين تورينگ کدشده محاسبه مي کند را محاسبه نمايد بعبارت ديگر جدول عمليات يک ماشين تورينگ را به صورت يک رشته ورودي به يک ماشين تورينگ ديگر داده ايم تا محاسباتي که ماشين اول مي بايست انجام مي داد را ماشين مقصد انجام دهد. آقاي تورينگ چنين ساختاري را با جزئيات بيشتر در مقاله اي در سال 1936 شرح داد.
در 1937اولين بارماشين تورينگ توسط آلن تورينگ توصيف شد.ماشين تورينگ ابزارمحاسبه اي ساده اي است که قصددارند به توسعه ومحدود کردن چيزهاي که محا سبه مي شوند رسيدگي کند.