تعريف ماشين تورينگ ومقايسه آن با ماشينهای واقعی
مقدمه
هر ماشين تورينگ يک تابع ثابت  قابل محاسبه معين را از روي رشته ورودي الفبايش محاسبه مي کند. از اين جهت مانند يک کامپيوتر با يک برنامه ثابت رفتار مي کند. بهر حال ما قادريم که جدول عمليات  هر ماشين تورينگي را در يک رشته کدگذاري کنيم. بنابراين مي توانيم يک ماشين تورينگ را که درانتظار يک رشته شرح دهنده ي جدول عمليات و بدنبالش يک رشته شرح دهنده نوار ورودي است را ايجاد کنيم , تا  نواري که ماشين تورينگ کدشده محاسبه مي کند را محاسبه نمايد بعبارت ديگر جدول عمليات يک ماشين تورينگ  را به صورت يک  رشته ورودي به يک ماشين تورينگ  ديگر داده ايم تا محاسباتي که ماشين اول مي بايست انجام مي داد را ماشين مقصد انجام دهد. آقاي تورينگ چنين ساختاري را با جزئيات بيشتر در مقاله اي در سال 1936 شرح داد.
در 1937اولين بارماشين تورينگ توسط آلن تورينگ توصيف شد.ماشين تورينگ ابزارمحاسبه اي ساده اي است که قصددارند به  توسعه ومحدود کردن چيزهاي که محا سبه مي شوند رسيدگي کند.
وي چنين اظهار نمود:
مي توان نشان داد که يک ماشين خاص منفرد از اين نوع را مي توان ساخت که بتواند کار همه ماشينها را انجام دهد.در حقيقت مي توان چنين ماشيني ساخت تا به صورت يک مدل براي هر ماشين ديگري کار کند.
اين گفته ,شايد , اولين نظريه مقدماتي  براي سيستم عامل باشد؛ يک برنامه براي اجراي کنترل شده برنامه هاي ديگر. او همچنين نشان داد که چنين ماشيني وجود دارد و اينرا که مي توان بصورت عملي چنين مدلي داشت را براي اذهان قابل قبول کرد.
با کدکردن جداول عملياتي به صورت رشته هاي ورودي , بعنوان يک اصل براي ماشينهاي تورينگ  ممکن شد که به سوالاتي درباره رفتار ماشينهاي تورينگ ديگر پاسخ دهند. بسياري از اين پرسشها تصميم ناپذيرند, بدين معني که تابع مورد سوال به صورت مکانيکي قابل محاسبه نيست. بعنوان مثال , مسئله  اينکه :" آيا  يک ماشين تورينگ مشخص  براي يک ورودي خاص  , يا براي همه وروديها توقف خواهد نمود؟"  _که با عنوان" مسئله توقف مشهور است _ در مقاله اصلي تورينگ نشان داده شده که بطور کلي اين مسئله تصميم ناپذير است . قضيه Rice   نشان مي دهد که هر سوال غير بديهي در باره رفتار يا خروجي يک ماشين تورينگ، تصميم ناپذير است .
1. مقايسه با ماشينهاي واقعي
اغلب گفته مي شود که ماشينهاي تورينگ برخلاف ديگر آتاماتاهاي ساده تر  توان و قدرت ماشينهاي واقعي را داراست , وقادر است که هر عملياتي که يک ماشين واقعي مي تواند اجرا کند را اجرا نمايد.چيزي که در اين جمله به آن توجه نشده آن است که تقريبا هر برنامه خاصي که بر روي يک ماشين خاص در حال اجراست در واقع هيچ چيزي نيست مگر يک  خودکارسازي محدود قطعي چراکه  ماشيني که آنرا اجرا مي کند فقط مي تواند بصورت محدود در پيکربندي هاي زيادي قرار بگيرد . ماشينهاي تورينگ درواقع با ماشيني که داراي مقدار فضاي ذخيره سازي نا محدودي است معادلند .ممکن است بپرسيم که چرا ماشينهاي تورينگ مدلهاي مفيدي براي کامپيوتر هاي واقعي هستند؟
روشهاي مختلفي براي پاسخ به آن وجود دارد:
1-  هر چيزي که يک کامپيوتر واقعي قادر به محاسبه آن است , ماشين تورينگ نيز قادر به آن است , بنابراين هر جمله اي درباره محدوديتهاي ماشين تورينگ  بر کامپيوتر هاي واقعي نيز اعمال خواهد شد.
2-  تفاوت کاذبي که وجود دارد تنها با اين توانايي ماشين تورينگ که قادر است مقدار نامحدودي از داده را دستکاري کند ايجاد مي شود . اگرچه براساس يک محدوده زماني داده شده , يک ماشين تورينگ ( مانند يک ماشين واقعي ) فقط مي تواند مقدار محدودي از داده را دستکاري کند.
3-  مانند يک ماشين تورينگ , يک ماشين واقعي ميتواند درصورت نياز با دريافت ديسکهاي بيشتر يا رسانه هاي ذخيره سازي ديگر فضاي ذخيره سازيش را بزرگ تر کند . اگراز فراهم کردن آن واماند, در ان صورت ممکن است که ماشين تورينگ بعنوان يک مدل غير مفيد بنظر برسد , ولي حقيقت آن است که نه ماشين تورينگ ونه ماشين واقعي هيچ کدام براي انجام محاسبات مفيد به مقادير نجومي فضاي ذخيره سازي نياز ندارند.زمان پردازش مورد نياز معمولا خيلي بيشتر از يک مساله مي باشد .
4-  ماشينهاي واقعي خيلي پيچيده تر از يک ماشين تورينگ هستند.بعنوان مثال ماشين تورينگي که يک الگوريتم را شرح مي دهد ممکن است از تعداد کم " چند صد حالت " تشکيل شده باشد , در حالي که خودکارسازي  محدود قطعي معادل روي يک ماشين واقعي داراي 1015 حالت مي باشد ! اين موجب مي شود که نمايش DFA براي آناليز غير عملي باشد.  
5-  ماشينهاي تورينگ الگوريتم ها را شرح مي دهند مستقل از اينکه چقدر حافظه بکار مي برند. براي هر ماشين شناخته شده حد بالاي مقدار حافظه اي که دارد مشخص است ولي اين محدوديت بطور قراردادي مي تواند برطرف شود, ماشين هاي تورينگ به ما اين امکان را مي دهند که جملاتي در باره الگوريتم ها بسازيم که بصورت تئوريک همواره نگه داشته مي شوند, بدون توجه به پيشرفتها در زمينه معماري مرسوم ماشين محاسبه گر.
6- ماشين هاي تورينگ جملات الگوريتم را ساده سازي مي کنند , الگوريتمهاي اجرا شده روي ماشينهاي مجرد معادل تورينگ معمولا خيلي کلي تر از همتايشان روي ماشين واقعي هستند, زيرا آنها داراي انواع داده با دقت قراردادي هستند و هرگز نبايد با شرايط غير منتظره مواجه شوند.
7- از مواردي که در آن ماشينهاي تورينگ مدلهاي ضعيفي براي برنامه ها هستند مي توان به بسياري از برنامه هاي واقعي اشاره کرد , مانند سيستم هاي عامل و پردازشگر کلمات , که اين برنامه ها براي دريافت ورودي نامحدود در طول زمان نوشته شده اند . ماشين هاي تورينگ چنين محاسبات موجودي را بخوبي مدل نمي کند.
8- محدوديت ديگر ماشينهاي تورينگ اين است که آنها توانايي هاي آرگومانهاي خاص را بخوبي مدل نمي کنند . براي مثال کامپيوتر هاي مدرن درواقع نمونه هايي از فرم ماشينهاي محاسبه گرخيلي خاص که بانام ماشينهاي بادسترسي تصادفي(RAM) مشخص مي شوند هستند.  ابتدايي ترين تفاوت ميان اين ماشينها و ماشين تورينگ اين است که ماشينهاي تورينگ يک نوار نامحدود استفاده مي کنند در حالي کهRAM ها  يک دنباله انديس دارشمارشي را استفاده مي کنند. نتيجه اين تفاوت اين است که براساس انديس هاي حافظه اي مي توان بهينه سازي هاي محاسباتي بکار برد که در يک ماشين تورينگ عام ممکن نيست ؛ بنابراين زمانيکه ماشينهاي تورينگ  بعنوان اساس اجراهاي زماني محدود بکار مي روند , يک " اشتباه محدوديت  پايين "  مي تواند در زمان هاي اجراي الگوريتم هاي معيني بوجود آيد.
2.يک تعريف از ماشين تورينگ
يک ماشين توريگ يک نوع ماشين حالت است، در هر زمان ماشين به شماره حالت محدوداست. دستورالعمل ها براي ماشين تورينگ وضعيت هاي خاصي را شامل مي شوند که ماشين بين دوحالت تغييرمي کند.
يک ماشين تورينگ يک نوار يک بعدي نامحدود تقسيم شده در سلول ها دارد. پايان يک نوار به سمت چپ آن گفته مي شود و دوره هاي بسيار نامحدود به سمت راست دارد.
هر سلول اين توانايي را دارد که يک علامت از دو علامت  0و1 را شامل شود.ماشين يک هد R / W(Read / Write) دارد که در هر واحد زماني يک سلول از روي نوار را مي خواند. اين هد R /W در طول نوار به چپ و راست حرکت مي کند تا سلول هاي متوالي را بخواند.
فعاليت يک ماشين تورينگ به وسيله موارد زير تعيين مي شود:
1. حالت فعلي ماشين
2.علامت روي سلول فعلي که به وسيله نوار خوانده مي شود.
3. ليستي از قوانين مرحله تغيير، که به عنوان برنامه براي ماشين به کار مي رود.
هر قانون مرحله تغيير از چهار پارامتر تشکيل شده:
<state₀, symbol, state_next, action>
که بدين معني است: (( اگر ماشين در حالت state₀ است و سلول فعلي شامل symbol است ، سپس به سمت state_next حرکت کند، آنگاه تغيير حالت اتفاق مي افتد. ))
فعاليتهاي ماشين تورينگ هم symbol را روي سلول فعلي نوار مي نويسد وهم هد را يک سلول به چپ يا راست حرکت مي دهد.
اگر ماشين به يک موقعيت رسيد که يک قانون تغيير حالت خاص وجود نداشت، آنگاه ماشين متوقف مي شود.دردوره هاي مدرن ،نوار به عنوان حافظه ماشين بکار مي رود.

