آشنایی با انواع ماشین‌های محاسبه تورینگ و کاربرد آن‌ها

ماشین تورینگ چیست؟

ماشین تورینگ (Turing machine) یک دستگاه فرضی است که روی نشان‌های روی یک قطعه نوار بر اساس جدول قوانین دست‌کاری انجام می‌دهد. با وجود اینکه مکانیزم ماشین تورینگ مقدماتی است، مفهومش برای پوشش عملکردهای بسیار پیچیده کافی و گسترده‌است. ماشین تورینگ می‌تواند برای شبیه‌سازی هر الگوریتم کامپیوتری و توضیح نحوه عملکرد یک واحد پردازشگر مرکزی به کار آید. حافظه این ماشین ساختاری بسیار ساده دارد. یعنی می‌تواند به صورت یک آرایه یک بعدی از عناصر (سلولها) باشد که هر یک می‌توانند حافظ تنها یک نماد باشند. این آرایه از هر دو طرف باز و نامحدود است (حافظه بینهایت) و اطلاعات آن می‌توانند به هر ترتیبی فراخوانی شوند. یک ماشین محاسبه تورینگ یک متغیر محاسباتی خاص را با استفاده از رشته‌ای از داده‌ها از طریق الفبای (صفر و یک) آن محاسبه می‌کند. از این لحاظ، این ماشین مانند یک کامپیوتر با برنامه ثابت عمل می‌نماید؛ اما، می‌توان جدول عملگرهای هر ماشین تورینگی را به صورت رشته‌ای از داده‌ها رمزگذاری نمود؛ بنابراین می‌توان ماشین محاسبه تورینگی ساخت که بر روی نوار ذخیره اطلاعات آن رشته‌ای از داده‌ها برای توصیف جدول عملگرها به همراه رشته‌ای برای توصیف نوار ورودی وجود داشته باشد و نواری را که ماشین تورینگ رمزگذاری کرده‌است، محاسبه نماید. تورینگ در مقاله سال ۱۹۳۶ خود این ساختار را با جزئیات کامل توصیف نمود: "این امکان وجود دارد که ماشینی را اختراع نمود تا بتواند هر تابع قابل محاسبه‌ای را محاسبه نماید. اگر این ماشین (U) دارای نواری باشد که در ابتدای آن توضیحات استاندارد (S.D) از جدول عملگرهای بعضی از ماشینهای محاسبه M نوشته شده باشد بنابراین U یعنی ماشین می‌تواند همان تابع را به عنوان M محاسبه نماید.

ماشین تورینگ متناوب

در نظریه پیچیدگی محاسباتی، یک ماشین تورینگ متناوب (Alternating Turing machine)، ماشین تورینگی غیر قطعی است و شامل قانونی برای پذیرش محاسباتی است که قوانین استفاده شده در تعریف کلاس‌های پیچیدگی NP و co-NP را کلیت می‌بخشد. مفهوم ATM توسط Chandra و Stockmeyer و مستقلاً توسط Kozen در سال ۱۹۷۶، و سپس به صورت مشترک، باانتشار در یک مجله در سال ۱۹۸۱ مطرح شد.

ماشین تورینگ کوانتومی

