ماشین تورینگ و مقایسه آن با ماشین واقعی
Universal Turing machines( UTM )
هر ماشین تورینگ یک تابع ثابت جزئی قابل محاسبه معین[1] را از روی رشته ورودی الفبایش محاسبه می کند. از این جهت مانند یک کامپیوتر با یک برنامه ثابت رفتار می کند. بهر حال ما قادریم که جدول عملیات [2] هر ماشین تورینگی را در یک رشته[3] کدگذاری[4] کنیم. بنابراین می توانیم یک ماشین تورینگ را که درانتظار یک رشته شرح دهنده ی جدول عملیات و بدنبالش یک رشته شرح دهنده نوار ورودی است را ایجاد کنیم , تا نواری که ماشین تورینگ کدشده محاسبه می نمود را محاسبه نماید بعبارت دیگر جدول عملیات یک ماشین تورینگ را به صورت یک رشته ورودی به یک ماشین تورینگ دیگر داده ایم تا محاسباتی که ماشین اول می بایست انجام می داد را ماشین مقصد انجام دهد. آقای تورینگ چنین ساختاری را با جزئیات بیشتر در مقاله ای در سال 1936 شرح داد.
در 1937 , وی چنین اظهار نمود:
"می توان نشان داد که یک ماشین خاص منفرد از این نوع را می توان ساخت که بتواند کار همه ماشینها را انجام دهد.در حقیقت می توان چنین ماشینی ساخت تا بصورت یک مدل برای هر ماشین دیگری کار کند , این ماشین خاص را ماشین جهانی[5] می نامیم . "
این گفته ,شاید , اولین نظریه مقدماتی برای سیستم عامل باشد؛ یک برنامه برای اجرای کنترل شده برنامه های دیگر . . . نشان داد که چنین ماشینی وجود دارد – واینرا که می توان بصورت عملی چنین مدلی داشت را برای اذهان قابل قبول کرد.
با چنین کدکردن جداول عملیاتی بصورت رشته های ورودی , بعنوان یک اصل برای ماشینهای تورینگ ممکن شد که به سوالاتی درباره رفتار ماشینهای تورینگ دیگر پاسخ دهند. بسیاری از این پرسشها , اگرچه تصمیم ناپذیرند[6], بدین معنی که تابع مورد سوال بصورت مکانیکی قابل محاسبه نیست. بعنوان مثال , مسئله اینکه :" آیا یک ماشین تورینگ مشخص برای یک ورودی خاص , یا برای همه ورودیها توقف[7] خواهد نمود؟" , که با عنوان" مسئله توقف[8] " مشهور است , نشان داده شده که بطور کلی در مقاله اصلی تورینگ تصمیم ناپذیر است . قضیه Rice نشان می دهد که هر سوال غیر بدیهی در باره رفتار یا خروجی یک ماشین تورینگ تصمیم ناپذیر است .
یک UTM می تواند نسبتا ساده باشد , فقط شامل تعداد کمی حالات و نیز تعداد معدودی از Symbol ها .بعنوان مثال از وقتی که یک 2X18 UTM (به معنی دو حالت و 18 Symbol ) شناخته شده است فقط دو حالت (State ) مورد نیاز است .
گاهی اوقات کوچکترین UTM های شناخته شده که یک مدل محاسباتی بنام سیستم برچسب[9] را شبیه سازی کرده اند دارای این تعداد از حالات و Symbol ها بوده اند:
2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 24×2 (بعنوان نمونه برای توضیحات مفصل یک ماشین tag-system-based 4x7 ببینید : Minsky , بخش : 14.8.1 صفحه ( 277
Wolfram در کتاب خود " "A New Kind of Scienceیک UTM کوچکتر با 2 حالت و 5 Symbol معرفی کرد که یک اوتوماسیون سلولی[10] را شبیه سازی می کند که آنرا بعنوان ساده ترین UTM شناخته شده در آورد.
یک ماشین تورینگ جهانی Turing-complete می باشد . چنین ماشینی قادر است که هر تایع بازگشتی را محاسبه کند , هر زبان بازگشتی را استنتاج نماید و هر زبان بازگشتی قابل شمارش[11] را بپذیرد. برمبنای قضیه Church-Turing مسائلی که با UTM قابل حل اند کاملا با یک الگوریتم ویا با یک متود محاسباتی موثر[12] قابل حل خواهند بود .
یک نسخه مجرد[13] از ماشین تورینگ جهانی تابع جهانی[14] می باشد ؛ یک تابع قابل محاسبه که می تواند برای محاسبه هر تابع قابل محاسبه دیگری مورد استفاده قرار گیرد . تئوری UTM وجود چنین تابعی را ثابت می کند.
مقایسه با ماشینهای واقعی
اغلب گفته می شود که ماشینهای تورینگ برخلاف دیگر آتاماتاهای ساده تر توان و قدرت ماشینهای واقعی را داراست , وقادر است که هر عملیاتی که یک ماشین واقعی می تواند اجرا کند را اجرا نماید.چیزی که در این جمله به آن توجه نشده آن است که تقریبا هر برنامه خاصی که بر روی یک ماشین خاص در حال اجراست در واقع هیچ چیزی نیست مگر یک خودکارسازی محدود قطعی[15] , چراکه ماشینی که آنرا اجرا می کند فقط می تواند بصورت محدود در پیکربندی[16] های زیادی قرار بگیرد . ماشینهای تورینگ درواقع معادلند با ماشینی که دارای مقدار فضای ذخیره سازی نا محدودی است .ممکن است بپرسیم که چرا ماشینهای تورینگ مدلهای مفیدی برای کامپیوتر های واقعی هستند .
روشهای مختلفی برای پاسخ به آن وجود دارد:
1- هر چیزی که یک کامپیوتر واقعی قادر به محاسبه آن است , ماشین تورینگ نیز قادر به آن است , بنابراین هر جمله ای درباره محدودیتهای ماشین تورینگ بر کامپیوتر های واقعی نیز اعمال خواهد شد.
2- تفاوت کاذبی که وجود دارد تنها با این توانایی ماشین تورینگ که قادر است مقدار نامحدودی از داده را دستکاری کند ایجاد می شود . اگرچه براساس یک محدوده زمانی داده شده , یک ماشین تورینگ ( مانند یک ماشین واقعی ) فقط می تواند مقدار محدودی از داده را دستکاری کند.
3- مانند یک ماشین تورینگ , یک ماشین واقعی میتواند درصورت نیاز با دریافت دیسکهای بیشتر یا رسانه های ذخیره سازی دیگر فضای ذخیره سازیش را بزرگ تر کند . اگراز فراهم کردن آن واماند, در ان صورت ممکن است که ماشین تورینگ بعنوان یک مدل غیر مفید بنظر برسد , ولی حقیقت آن است که نه ماشین تورینگ ونه ماشین واقعی هیچ کدام برای انجام محاسبات مفید به مقادیر نجومی فضای ذخیره سازی نیاز ندارند.زمان پردازش مورد نیاز معمولا خیلی بیشتر از یک مساله می باشد ؛بعنوان نمونه "busy beaver" مثالی است از ماشینهایی که تعداد خیلی زیادی از مراحل را فقط با استفاده از مقادیر ناچیزی ازتعداد بیتها بانجام می رسانند.
4- ماشینهای واقعی خیلی پیچیده تر از یک ماشین تورینگ هستند.بعنوان مثال ماشین تورینگی که یک الگوریتم را شرح می دهد ممکن است از تعداد کم " چند صد حالت " تشکیل شده باشد , در حالی که خودکارسازی محدود قطعی معادل روی یک ماشین واقعی دارای 1015 حالت می باشد ! این موجب می شود که نمایش DFA برای آنالیز غیر عملی باشد.
5- ماشینهای تورینگ الگوریتمها را شرح می دهند مستقل از اینکه چقدر حافظه بکار می برند. برای هر ماشین شناخته شده حد بالای مقدار حافظه ای که دارد مشخص است ولی این محدودیت بطور قراردادی می تواند برطرف شود, ماشین های تورینگ به ما این امکان را می دهند که جملاتی در باره الگوریتم ها بسازیم که بصورت تئوریک همواره نگه داشته می شوند, بدون توجه به پیشرفتها در زمینه معماری مرسوم ماشین محاسبه گر.
6- ماشین های تورینگ جملات الگوریتم را ساده سازی می کنند , الگوریتمهای اجرا شده روی ماشینهای مجرد معادل تورینگ معمولا خیلی کلی تر از همتایشان روی ماشین واقعی هستند, زیرا آنها دارای انواع داده با دقت قراردادی هستند و هرگز نباید با شرایط غیر منتظره مواجه شوند( مثلا running out of memory )
از مواردی که در آن ماشینهای تورینگ مدلهای ضعیفی برای برنامه ها هستند می توان به بسیاری از برنامه های واقعی اشاره کرد , مانند سیستمهای عامل و پردازشگر کلمات , که این برنامه ها برای دریافت ورودی نامحدود در طول زمان نوشته شده اند . ماشینهای تورینگ چنین محاسبات موجودی را بخوبی مدل نمی کند ( ولی هنوزقسمتهایی از آنرا نیز مدل می کند , مانند رویه های مستقل)
محدودیت دیگر ماشینهای تورینگ این است که آنها توانایی های آرگومانهای خاص را بخوبی مدل نمی کنند . برای مثال کامپیوتر های مدرن درواقع نمونه هایی از فرم ماشینهای محاسبه گرخیلی خاص که بانام ماشینهای بادسترسی تصادفی[17]( (RAM مشخص می شوند هستند. ابتدایی ترین تفاوت میان این ماشینها و ماشین تورینگ این است که ماشینهای تورینگ یک نوار نامحدود استفاده می کنند در حالی کهRAM ها یک دنباله اندیس دارشمارشی[18] را استفاده می کنند(بطور نمونه یک فیلد Integer). نتیجه این تفاوت این است که براساس اندیس های حافظه ای می توان بهینه سازی های محاسباتی بکار برد که در یک ماشین تورینگ عام ممکن نیست ؛ بنابراین زمانیکه ماشینهای تورینگ بعنوان اساس اجراهای زمانی محدود بکار می روند , یک " اشتباه محدودیت پایین[19] " می تواند در زمان های اجرای الگوریتم های معینی بوجود آید ( مربوط به فرض " "false simplifyingدر ماشین تورینگ).
یک مثال از آن مرتب سازی شمارشی [20] است که از قرار معلوم در الگوریتم های مرتب سازی حد پایین Ω(n log n)را نقض می کند . مورد دیگر جستجوی دودویی است که حد پایین خطی Ω(n) جستجو در لیست مرتب ماشینهای تورینگ را نقض می کند.
[1] certain fixed partial computable function
[2] action table
[3] string
[4] encode
[5] universal machine
[6] undecidable
[7] halt
[8] Halting problem
[9] tag system
[10] cellular automaton
[11] recursively enumerable language
[12] effective method of computation
[13] abstract version
[14] universal function
[15] deterministic finite automaton
[16] configurations
[17] random access machine
[18] numerically indexed sequence
[19] false lower bound
[20] counting sort
References
- Rolf Herken. The Universal Turing Machine – A Half-Century Survey. Springer Verlag. ISBN 3-211-82637-8.
- Paul Strathern. Turing and the Computer – The Big Idea. Anchor Books/Doubleday. ISBN 0-385-49243-X.
- Wolfram, Stephen, A New Kind of Science, Wolfram Media, ISBN 1-57955-008-8 John Hopcroft and Jeffrey Ullman,
- Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading Mass, 1979. See Chapter 7 "Turing Machines." An incredibly difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
