ماشین محاسبه تورینگ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه‌ای، ماشین محاسبه تورینگ (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»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ ژوئن ۲۰۱۳).