یک ماشین تورینگ کوانتومی (quantum Turing machine) که به آن ماشین تورینگ جهانی نیز می‌گویند یک ماشین انتزاعی است که برای مدل کردن تأثیرات یک کامپیوتر کوانتومی استفاده می‌شود. این ماشین یک مدل بسیار ساده را ارائه می‌کند که قدرت محاسبات کوانتومی را نشان می‌دهد. هر الگوریتم کوانتومی می‌تواند به صورت رسمی توسط یک ماشین تورینگ کوانتومی بیان شود. این نوع ماشین تورینگ نخستین بار توسط دانشمند فیزیکدان دانشگاه اکسفورد David Deutsch در سال ۱۹۸۵ ارائه شد. وی پیشنهاد کرد که گیت‌های کوانتومی می‌توانند همانند گیت‌های منطقی دودویی کلاسیک عمل کنند. معمولاً ماشین‌های تورینگ کوانتومی برای آنالیز کردن محاسبات کوانتومی مورد استفاده قرار نمی‌گیرند و معمولاً از مدل مدارات کوانتومی که مدل‌های رایج تری هستند استفاده می‌شود و این مدل‌ها با یکدیگر معادل هستند. ماشین‌های تورینگ کوانتومی می‌توانند توسط ماتریس‌های انتقال با ماشین تورینگ‌های احتمالی کلاسیک معادل شوند. Iriyama، Ohya و Volovich مدل دیگری از ماشین تورینگ کوانتومی را تحت عنوان ماشین تورینگ کوانتومی خطی (LQTM) ارائه دادند. این نوع ماشین تورینگ حالتی کلی از ماشین‌های تورینگ کوانتومی کلاسیک هستند که توابع انتقال غیرقابل برگشت را مدل می‌کنند. این مسئله باعث می‌شود که بتوان اندازه‌گیری‌های کوانتومی را بدون نتیجه خروجی کلاسیک بیان کرد.

ماشین تورینگ غیرقطعی

در علوم کامپیوتر نظری، ماشین تورینگ نظری یک ماشین است که در آزمایش‌های فکری برای آزمایش توانایی‌ها و محدودیت‌های کامپیوتر استفاده می‌شود. دراصل، ماشین تورینگ به صورت یک کامپیوتر ساده تصور می‌شود که با دنبال کردن مجموئه‌ای از قوانین، نمادها را در واحد زمان می‌خواند و بر روی یک نوار بی پایان می‌نویسد؛ و با توجه به وضعیت جاری نمادی که دیده است، تعیین می‌کند چه عملی باید انجام دهد. یک مثال از قوانین ماشین تورینگ: «اگر در وضعیت ۲ هستید و نماد 'A' دیدید، آن را به 'B' تغییر دهید و به چپ بروید.» در ماشین تورینگ قطعی، مجموعه قوانین به ازای هر وضعیت داده شده، حداکثر یک حرکت را مجاز می‌کند. ماشین تورینگ غیرقطعی (Non-deterministic Turing machine) برخلاف ماشین تورینگ قطعی، دارای مجموعه قوانینی است که به ازای هر وضعیت، بیشتر از یک حرکت را مجاز می‌کند. برای مثال، ماشین تورینگ غیرقطعی ممکن است هر دو قوانین «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘B’ تغییردهید و به چپ بروید.» و «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘C’ تغییر دهید و به راست بروید» را در مجموعه قوانینش داشته باشد. ماشین تورینگ معمولی (قطعی - DTM) دارای تابع انتقال است که برای وضعیت داده شده و نمادی که روی نوار به آن اشاره می‌شود، ۳ چیز را مشخص می‌کند: نمادی که باید روی نوار نوشته شود، جهت حرکت هد (چپ، راست یا هیچکدام) و وضعیت بعدی ... برای مثال، X روی نوار در وضعیت ۳ ممکن است DTM را وادار به نوشتن Y روی نوار، حرکت هد به راست و انتقال به وضعیت ۵ کند. تفاوت ماشین تورینگ غیرقطعی (NTM) این است که وضعیت داده شده و نماد روی نوار ۳چیز منحصربه فرد را مشخص نمی‌کند، بلکه برای ترکیب مشابه از وضعیت و نماد ممکن است انتقال‌های متفاوتی انجام شود. برای مثال، X روی نوار در وضعیت۳ ممکن است به ماشین اجازه دهد Y را روی نوار بنویسد، به راست برود و به وضعیت ۵ برود یا X را بنویسد، به چپ برود و در وضعیت ۳ بماند.

ماشین خواندنی تورینگ