در مورد نوار دوچيزمهم وجود دارد :
1- نامحدودي طول نوار ماشين: نوشته هايي وجود دارد که ثابت مي کند حافظه ماشين نامحدود است.
2-  مشابهت در ماهيت: اما تعريف ماشين روشن نيست، اگريک دسته از دستورالعمل ها در عملکرد يک ماشين تورينگ محاسبه گر وجود داشته باشد آنگاه ماشين محاسبه گر، نتيجه اي بدون توجه به اندازه وظايف در واحد زمان را به دست مي دهد. 
1-2. معني رسمی
بحث نوار و هدR/ W مي تواند به تعريف کلي کمک کند، اما قانون مهمي درمورد تعريف ماشينهاي تورينگ ارائه نمي دهد، در جاهايي که يک تجزيه رسمي از ماشين هاي تورينگ لازم داريم ،براي اصطلاحات رياضي دستگاه و برنامه مناسب مي باشد. 
به طور کلي يک ماشين ممکن است شامل موارد زير باشد :
  ● يک دسته متناهي از حالات Q با مشخص بودن حالت شروع.
  ●يک دسته متناهي از الفباي ∑ .
يک حالت از ماشين مي تواند چنين توصيف شود:
   ََQ_state عضوي ازQ .
   _state σ يک تابع ازالفباي ∑.
   H_state  يک عدد طبيعي.
