مقدمه
هر ماشين تورينگ يک تابع ثابت جزئي قابل محاسبه معين را از روي رشته ورودي الفبايش محاسبه مي کند. از اين جهت مانند يک کامپيوتر با يک برنامه ثابت رفتار مي کند. بهر حال ما قادريم که جدول عمليات هر ماشين تورينگي را در يک رشته کدگذاري کنيم. بنابراين مي توانيم يک ماشين تورينگ را که درانتظار يک رشته شرح دهنده ي جدول عمليات و بدنبالش يک رشته شرح دهنده نوار ورودي است را ايجاد کنيم , تا نواري که ماشين تورينگ کدشده محاسبه مي نمود را محاسبه نمايد بعبارت ديگر جدول عمليات يک ماشين تورينگ را به صورت يک رشته ورودي به يک ماشين تورينگ ديگر داده ايم تا محاسباتي که ماشين اول مي بايست انجام مي داد را ماشين مقصد انجام دهد. آقاي تورينگ چنين ساختاري را با جزئيات بيشتر در مقاله اي در سال 1936 شرح داد.
در 1937اولين بارماشين تورينگ توسط آلن تورينگ توصيف شد,که ابزارمحاسبه اي ساده اي هستندکه قصددارندکمک کنندبه رسيدگي توسعه ومحدوديت چيزهاي که محا سبه مي شوند.
وي چنين اظهار نمود:
مي توان نشان داد که يک ماشين خاص منفرد از اين نوع را مي توان ساخت که بتواند کار همه ماشينها را انجام دهد.در حقيقت مي توان چنين ماشيني ساخت تا بصورت يک مدل براي هر ماشين ديگري کار کند ,
اين گفته ,شايد , اولين نظريه مقدماتي براي سيستم عامل باشد؛ يک برنامه براي اجراي کنترل شده برنامه هاي ديگر . . . نشان داد که چنين ماشيني وجود دارد – واينرا که مي توان بصورت عملي چنين مدلي داشت را براي اذهان قابل قبول کرد.
با چنين کدکردن جداول عملياتي بصورت رشته هاي ورودي , بعنوان يک اصل براي ماشينهاي تورينگ ممکن شد که به سوالاتي درباره رفتار ماشينهاي تورينگ ديگر پاسخ دهند. بسياري از اين پرسشها , اگرچه تصميم ناپذيرند, بدين معني که تابع مورد سوال بصورت مکانيکي قابل محاسبه نيست. بعنوان مثال , مسئله اينکه :" آيا يک ماشين تورينگ مشخص براي يک ورودي خاص , يا براي همه وروديها توقف خواهد نمود؟" , که با عنوان" مسئله توقف مشهور است , نشان داده شده که بطور کلي در مقاله اصلي تورينگ تصميم ناپذير است . قضيه Rice نشان مي دهد که هر سوال غير بديهي در باره رفتار ياخروجي يک ماشين تورينگ تصميم ناپذير است .
1. مقايسه با ماشينهاي واقعي
اغلب گفته مي شود که ماشينهاي تورينگ برخلاف ديگر آتاماتاهاي ساده تر توان و قدرت ماشينهاي واقعي را داراست , وقادر است که هر عملياتي که يک ماشين واقعي مي تواند اجرا کند را اجرا نمايد.چيزي که در اين جمله به آن توجه نشده آن است که تقريبا هر برنامه خاصي که بر روي يک ماشين خاص در حال اجراست در واقع هيچ چيزي نيست مگر يک خودکارسازي محدود قطعي چراکه ماشيني که آنرا اجرا مي کند فقط مي تواند بصورت محدود در پيکربندي هاي زيادي قرار بگيرد . ماشينهاي تورينگ درواقع معادلند با ماشيني که داراي مقدار فضاي ذخيره سازي نا محدودي است .ممکن است بپرسيم که چرا ماشينهاي تورينگ مدلهاي مفيدي براي کامپيوتر هاي واقعي هستند؟
روشهاي مختلفي براي پاسخ به آن وجود دارد:
1- هر چيزي که يک کامپيوتر واقعي قادر به محاسبه آن است , ماشين تورينگ نيز قادر به آن است , بنابراين هر جمله اي درباره محدوديتهاي ماشين تورينگ بر کامپيوتر هاي واقعي نيز اعمال خواهد شد.
2- تفاوت کاذبي که وجود دارد تنها با اين توانايي ماشين تورينگ که قادر است مقدار نامحدودي از داده را دستکاري کند ايجاد مي شود . اگرچه براساس يک محدوده زماني داده شده , يک ماشين تورينگ ( مانند يک ماشين واقعي ) فقط مي تواند مقدار محدودي از داده را دستکاري کند.
3- مانند يک ماشين تورينگ , يک ماشين واقعي ميتواند درصورت نياز با دريافت ديسکهاي بيشتر يا رسانه هاي ذخيره سازي ديگر فضاي ذخيره سازيش را بزرگ تر کند . اگراز فراهم کردن آن واماند, در ان صورت ممکن است که ماشين تورينگ بعنوان يک مدل غير مفيد بنظر برسد , ولي حقيقت آن است که نه ماشين تورينگ ونه ماشين واقعي هيچ کدام براي انجام محاسبات مفيد به مقادير نجومي فضاي ذخيره سازي نياز ندارند.زمان پردازش مورد نياز معمولا خيلي بيشتر از يک مساله مي باشد .
4- ماشينهاي واقعي خيلي پيچيده تر از يک ماشين تورينگ هستند.بعنوان مثال ماشين تورينگي که يک الگوريتم را شرح مي دهد ممکن است از تعداد کم " چند صد حالت " تشکيل شده باشد , در حالي که خودکارسازي محدود قطعي معادل روي يک ماشين واقعي داراي 1015 حالت مي باشد ! اين موجب مي شود که نمايش DFA براي آناليز غير عملي باشد.
5- ماشينهاي تورينگ الگوريتم ها را شرح مي دهند مستقل از اينکه چقدر حافظه بکار مي برند. براي هر ماشين شناخته شده حد بالاي مقدار حافظه اي که دارد مشخص است ولي اين محدوديت بطور قراردادي مي تواند برطرف شود, ماشين هاي تورينگ به ما اين امکان را مي دهند که جملاتي در باره الگوريتم ها بسازيم که بصورت تئوريک همواره نگه داشته مي شوند, بدون توجه به پيشرفتها در زمينه معماري مرسوم ماشين محاسبه گر.
6- ماشين هاي تورينگ جملات الگوريتم را ساده سازي مي کنند , الگوريتمهاي اجرا شده روي ماشينهاي مجرد معادل تورينگ معمولا خيلي کلي تر از همتايشان روي ماشين واقعي هستند, زيرا آنها داراي انواع داده با دقت قراردادي هستند و هرگز نبايد با شرايط غير منتظره مواجه شوند.
7- از مواردي که در آن ماشينهاي تورينگ مدلهاي ضعيفي براي برنامه ها هستند مي توان به بسياري از برنامه هاي واقعي اشاره کرد , مانند سيستمهاي عامل و پردازشگر کلمات , که اين برنامه ها براي دريافت ورودي نامحدود در طول زمان نوشته شده اند . ماشينهاي تورينگ چنين محاسبات موجودي را بخوبي مدل نمي کند.
8- محدوديت ديگر ماشينهاي تورينگ اين است که آنها توانايي هاي آرگومانهاي خاص را بخوبي مدل نمي کنند . براي مثال کامپيوتر هاي مدرن درواقع نمونه هايي از فرم ماشينهاي محاسبه گرخيلي خاص که بانام ماشينهاي بادسترسي تصادفي(RAM) مشخص مي شوند هستند. ابتدايي ترين تفاوت ميان اين ماشينها و ماشين تورينگ اين است که ماشينهاي تورينگ يک نوار نامحدود استفاده مي کنند در حالي کهRAM ها يک دنباله انديس دارشمارشي را استفاده مي کنند. نتيجه اين تفاوت اين است که براساس انديس هاي حافظه اي مي توان بهينه سازي هاي محاسباتي بکار برد که در يک ماشين تورينگ عام ممکن نيست ؛ بنابراين زمانيکه ماشينهاي تورينگ بعنوان اساس اجراهاي زماني محدود بکار مي روند , يک " اشتباه محدوديت پايين " مي تواند در زمان هاي اجراي الگوريتم هاي معيني بوجود آيد.
يک مثال از آن مرتب سازي شمارشي است که از قرار معلوم در الگوريتم هاي مرتب سازي حد پايين ( Ω(n log n را نقض مي کند . مورد ديگر جستجوي دودويي است که حد پايين خطي ( Ω(nجستجو در ليست مرتب ماشينهاي تورينگ را نقض مي کند.
2.يک تعريف از ماشين تورينگ
يک ماشين توريگ يک نوع ماشين حالت است، در هرزمان ماشين به شماره حالت محدوداست.دستورالعملها براي ماشين تورينگ وضعيت هاي خاصي را شامل ميشود که ماشين بين دوحالت تغييرمي کند.
يک ماشين تورينگ يک نوار تک بعدي نامحدود تقسيم شده در سلول ها دارد.فک معمول ما از نوار به عنوان يک قطعه افقي با سلول هاي مرتب شده در جهت چپ، راست مي باشد. پايان يک نوار به سمت چپ آن گفته مي شود و دوره هاي بسيار نامحدود به سمت راست دارد.
هر سلول اين توانايي را دارد که يک علامت از دو علامت 0و1 را شامل شود.ماشين يک هد R / W(Read / Write) دارد که در هر واحد زماني يک سلول از روي نوار را مي خواند. اين R /W در طول نوار به چپ و راست حرکت مي کند تا سلول هاي متوالي را بخواند.
فعاليت يک ماشين تورينگ کاملاً تعيين مي شود به وسيله :
1. حالت فعلي ماشين
2. علامت روي سلول فعلي که به وسيله نوار خوانده مي شود.
3. ليستي از قوانين مرحله تغيير که به عنوان برنامه براي ماشين به کار مي رود.
هر قانون مرحله تغيير از چهار پارامتر:
<STATE0, symbol, statenext, action>
که بدين معني است: (( اگر ماشين در حالت state0 است و سلول فعلي شامل symbol است پس به سمت statenext حرکت مي کند آنگاه action اتفاق مي افتد. ))
فعاليتهاي ماشين تورينگ هم symbol را روي سلول فعلي نوار مي نويسد وهم هد را يک سلول به چپ يا راست حرکت مي دهد که ما به وسيله علامتهاي 'and' معني مي كنيم.
اگر ماشين به يک موقعيت رسيد که يک قانون تغيير حالت خاص وجود ندارد، آنگاه ماشين متوقف مي شود.دردوره هاي مدرن ،نوار به عنوان حافظه ماشين بکارمي رود.دوچيزمهم وجود دارد :
1- نامحدودي طول نوار ماشين: نوشته هاي وجوددارد که ثابت مي کند که حافظه ماشين نامحدود است.
2- مشابهت در ماهيت: اما در تعريف ماشين روشن نيست، اگريک دسته از دستورالعمل ها در عملکرد يک تورينگ قابل محاسبه وجود داشته باشد آنگاه ماشين محاسبه، عمل کردي بدون توجه به اندازه واحد زمان در وظايف را نتيجه مي دهد.
اين دو گمان قصد دارند تضمين کنند که آن تعريف محاسباتي نتيجه خيلي مطمئن ندارد اين که توابع غير قابل محاسبه شکست مي خورند به ما اطمينان ميدهند که ماشين تورينگ منحصر به فرد است زيرا زمان و حافظه براي کامل کردن محاسبات کافي نيست.
1-2. معني رسمي
بحث از نوار و هدR/ W قصد دارد تا به تعريف کلي کمک کند، اما قانون مهمي درمورد تعريف ماشينهاي تورينگ ارائه نمي دهد در جاهايي که يک تجزيه رسمي از ماشين هاي تورينگ لازم داريم معني مناسب براي اصطلاحات رياضي دستگاه و برنامه مي باشد.
به صورت معمول يک ماشين ممکن است شامل شود :
يك دسته متناهي از حالات Q با مشخص بودن حالت شروع.
يک دسته متناهي از الفباي ∑ .
يک حالت محاسبه از ماشين مي تواند توصيف شود:
ََQstate عضوي ازQ .
stateσ يك تابع ازالفباي ∑.
Hstate يك عدد طبيعي.
عملکرد حالت تغيير براي ماشين δ يک عملکرد از حالات محاسبه به حالات محاسبه است، اگر t=(s)δ .
t σ همه جا با sσ موافق است مگر روي hs.
اگر t (hs)σ ≠(hs) sσ آنگاه hs=ht در غير اين صورت1=< ا hs-ht ا.
مي بينيد که چگونه معني رسمي به يک اصل مربوط مي شود از تابع σ به عنوان نمايش نوار به وسيله انتقا ل شاخص به هر سلول از نوار استفاده مي شود و سپس رمزي کردن علامت در آن سلول به عنوان مقداري از تابع σ شاخص سلول را مي دهد.
هدR/W به وسيله h نمايش داده مي شود و شاخص سلول به وسيله هد خوانده مي شود. تابع تغيير حالت با برگشت يک حالت جديد σ محتويات جديد روي نوار را تعين مي کند. اما اين تابع جديد تحميل شده با تفاوت داشتن از اصل در بیشتر سلول نوار خوانده مي شود، وقتي که هد نبايد حرکت کند اگر سلول تغيير داده شود، در حالت تغيير و هنگامي که هد تحميل شد اگر آن تغيير داده نشود حرکت مي کند يک سلول در دستور ديگر.
اين دگرگوني دسته اي از توابع تورينگ قابل محاسبه را تغيير نمي دهد و تعريف رسمي به وسيله حذف دومين وضعيت روي تابع مرحله تغيير در تعريف ما ساده مي شود اين دو تعريف اجازه مي دهند حروف الفباي روي نوار دسته اي متناهي با شد،زماني که تعريف اصلي روي{0,1}=∑ پا فشاري ميکند اين تغيير روي تعريف دسته اي از توابع تورينگ قابل محاسبه اثر نمي کند .
3.توصيف ماشينهاي تورينگ
هر ماشين تورينگ تعدادي دستگاه دارد چيزي که اين ماشين تورينگ را مجبور ميکند يک وظيفه را انجام دهد و ديگري يک وظيفه ديگر را ليستي از قوانين حالت تغييراست که برنامه ماشينها را تغيير ميدهد و يک حالت اوليه براي ماشين تعيين ميکند .
ما مي توانيم يک ماشين توريگ توصيف کنيم بنابراين با تعيين کردن تنها 4 پارامتر که مشخص مي کند آن يک برنامه است. پارامترهاي توصيفي يک ماشين ساده عبارتند از :
<S0,1,s0,»>
<S0,0,s1,1>
<S1,1,s1,«>
<S1,0,s2, »>
وقتي كه ما به امتحان كردن رفتاري از ماشين تورينگ علاقه منديم آن رايج است و ممکن است بخواهيم آن را با دياگرام حالت نمايش دهيم.
يک ماشين در شکل نمايش داده است.
شکل ( 1): يک دياگرام حالت.
در اين نمودار حالتهايي با حلقه ها نمايش داده شده اندو حالت شروع با دو حلقه . يک حالت تغيير با يک فلش از يک حلقه شروع شده و در حلقه ديگر به پايان ميرسد نمايش داده مي شود فلشها با يک جفت – متشکل از عدد اول که بايد براي فلش خوانده شود تا ادامه داشته باشد و دوم فعاليت آن است که به عنوان حالت تغيير گرفته مي شود – برچسب خورده اند .
چيزي که ما دنبال مي کنيم ،ما شينهاي تورينگ در شکل ماشين حالت توصيف خواهد شد.
1-3.نمونه ها
در دستوري که در مورد بعضي از فوايد ماشين تورينگ صحبت مي شود ما يک شرح از علا متها و ثبت کردن روي نوار تهيه خواهيم کرد. براي مثال اگر ما بخوا هيم يک ماشين طراحي کنيم که بعضي از توابع رياضي و افزايش دسته را نشان دهد ما نياز داريم تو صيف کنيم چگونگي ظاهر شدن يک ها و صفر ها روي نوار به عنوان شماره در مثالها يي که ما n شماره به عنوان يك بلوك ازn+1 علامت'1' روي نوار نمايش مي دهيم شماره صفر را به عنوان نوع '1' و شماره 3 به عنوان يك بلوك از چهار'1' .
ما فرض هاي در مورد ترکيب نوار ايجاد خواهيم کرد وقتي که ماشين شروع شده و در دستوري که محاسبات نمايش داده مي شود پايان مي پذيرد . ما گمان مي کنيم که وقتي ماشين تورينگ شروع شود بخواهيم N بحث مورد نياز تابع را حسا ب کنيم سمت چپ ترين '1' از يک ترتيب N بلو كي '1' با هد خوانده مي شود مبحث نمايش بلوک هاي '1' بايد به وسيله يک علامت0' 'جدا شود. ماشين تورينگ در دنباله ترکيب شروع خواهد شد وقتي که بيضي هاي آن نوار فقط صفرهايي روي سلولها که ما نمي توانيم ببينيم نمايش داده مي شود .به طرف بالا سلولي که خواندن روي آن اتفاق مي افتد نشان داده مي شود.
|
...... |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
....... |
همچنين يک ماشين بايد در يک شکل استاندارد پايان پذيرد . بايد يک نوع بلوک از روي نوار موجود باشد وماشين بايد بخواند دست چپ هر يک را ،اگر ماشين بطور صحيح توابع را حساب کند آنگاه اين بلوک بايد جواب صحيح را نمايش دهد همچنين افزايش ماشين شروع شده در ترکيب بالا بايد تمام شود روي نوار که شبيه اين است.
|
...... |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
........ |
اتخاذ اين قرارداد براي شکل پايان يک ماشين تورينگ اين معني را ميدهد که ما ميتوانيم بسازيم ماشينهاي به وسيله يکي کردن حالت پايان يک ماشين با حالت اوليه بعدي .
زير اين قراردادها، دياگرام حالت در نمودار1 توصيف مي کند يک ماشين را که حساب مي کند تابع جانشين را، وقتي که شروع مي شود در شکل استاندارد روي نوار نمايش داده ميشود شماره Nآن خواهد ايستاد در شکل استاندارد شماره N+1 ،آن اين کار انجام مي دهد بوسيله حالت S0 تا اولين '0' سمت راست بلوك '1' ها. وقتي كه '0' را با '1' به جاي خود بر مي گرداند ،به سمت چپ مي خواند در حالت S1 تا يك '0' پيدا شود سپس به عقب برميگردد تا بخواند اولين '1' را و در حالت S2 متوقف شود.
براي مثال ديگر ، ماشين شکل دو را بررسي مي کنيم که تابع افزايش را حساب مي کند وقتي که شمارههاي NوM شروع مي شود روي يک نوار نمايشي استاندارد،ماشين روي يک نوار نمايشي N+M متوقف ميشود .
شکل 2:يک ماشين براي محاسبه N+M
نتيجه اين ماشين شبيه است به اضافه كردن يک ماشين بين حالتهاي S0 و S2 باعث مي شود ماشين1را در سمت راست اولين بلوک 1 بنويسد و هد را به سمت چپ ترين 1 برمي گرداند.
در شکل استاندارد براي افزايش ، اين دو بلوک 1 را به يک بلوک منفرد شامل (N+1)+1+(M+1) قطعه از علامت 1 متصل مي كند و بنابراين آن روي ورودي و حالت S2 ،نوار شمارهN+M+2 رانمايش مي دهد.
به اين ترتيب ما احتياج داريم تا دو علامت 1 را حذف کنيم که توسط حالات S2 و s3 به دست مي آيد هر 1 به وسيله 0 سر جاي خود قرار مي گيرد وسپس به سمت راست حرکت مي کند.
اولين نوار کمتر از دو1 شامل مي شود و ما يکي بيشتر مي نويسيم،حذف دو 1 يکي کمتر از روي نوار در پايان محاسبه از دست خواهد داد و ما سمت چپ ترين آنها را خواهيم خواند .
2-3.توصيفهاي آني يک محاسبه
حالت کامل يک ماشين تورينگ درهرنکته در طول يک محاسبه ممکن است توسط اسم حالتي که ماشين در آن است توصيف شود، نشانه هاي روي نوار و سلولي که عمل خواندن روي آن انجام مي شود .
يک توصيف از اين سه فرضيه توصیف آني ازيک محاسبه ناميده ميشود .
شکل (3) : توصيف آني يک ماشين تورينگ محاسبه گر
4 . انواع مختلف ماشين تورينگ
ما اينجا يکي از رايج ترين تدوين هاي نظريه اساسي تورينگ را نمايش مي دهيم . تعدادي اختلاف در تدوين عملکرد آن در مدت معين وجود دارد تا مشابه اين باشد و نويسندگان هر يک از اين ماشين هاي تورينگ را نمايش داده اند.
اثبات همه آنها مشابه است .ما مي توانيم هر يک از آنها را به عنوان ماشين تورينگ بررسي کنيم و مناسب ترين را پيدا کنيم .شکل f1 و شكل f2 مشابه اند اگر براي توصيف هر ماشين درشکل f1 وجود داشته باشد يک توصيف درf2 كه تعدادي حالت ورودي و خروجي و برعکس دارد .بنابراين روي چند نوار در چند سلول شروع مي شود و با چند نوار روي چند سلول به پايان مي رسد.
نوارهاي نا محدود دو روشي
در شکل اصلي ما مشخص کرديم که نوار يک پايان دارد در دسته چپ و امتداد دارد بي نهايت به سمت راست ،به راحتي اين شرط اجازه مي دهد که نوار بي نهايت به سمت راست و چپ امتداد پيدا کند .
نتايج در شکل جديد ماشين تورينگ مشابه اصلي است ، از اين استفاده مي شود که براي هر ماشين تورينگ يک نوار دو وضعيتي وجود دارد. يک ما شين تورينگ با يک نوار نامحدود يک وضعيتي و تعدادي حالت ورودي خروجي و برعکس.
نوارهاي دو بعدي
به جاي يک نوار يک بعدي ما مي توانيم يک نوار دو بعدي را بررسي کنيم که به بالا يا پايين و به چپ و راست تا بي نهايت امتداد دارد. ما به شکل آن يک ماشين تغيير حالت اضافه کرديم که مي تواند سبب حرکت هد به بالا و پايين يک سلول شود. در ادامه هد مي تواند به چپ و راست حرکت کند. دوباره اين شکل مشابه اصل مي شود.
شماره هاي اختياري هد هاي خواندن، نوشتن
تعريف ماشين تورينگ تغيير مي کند زماني که ماشين چندين هد خواندن نوشتن دارد، نظريه تورينگ محاسباتي تغيير نمي کند.
حرکت اختياري هد
ويرايش تعريف ماشين تورينگ زماني که هد هاي خواندن و نوشتن ممکن است يک سلول با شماره اختياري را حرکت دهند. در هر مرحله تغيير داده شده نظريه تورينگ محاسباتي را تغييرنمي دهد.
الفباي محدود اختياري
در شکل اصلي، ما اجازه داريم تنها از دو علامت استفاده کنيم. در حقيقت ما قدرت ماشين تورينگ را با استفاده از هر علامت الفباي متناهي افزايش نمي دهيم.
شکل پنج پارامتري
يک روش رايج براي توصيف ماشين تورينگ اين است که اجازه دهيم ماشين دو عمل نوشتن و حرکت کردن هد را در دو مرحله تغيير قرار دهد.اين شکل احتياج دارد تا چهار پارامتر شکل اصلي را با پنج پارامتر جايگزين کند .
<STATEo, symbol, statenew, symbolnew, move>
مجدداً، اين افزايش استقلال نتيجه اي در تعريف تورينگ قابل محاسبه ندارد. براي هر يك از ماشين هاي جديد يک ماشين قديمي با چند ويژگي وجود دارد.
يک ماشين بسيار پيچيده
براي کمک به انجام توابع عددي استفاده مي شوند همچنين نمايش اعداد،ما مي توانيم وظايفي مانند کپي بلوک هاي علامت حذف بلوک هاي علامت و هم چنين روشن کردن.اينجا يک نمونه از ما شين تورينگ است که وقتي در تنظيم هاي استاندارد روي يک نوار شامل يک بلوک منفرد از 1 ها شروع مي شود و روي يک نوار شامل دو کپي از بلوک '1' ها با بلوک هاي جدا شده توسط 0 متوقف مي شود. اين در الفباي شامل علامت هاي 0 و 1و A استفاده مي شود.
شکل (4) : يک ماشين براي کپي يک بلوک از 1ها
کار اين ما شين تغيير مکرر يکي از '1' هاي اصلي درA است و وقتی يک '1' جديد به سمت راست همه '1' هاي باقي مانده روي نوار مي نويسد آن کاه يک صفر بين بلوک اصلي و کپي قرار مي دهد.
حالت اوليه -s0 – استفاده مي شود تا يک '1' داخل A تغيير کند و به سمت راست و حالت s1 حرکت مي کند. در حالت s1 باقی مانده بلوک '1'ها را حذف ميکنيم تا يک '0' پيدا کنيم و در حالت s2 هر '1' را از سمت راست آن '0' حذف مي کنيم ، وقتي که به پايان بلوک مي رسيم يک '0' پيدا مي کنيم که ما به يک '1' مي رسيم و هد به چپ بر مي گردد، به سمت حالت s3. حالتهاي s3وs4 تمام '1'هاي بخش چپ را حذف مي کند و'0'ها را تا زماني که يک A پيدا کند جدا مي کند. زماني که اين اتفاق مي افتد ما به حالت s0 بر مي گرديم و به بخش راست حرکت مي کنيم . در اين شکل ما هر يک از دو کار خواندن '1' بعدي از بلوک اصلي يا ورودي A بلوک اصلي را داريم. و ما '0' جدا کننده را مي خوانيم. در قسمت قبلي حرکت ما از S1 به S4 درست نيست اما در بعد ما حرکت به بخش چپ state6 را انجام داديم در اين حالت ما با تکرار A ها را پيدا کرديم و آنها را با '1' جايگزين کرديم و به چپ حرکت کرديم. اگر ما يک '0' پيدا کنيم آنگاه همه A ها '1' مي شوند. ما '0' ها را به سمت چپ سلول اصلي مي خوانيم و همچنين به سمت راست حرکت مي کنيم و بعد به سمت حالت S0 پايان مي رويم. اين ماشين کپي ميتواند در پيوستن به ماشين افزايشي شکل 2استفاده شود تا يک ماشين دو کاره ايجاد کنيم.بنابراين هنگامي که يک ماشين روي يک نوار نمايشي شماره N شروع مي شود ، روي يک نوار نمايشي شماره 2n مي ايستد. ما مي توانيم اين کار را به وسيله استفاده اول از ماشين کپي انجام دهيم تا نتيجه يک نوار با دو کپي از n بر روي نوار باشد و سپس از ماشين افزايشي استفاده کنيم تا (n+n)=2n را محاسبه کنيم. ما بايد اين کار را به وسيله يکي کردن حالت توقف (62) ماشين کپي و اضافه کردن حالت اوليه ماشين (s0) انجام دهيم.
ماشين تورينگ در يک حالت استاندارد به پايان مي رسد که براي اضافه کردن ماشين نياز است نتيجه را بطور صحيح حساب کند. با طراحي ماشينهاي تورينگي که در تنظيم هاي استاندارد شروع و تمام مي شوند.ما مي توانيم اطمينان داشته باشيم که آنها مي توانند اين نوع را بسازند در مثال ماشين کپي يک پايان منحصر به فرد دارد که اين قطعي نيست.
ما مي توانيم يک ماشين تورينگ بسازيم که نتيجه محاسبات آن را نشان دهيم که روي حالتهاي زيادي به پايان برسد و مي توانيم يک ماشين را با بيش تر از يک ماشين ترکيب کنيم که ارتباط روي ماشين تغيير را دنبال مي کند.
منابع
فرهنگ لغت انگلیسی به فارسی حییم
http://plato.stanford.edu/entries/turing-machin/
نظريه زبانها و ماشينها-مسعود پرهيزگاری