ماشین‌های خواندنی تورینگ یا ماشین‌های تعیین‌پذیر حالات متناهی ۲مسیره (Read-only Turing machine یا Two-way deterministic finite-state automaton) رده‌ای از مدل‌های محاسبه پذیری هستند که مانند یک ماشین تورینگ استاندارد عمل می‌کنند و می‌توانند در هر ۲ جهت روی نوار حرکت کنند اما نمی‌توانند چیزی بنویسند.در حقیقت این ماشین‌ها از نظر قدرت محاسباتی معادل یک ماشین تعیین‌پذیر حالات متناهی هستند که فقط می‌توانند عمل تجزیه و تحلیل را روی یک زبان منظم انجام دهند.

ماشین تورینگ احتمالی

در نظریه محاسبه پذیری، یک ماشین تورینگ احتمالی (به انگلیسی: Probabilistic turing machines) یک ماشین تورینگ غیر قطعی است که بین انتقال‌های موجود در هر نقطه بوسیلهٔ برخی از توزیع‌های احتمال به صورت تصادفی یکی را انتخاب می‌کند. در مورد احتمال‌های برابر برای انتقال‌ها، می‌توان آن را به عنوان یک تورینگ ماشین قطعی در نظر گرفت که دارای یک حوزه اضافی «نوشتن» است که در آن ارزش «نوشتن» به صورت یکنواخت روی الفبای ماشین تورینگ توزیع شده است. (به طور کلی، احتمال مساوی برای نوشتن '۱ 'یا' ۰ ' روی نوار). یکی دیگر از فرمول بندی‌های رایج یک ماشین تورینگ قطعی با یک نوار اضافی که شامل بیت‌های تصادفی است که نوار تصادفی نامیده می‌شود. به عنوان یک نتیجه، یک ماشین تورینگ احتمالی (بر خلاف یک ماشین تورینگ قطعی) می‌تواند نتایج تصادفی داشته باشد؛ با یک ورودی معین و قرار گرفتن در یک وضعیت از ماشین، ممکن است زمان اجراهای مختلف بدست اورد یا ممکن است ماشین اصلاً متوقف نشود. به علاوه، ممکن است ورودی در یک اجرا پذیرش و همان ورودی در اجرای دیگر رد شود. بنابراین مفهوم پذیرش یک رشته توسط یک ماشین تورینگ احتمالی را می‌توان به روش‌های مختلف تعریف کرد. کلاس‌های پیچیدگی زمانی متفاوتی که برای تعاریف مختلف پذیرش وجود دارند شامل RP, Co-RP, BPP و ZPP هستند. اگر ماشین به جای زمان چندجمله‌ای به فضای لگاریتمی محدود شود کلاس‌های مشابهRL,Co-RL, BPL, ZPL نیز بدی می ایند. با اجرای هر دو محدودیت RLP ،Co-RLP، BPLP، و ZPLP بدست می ایند. همچنان محاسبه پذیری احتمالی برای تعریف اکثر کلاس‌های سیستم‌های اثبات تعاملی(interactive proof systems)، حیاتی است.

ماشین تورینگ چندمسیره

