تعریف ماشین تورینگ ومقایسه آن با ماشینهای واقعی
مقدمه
هر ماشین تورینگ یک تابع ثابت  قابل محاسبه معین را از روی رشته ورودی الفبایش محاسبه می کند. از این جهت مانند یک کامپیوتر با یک برنامه ثابت رفتار می کند. بهر حال ما قادریم که جدول عملیات  هر ماشین تورینگی را در یک رشته کدگذاری کنیم. بنابراین می توانیم یک ماشین تورینگ را که درانتظار یک رشته شرح دهنده ی جدول عملیات و بدنبالش یک رشته شرح دهنده نوار ورودی است را ایجاد کنیم , تا  نواری که ماشین تورینگ کدشده محاسبه می کند را محاسبه نماید بعبارت دیگر جدول عملیات یک ماشین تورینگ  را به صورت یک  رشته ورودی به یک ماشین تورینگ  دیگر داده ایم تا محاسباتی که ماشین اول می بایست انجام می داد را ماشین مقصد انجام دهد. آقای تورینگ چنین ساختاری را با جزئیات بیشتر در مقاله ای در سال 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}=∑ است، این تغییر روی تعریف تمامی توابع ماشین های تورینگ محاسبه گر اثر نمی کند .