متغير δ جهت تغيير ماشين، از يک حالت به حالات ديگر است، اگر t=(s)δ .
   _t σ همه جا با _s σ موافق است به جز روي h_s.
   اگر_t (h_s) σ≠(h_s) _s σ آنگاه h_s=h_t در غير اين صورت1=< ا h_s-h_t  ا.
مي بينيد که چگونه معني رسمي به يک اصل مربوط مي شود از تابع σ به عنوان نمايش نوار به وسيله انتقا ل شاخص به هر سلول از نوار استفاده مي شود و سپس علامت رمز گذاري شده در آن سلول به عنوان مقداري از تابع σ شاخص سلول را مي دهد.
هدR/W به وسيله h نمايش داده مي شود و شاخص سلول به وسيله هد خوانده مي شود. تابع تغيير حالت با برگشت يک حالت جديد σ محتويات جديد روي نوار را تعين مي کند. زماني که نياز نباشد هد حرکت کند، اگر سلول تغيير داده شود، در حالت تغيير و هنگامي که هد حرکت کرد اگر سلول تغيير داده نشود هد يک سلول در دستور ديگر حرکت مي کند.
اين دگرگوني تمامي توابع تورينگ قابل محاسبه را تغيير نمي دهد و تعريف رسمي به وسيله حذف دومين وضعيت روي تابع مرحله تغيير  ساده مي شود. اين دو تعريف اجازه مي دهند حروف الفباي روي نوار متناهي با شد،زماني که الفبا شامل {0,1}=∑ است، اين تغيير روي تعريف تمامي توابع ماشين هاي تورينگ محاسبه گر اثر نمي کند .