ماشین تورینگ چندمسیره (Multi-track Turing machine) یا چندمجرایی نوع خاصی از ماشین تورینگ چندنواره است. در یک ماشین تورینگ استاندارد با n نوار ،n کلاهک به صورت مستقل در امتداد n مسیر حرکت می‌کنند. در یک ماشین تورینگ چند مجرایی با n مجرا یک کلاهک روی تمام مجراها عمل خواندن و نوشتن را به صورت هم‌زمان انجام می‌دهد. هر موقعیت در این ماشین تورینگ شامل n نماد از حروف الفبا می‌باشد. این ماشین تورینگ، معادل ماشین تورینگ استاندارد است و زبان‌های شمارا را، که به صورت بازگشتی تعریف شده‌اند، می‌پذیرد. با توجه به پیچیدگی برنامه‌های کامپیوتری، ماشین محاسبه تورینگ چند نواری در مقایسه با ماشین‌هایی که آن‌ها را شبیه‌سازی می‌کند، فقط دارای عامل لگاریتمی است که عملکرد آن را آهسته‌تر می‌نماید. هنگامیکه آلن تورینگ به نظریه ساخت دستگاه محاسباتی خود رسید درذهنش فقط مدل محاسباتی ساده و قوای برای محاسبه تمامی عملگرهای ممکن داشت. کلود شانون ابتدا به صراحت در سال ۱۹۵۶ مسئله اختراع کوچکترین ماشین محاسباتی تیورینگ را مطرح نمود. وی نشان داد تا زمانی‌که دو حالت مورد استفاده قرار گیرند دو نماد کافی هستند و همیشه این امکان وجود داشت که علائم به جای حالات بکار گرفته شوند. «ماروین مینسکی» با استفاده از سیستم‌های داده‌ای دو حرفی، ماشین محاسبه تورینگی با ۷ حالت و ۴ علامت کشف نمود. از آن زمان سایر ماشین‌های محاسباتی تورینگ توسط «یوری روگوژین» و سایرین با استفاده از روش شبیه‌سازی سیستم حروف به وجود آمدند. اگر m را حالات و n را علائم در نظر بگیریم، مجموعه‌های زیر یافت می‌شوند: (۲، ۱۵)، (۳٬۹)، (۴٬۶)، (۵٬۵)، (۶٬۴)، (۳٬۹) و (۲٬۱۸). ماشین (۶٬۴) «روگوژین» فقط ۲۲ دستورالعمل دارد و هیچ معیار UTM کوچکتر در آن وجود ندارد؛ ولیکن، با تعمیم معیار مدل ماشین محاسبه تورینگ حتی ماشین‌های محاسباتی کوچکتر نیز قابل پذیرش هستند. چنین تعمیمی تکرار یک کلمه نامحدود را بر یک طرف یا دو طرف ورودی ماشین میسر می‌سازد، و موجب گسترش فراگیری آن و در نتیجه شناخت آن به عنوان «نیمه ضعیف» یا «ضعیف» می‌گردد. در ماشین محاسبه تورینگ کوچک و ضعیفی که قانون ۱۱۰ دستگاه‌های هدایت خودکار تلفن‌های همراه را شبیه‌سازی می‌کند از مجموعه‌های دو تایی (۶٬۲)، (۳٬۳) و (۲٬۴) استفاه می‌شود. ماشین محاسبه تورینگ ۲ حالته ۳ علامتی وولفریم با استفاده از قراردادن حروف ابتدایی، ضعف این فراگیری را بیشتر نشان می‌دهد. سایر متغیرها در الگوی استاندارد ماشین محاسبه تورینگ از UTMهای کوچک استفاده می‌کردند ازجمله ماشین‌هایی با نوارهای متعدد ذخیره اطلاعات یا نوارهای چند بعدی و ماشین‌هایی با دستگاه‌های هدایت خودکار محدود.

نظریات وابسته به ریاضیات

