ماشین تورینگ جهانی
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
در علوم رایانه‌ای، ماشین تورینگ جهانی (به انگلیسی: Universal Turing machine) (مخفف انگلیسی: UTM) نوعی ماشین محاسباتی است که می‌تواند براساس یک داده تصادفی یک محاسبه تورینگ تصادفی را شبیه‌سازی نماید. این ماشین محاسباتی اساساً با خواندن توضیح ماشین و نیز داده مربوطه از روی نوار موجود در خود ماشین این کار را انجام می‌دهد. آلن تورینگ این ماشین را بین سال‌های ۱۹۳۷–۱۹۳۶ معرفی کرد. این الگو از نظر بعضی (مانند مارتین دیویس) منشأ ساخت قطعه «ذخیره‌کننده دستورهای برنامه‌های کامپیوتری» می‌باشد که توسط جان فون نویمان در ابزار محاسباتی الکترونیکی بکار می‌رفت و اکنون در علم رایانه «ساختار فون نویمان» نام دارد. این ماشین همچنین ماشین محاسبه جامع، ماشین جامع (UM) و ماشین (U) نامیده می‌شود.
با توجه به پیچیدگی برنامه‌های رایانه‌ای، ماشین محاسبه تورینگ چند نواری در مقایسه با ماشین‌هایی که آن‌ها را شبیه‌سازی می‌کند، فقط دارای عامل لگاریتمی است که عملکرد آن را آهسته‌تر می‌نماید.
مقدمه ویرایش
یک ماشین محاسبه تورینگ یک متغیر محاسباتی خاص را با استفاده از رشته‌ای از داده‌ها از طریق الفبای (صفر و یک) آن محاسبه می‌کند. از این لحاظ، این ماشین مانند یک کامپیوتر با برنامه ثابت عمل می‌نماید؛ ولیکن، می‌توان جدول عملگرهای هر ماشین تورینگی را به صورت رشته‌ای از داده‌ها رمزگذاری نمود؛ بنابراین می‌توان ماشین محاسبه تورینگی ساخت که بر روی نوار ذخیره اطلاعات آن رشته‌ای از داده‌ها برای توصیف جدول عملگرها به همراه رشته‌ای برای توصیف نوار ورودی وجود داشته باشد و نواری را که ماشین تورینگ رمزگذاری کرده‌است، محاسبه نماید. تورینگ در مقاله سال ۱۹۳۶ خود این ساختار را با جزئیات کامل توصیف نمود: "این امکان وجود دارد که ماشینی را اختراع نمود تا بتواند هر تابع قابل محاسبه‌ای را محاسبه نماید. اگر این ماشین (U) دارای نواری باشد که در ابتدای آن توضیحات استاندارد (S.D) از جدول عملگرهای بعضی از ماشینهای محاسبه M نوشته شده باشد بنابراین U یعنی ماشین می‌تواند همان تابع را به عنوان M محاسبه نماید.
کامپیوتر ذخیره دستورهای برنامه‌نویسی ویرایش
"دیویس" استدلال قانع‌کننده‌ای ارائه می‌دهد که تعریف تورینگ از آنچه که اکنون "کامپیوتر ذخیره دستورهای برنامه نویسی"، نامیده می‌شود و نیز قرار دادن "جدول عملگرهاً یعنی دستورهای موجود در ماشین را که در همان حافظه‌ای ذخیره می‌شوند که داده‌ها در آن وجود دارند، تعریف اولیه جان وون نیومن از نماد گسسته (در مقابل نماد متشابه) را تحت تأثیر خود قرار داد، یعنی EDVAC. دیویس در این زمینه در مجله "تایم" بیان می‌کند که "هر فردی که بر روی کیبورد ضربه وارد می‌کند به نوعی در حال تجسم بخشیدن به ماشین محاسبه تورینگ است" و اینکه " نظریه آلن تورینگ اساس نظریه جان وون نیومن بوده‌است." دیویس بیان می‌کند که موتور محاسبه خودکار تورینگ (ACE) مفاهیم کوچکترین دستورهای برنامه‌های کامپیوتری و پردازنده‌های RISC را پیش‌بینی کرده بود. "ناچ" نیز از موتور محاسبه خودکار تورینگ به عنوان طراحی "سخت افزاری برای تسهیل عملگرهای توابع به هم پیوسته" یاد می‌کند، دیویس همچنین از موتور محاسبه خودکار تورینگ به عنوان سخت‌افزار "حافظه کوتاه مدت" نام می‌برد. از آنجا که ماشین محاسبه تیورینگ منشأ ساخت کامپیوترها بوده‌است، بنابراین ماشین محاسبه تورینگ را می‌توان نسل کامپیوترهای اولیه دانست. به گفته دیویس یکی از اولین برنامه‌های کامپیوتری توسط یک برنامه‌نویس برجسته جوان برای EDVAS ارائه شد. اولین برنامه جدی "وون نیومن" فقط داده‌های ساده‌ای بودند که به‌طور مؤثری نوشته شده بودند. "ناچ" بیان می‌کند که اجرای دستورهای تابع به جای ثبت در برنامه‌های خاص منتسب به "وون نیومان" و "گولد استین" در خود برنامه جاسازی شده‌است. "ناچ" همچنین بیان می‌دارد که "اولین برنامه‌های تفسیری شاید در ماشین محاسبه تورینگ آورده شده بودند." "جان ماکلی" در سخنرانی خود که در سال ۱۹۴۶ در دانشگاه "مور" برگزار نمود به برنامه‌های تفسیری اشاره کرد. تورینگ همچنین در توسعه و نوشتن و هدایت برنامه‌های تفسیری برای کامپیوتر آزمایشی ACE شرکت داشت. (ناچ) دیویس به اختصار به سیستم‌های نرم‌افزاری پشتیبان و کامپایلرها به عنوان خروجی و نتیجه مفهوم "برنامه به عنوان داده" اشاره می‌کند؛ ولیکن تاحدی شاید با این ارزیابی مشکلاتی را به وجود میاورد. در آن زمان (اواسط دهه ۱۹۴۰ تا اواسط دهه ۱۹۵۰) گروه نسبتاً کوچکی از محققان به‌طور محرمانه در ساخت "کامپیوترهای دیجیتال" جدید با یکدیگر همکاری داشتند. "هائو وانگ" که در آن زمان محقق جوانی بود مشاهدات خود را بدین گونه بیان نمود: تئوری تورینگ در مورد توابع قابل محاسبه از زمان خود بسیار جلوتر بوده‌است، اما تأثیر چندانی بر ساخت واقعی کامپیوترهای دیجیتال نداشته‌است. این دو جنبه تئوری و عملی بیشتر به‌طور مستقل از یکدیگر گسترش یافته‌اند. دلیل اصلی این امر بدون شک آن است که منطق گرایان اساساً به مسائلی علاقه‌مند هستند که با نظریات مورد علاقه ریاضی دانان و مهندسین برق تفاوت دارند؛ ولیکن جای تعجب نیست که اغلب، مفاهیم مشابه با اصطلاحات و روش‌های متفاوتی بیان می‌شوند. "وانگ" امیدوار بود که مقاله وی موجب پیوند بین این دو روش و دیدگاه شود. درواقع، "مینسکی" تأیید می‌کند که "اولین فرمول نظریه ماشینهای محاسبه تورینگ در مدل‌های مشابه کامپیوتر در نظریه "وانگ" ظاهر شده‌است. مینسکی ماشین محاسبه تورینگ را به نوعی معادل ماشینهای ابتدایی ذخیره اطلاعات می‌داند. با توجه به تبدیل کامپیوترها به مدل‌های ساده معادل تورینگ (و برعکس)، انتخاب "وانگ" از طرف "مینسکی" به عنوان اولین فردی که ماشینهای محاسبه را قاعده مند ساخت، موجب به وجود آمدن مباحثی شد. درحالیکه "شِفِردسون" و "استورگیس" به مقاله "مینسکی" در سال ۱۹۶۱ و مقاله "وانگ" در سال ۱۹۵۷ اشاره کرده بودند، خلاصه‌ای از جزئیات بعضی آثار ریاضی دانان اروپایی از جمله "کافِنست"، "اِرشوو" و "پیتر" را نیز مطرح نمودند. نام ریاضی دانانی مانند "هِرمِس" و "کافِنست" در کتاب‌شناسی "شِفِردسون" و "استورگیس" و "اِلگوت رابینسون" آورده شده‌است. دو نام مهم دیگر نیز در این میان عبارتند از محققان کانادایی "مِلزاک" و "لامبِک".
نظریات وابسته به ریاضیات ویرایش
با رمزگذاری و نامگذاری جداول عملکردها به عنوان رشته‌ای از داده‌ها و دستورهای، این امکان به وجود آمد تا ماشینهای تورینگ برای فرضیاتی در مورد عملکرد سایر ماشینهای تورینگ پاسخی بیابند؛ ولیکن بیشتر این فرضیات قابل اثبات نبودند یعنی عملگر مورد نظر از لحاظ مکانیکی قابل محاسبه نبود؛ مثلاً، این مشکل که آیا عملکرد ماشین تورینگ با ورود داده‌های خاص یا تمامی داده‌ها متوقف خواهد شد، در مقاله اولیه تورینگ غیرقابل اثبات بود و «مشکل توقف برنامه» نام گرفت. (Halting Problem به مشکلی گفته می‌شود که در آن یک برنامه کامپیوتری انتهایی ندارد و به جایی نمی‌رسد). قضیه «رایس» نشان می‌دهد که هر سؤال مهمی در مورد خروجی ماشین تورینگ غیرقابل اثبات است. ماشین محاسبه تورینگ نشان می‌دهد که هر عملگر یا زبان در یک برنامه کامپیوتری خاص که نیازمند اجرای کل آن برنامه باشد قابل محاسبه است و هر زبان عددی را می‌پذیرد. طبق نظریه «چرچ – تورینگ»، مسائلی که به وسیلهٔ ماشین محاسبه تورینگ قابل حل باشند دقیقاً همان مسائلی هستندکه از طریق الگوریتمی یا روش مؤثر محاسباتی قابل حل هستند. به این دلیل ماشین محاسبه تورینگ معیاری است که با آن سیستم‌های محاسباتی و هر سیستمی که می‌تواند ماشین محاسبه تورینگ را شبیه‌سازی کند مقایسه می‌شوند و «تورینگ کامل» نام دارد. نسخه برگرفته از ماشین محاسبه تورینگ تابع عمومی است، یعنی تابع قابل محاسبه‌ای که می‌تواند برای محاسبه سایر توابع قابل محاسبه بکار گرفته شود. ماشین محاسبه تورینگ وجود این تابع عمومی را اثبات می‌کند.
کارایی ویرایش
داده در ماشین تورینگ می‌تواند به شکل الفبایی (صفر و یک) فرض شود، هر الفبای دیگری می‌تواند به شکل صفر و یک رمزگذاری گردد. عملکرد یک ماشین تورینگ (M) از طریق تابع متغیر آن تعریف می‌شود. این تابع نیز می‌تواند به سادگی به رشته‌ای از دستورهای صفر و یک تبدیل گردد. مقدار الفبای M، تعداد نوارهای ذخیره اطلاعات و اندازه فواصل آن‌ها می‌تواند از جدول توابع متغیر استخراج شود. حالات و نمادهای متفاوت از طریق جایگاه آن‌ها تعیین می‌شوند مثلاً دو حالت اول به‌طور قراردادی حالات شروع و پایان را نشان می‌دهند. در نتیجه، هر ماشین محاسبه تورینگ می‌تواند رشته‌ای از دستورهای الفبایی صفر و یک را رمزگذاری نماید. به علاوه، می‌توان نتیجه گرفت که هر گونه رمزگذاری نامعتبری نمایانگر یک محاسبه تورینگ نامعتبر است که متوقف می‌شود و هر ماشین تورینگ می‌تواند با رمزگذاری مداوم و ثابت با عدد قراردادی یک (۱) در انتهای یک دستور، تعداد نامحدودی رمزگذاری انجام دهد دقیقاً مانند توضیحاتی که در یک زبان برنامه‌نویسی می‌آید. تعجب‌آور نیست که با توجه به وجود عدد «گودل» و معادله محاسباتی میان ماشین تیورینگ و عملگرهای بازگشتی µ می‌توان به این رمزگذاری دست یافت. همچنین این توضیح و تفسیر در تمامی دستورهای باینری (صفر و یک) α و ماشین تورینگ Mα مشترک است. با نگاهی به آغاز این نوع رمزگذاری در سال ۱۹۹۶ توسط «هِنی» و «اِستِرن» می‌توان دریافت که اگر ماشین تورینگ را Mα فرض کنیم که داده X را در مراحل N متوقف می‌کند، پس ماشین محاسبه تورینگ چند نوارای به وجود می‌آید که در داده α، x (با فرض نوارهای متفاوت) در CN پردازش مراحل N را شروع می‌کند، C مقدار ثابتی است که به طول دستور x بستگی ندارد، اما به اندازه، تعداد نوارهای ذخیره اطلاعات و تعداد حالات M وابسته است. این عمل در متغیر O نیز شبیه‌سازی می‌شود. (N آغاز پردازش N)
کوچکترین دستگاه‌ها ویرایش
هنگامیکه «آلن تورینگ» به نظریه ساخت دستگاه محاسباتی خود رسید درذهنش فقط مدل محاسباتی ساده و قوای برای محاسبه تمامی عملگرهای ممکن داشت. «کلود شانون» ابتدا به صراحت در سال ۱۹۵۶ مسئله اختراع کوچکترین ماشین محاسباتی تیورینگ را مطرح نمود. وی نشان داد تا زمانی‌که دو حالت مورد استفاده قرار گیرند دو نماد کافی هستند و همیشه این امکان وجود داشت که علائم به جای حالات بکار گرفته شوند. «ماروین مینسکی» با استفاده از سیستم‌های داده‌ای دو حرفی، ماشین محاسبه تورینگی با ۷ حالت و ۴ علامت کشف نمود. از آن زمان سایر ماشینهای محاسباتی تورینگ توسط «یوری روگوژین» و سایرین با استفاده از روش شبیه‌سازی سیستم حروف به وجود آمدند. اگر m را حالات و n را علائم در نظر بگیریم، مجموعه‌های زیر یافت می‌شوند: (۲، ۱۵)، (۳٬۹)، (۴٬۶)، (۵٬۵)، (۶٬۴)، (۳٬۹) و (۲٬۱۸). ماشین (۶٬۴) «روگوژین» فقط ۲۲ دستورالعمل دارد و هیچ معیار UTM کوچکتر در آن وجود ندارد؛ ولیکن، با تعمیم معیار مدل ماشین محاسبه تورینگ حتی ماشینهای محاسباتی کوچکتر نیز قابل پذیرش هستند. چنین تعمیمی تکرار یک کلمه نامحدود را بر یک طرف یا دو طرف ورودی ماشین میسر می‌سازد، و موجب گسترش فراگیری آن و در نتیجه شناخت آن به عنوان «نیمه ضعیف» یا «ضعیف» می‌گردد. در ماشین محاسبه تورینگ کوچک و ضعیفی که قانون ۱۱۰ دستگاه‌های هدایت خودکار تلفن‌های همراه را شبیه‌سازی می‌کند از مجموعه‌های دو تایی (۶٬۲)، (۳٬۳) و (۲٬۴) استفادزه می‌شود. ماشین محاسبه تورینگ ۲ حالته ۳ علامتی «وولفریم» با استفاده از قراردادن حروف ابتدایی، ضعف این فراگیری را بیشتر نشان می‌دهد. سایر متغیرها در الگوی استاندارد ماشین محاسبه تورینگ از UTMهای کوچک استفاده می‌کردند ازجمله ماشین‌هایی با نوارهای متعدد ذخیره اطلاعات یا نوارهای چند بعدی و ماشین‌هایی با دستگاه‌های هدایت خودکار محدود.
نمونه‌ای از جامعیت ماشین رمزگذاری ویرایش
نمونه زیر برگرفته از نظریه تورینگ می‌باشد. برای کسب اطلاعات بیشتر در این زمینه به صفحه مثال‌های ماشین تورینگ مراجعه شود. تورینگ برای رمزگذاری هریک از ۵ حروف از ۷ نماد (A, C, D, R, L, N, ;) استفاده نمود، همان‌طور که در مقاله ماشین محاسبه تورینگ توضیح داده شد، ۷ حروف وی فقط از نوع N1, N2, N3 هستند. تعداد هر ترتیب m (دستورالعمل، حالت) با حرف 'D' نشان داده می‌شود که رشته‌ای از یگان A به دنبال دارد مثلاً Q3=DAAA. وی در روشی مشابه نماد blank (خالی) را با حرف 'D'، نماد "." را با حرف 'DC'، نماد "۱" را با حروف DCC رمزگذاری می‌کند. نماد 'R', 'L', 'N' به همان شکل باقی می‌مانند.
پس از رمزگذاری هر ۵ حروف آن‌ها را در یک زنجیره به شکل جدول زیر نشان می‌دهد:
| Current m-configuration | Tape symbol | Print-operation | Tape-motion | Final m-configuration | Current m-configuration code | Tape symbol code | Print-operation code | Tape-motion code | Final m-configuration code | 5-tuple assembled code | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| q1 | blank | P0 | R | q2 | DA | D | DC | R | DAA | DADDCRDAA | |
| q2 | blank | E | R | q3 | DAA | D | D | R | DAAA | DAADDRDAAA | |
| q3 | blank | P1 | R | q4 | DAAA | D | DCC | R | DAAAA | DAAADDCCRDAAAA | |
| q4 | blank | E | R | q1 | DAAAA | D | D | R | DA | DAAAADDRDA |
در نهایت، رمزها برای ۵ مجموعه در رشته‌ای با یکدیگر جمع شده‌اند که با ';' شروع می‌شود و با ';' از هم جدا می‌شوند مثل:
- DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA
او این رمز را در مربعهای یک در میان قرار داده‌است یعنی "مربعهای F" و خالی گذارن مربعهای E. جمع‌بندی نهایی کدها بر روی نوار ماشین محاسبه شامل قرار دادن دو نماد خاص ('e') یکی پس از دیگری، و سپس رمزی که مربع‌ها را از یکدیگر جدا کرده‌است و بالاخره نماد '::' (فضای خالی که با "." نمایش داده شده برای درک بهتر) ee. ; D.A.D.D.C.R.D.A.A. ;.D.A.A.D.D.A.A.A. ;.D.A.A.A.D.D.C.C.R.D.A.A.A.A. ;.D.A.A.A.A.D.D.R.D.A. ::
جدول عملگرهای ماشین محاسبه (جدول تغییر حالت) مسئول رمزگشایی نمادها است. جدول عملکرد تورینگ با قرار دادن حروف نشانه 'u', 'v', 'x', 'y'، 'z' در "مربعهای E" در سمت راست نماد مشخص شده، کاملاً از جایگاه خود آگاهی می‌یابد؛ مثلاً برای نشان دادن دستور جاری، z در سمت راست علامت ';' قرار می‌گیرد و x ترتیب کنونی m با DAA را حفظ می‌کند. جدول عملگرهای ماشین محاسبه در طی اجرای فرایند محاسبه بین این نمادها حرکت می‌کند (آن‌ها را حذف می‌کند و در محل‌های دیگری قرار می‌دهد) ee. ; D.A.D.D.C.R.D.A.A. ;zD.A.AxD.D.R.D.A.A.A. ;.D.A.A.A.D.D.C.C.R.D.A.A.A.A. ;.D.A.A.A.A.D.D.R.D.A. :: جدول عملگرهای تورینگ در ماشین محاسباتی وی بسیار کاربرد دارد.
تعداد دیگری از مفسران (بخصوص پِنسور در سال ۱۹۸۹) نمونه‌های دیگری از روش‌های رمزگذاری دستورهای را در ماشین محاسباتی تورینگ ارائه دادند. بیشتر مفسران نیز مانند پِنسور فقط از نمادهای باینری (صفر و یک) یا (جای خالی و علامت ا) استفاده می‌کنند. پِنسور فراتر می‌رود و سیستم رمزگذاری مخصوص به خود را می‌نویسد. وی ادعا می‌کند که این علائم سیستم رمزگذاری واقعی و درست هستند، عدد بزرگی که به اندازه ۲ صفحه ۱ و ۰ (صفر و یک) است.
جستارهای وابسته ویرایش
منابع ویرایش
مشارکت‌کنندگان ویکی‌پدیا. «Universal Turing machine». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳ ژوئن ۲۰۱۳.