با رمزگذاری و نامگذاری جداول عملکردها به عنوان رشته‌ای از داده‌ها و دستورهای، این امکان به وجود آمد تا ماشین‌های تورینگ برای فرضیاتی در مورد عملکرد سایر ماشین‌های تورینگ پاسخی بیابند؛ اما بیشتر این فرضیات قابل اثبات نبودند یعنی عملگر مورد نظر از لحاظ مکانیکی قابل محاسبه نبود. مثلاً، این مشکل که آیا عملکرد ماشین تورینگ با ورود داده‌های خاص یا تمامی داده‌ها متوقف خواهد شد، در مقاله اولیه تورینگ غیرقابل اثبات بود و «مشکل توقف برنامه» نام گرفت. (Halting Problem به مشکلی اطلاق می‌شود که در آن یک برنامه کامپیوتری انتهایی ندارد و به جایی نمی‌رسد). قضیه «رایس» نشان می‌دهد که هر سؤال مهمی در مورد خروجی ماشین تورینگ غیرقابل اثبات است. ماشین محاسبه تورینگ نشان می‌دهد که هر عملگر یا زبان در یک برنامه کامپیوتری خاص که نیازمند اجرای کل آن برنامه باشد قابل محاسبه است و هر زبان عددی را می‌پذیرد. طبق نظریه «چرچ – تورینگ»، مسائلی که به وسیله ماشین محاسبه تورینگ قابل حل باشند دقیقاً همان مسائلی هستندکه از طریق الگوریتمی یا روش مؤثر محاسباتی قابل حل هستند. به این دلیل، ماشین محاسبه تورینگ معیاری است که با آن سیستم‌های محاسباتی و هر سیستمی که می‌تواند ماشین محاسبه تورینگ را شبیه‌سازی کند مقایسه می‌شوند و «تورینگ کامل» نام دارد. نسخه برگرفته از ماشین محاسبه تورینگ، تابع عمومی است، یعنی تابع قابل محاسبه‌ای که می‌تواند برای محاسبه سایر توابع قابل محاسبه بکار گرفته شود. ماشین محاسبه تورینگ وجود این تابع عمومی را اثبات می‌کند.

عملکرد

داده در ماشین تورینگ می‌تواند به شکل الفبایی (صفر و یک) فرض شود، هر الفبای دیگری می‌تواند به شکل صفر و یک رمزگذاری گردد. عملکرد یک ماشین تورینگ (M) از طریق تابع متغیر آن تعریف می‌شود. این تابع نیز می‌تواند به سادگی به رشته‌ای از دستورهای صفر و یک تبدیل گردد. مقدار الفبای M، تعداد نوارهای ذخیره اطلاعات و اندازه فواصل آن‌ها می‌تواند از جدول توابع متغیر استخراج شود. حالات و نمادهای متفاوت از طریق جایگاه آن‌ها تعیین می‌شوند مثلاً دو حالت اول به‌طور قراردادی حالات شروع و پایان را نشان می‌دهند. در نتیجه، هر ماشین محاسبه تورینگ می‌تواند رشته‌ای از دستورهای الفبایی صفر و یک را رمزگذاری نماید. به علاوه، می‌توان نتیجه گرفت که هر گونه رمزگذاری نامعتبری نمایانگر یک محاسبه تورینگ نامعتبر است که متوقف می‌شود و هر ماشین تورینگ می‌تواند با رمزگذاری مداوم و ثابت با عدد قراردادی یک (۱) در انتهای یک دستور، تعداد نامحدودی رمزگذاری انجام دهد دقیقاً مانند توضیحاتی که در یک زبان برنامه‌نویسی می‌آید. تعجب‌آور نیست که با توجه به وجود عدد «گودل» و معادله محاسباتی میان ماشین تیورینگ و عملگرهای بازگشتی µ می‌توان به این رمزگذاری دست یافت. همچنین این توضیح و تفسیر در تمامی دستورهای باینری (صفر و یک) α و ماشین تورینگ Mα مشترک است. با نگاهی به آغاز این نوع رمزگذاری در سال ۱۹۹۶ توسط «هِنی» و «اِستِرن» می‌توان دریافت که اگر ماشین تورینگ را Mα فرض کنیم که داده X را در مراحل N متوقف می‌کند، پس ماشین محاسبه تورینگ چند نوارای به وجود می‌آید که در داده α، x (با فرض نوارهای متفاوت) در CN پردازش مراحل N را شروع می‌کند، C مقدار ثابتی است که به طول دستور x بستگی ندارد، اما به اندازه، تعداد نوارهای ذخیره اطلاعات و تعداد حالات M وابسته است. این عمل در متغیر O نیز شبیه‌سازی می‌شود. (N آغاز پردازش N)