اگر دو TM داشته باشیم که یک زبان قابل تصمیم را توصیف می کنند، آیا سؤال هم ارزی هنوز غیرقابل تصمیم گیری است؟
در زمینه نظریه پیچیدگی محاسباتی، مفهوم تصمیم پذیری نقش اساسی دارد. اگر یک ماشین تورینگ (TM) وجود داشته باشد که بتواند برای هر ورودی معینی تعیین کند که آیا به زبان تعلق دارد یا نه، زبانی قابل تصمیم گیری است. تصمیم پذیری یک زبان یک ویژگی مهم است، زیرا به ما امکان می دهد در مورد زبان و ویژگی های آن به صورت الگوریتمی استدلال کنیم.
سوال هم ارزی ماشین های تورینگ با تعیین اینکه آیا دو TM داده شده یک زبان را تشخیص می دهند، مربوط می شود. به طور رسمی، با توجه به دو TM M1 و M2، سوال هم ارزی می پرسد که آیا L(M1) = L(M2)، که در آن L(M) نشان دهنده زبان شناخته شده توسط TM M است.
مشکل کلی تعیین هم ارزی دو TM غیرقابل تصمیم گیری شناخته شده است. این بدان معنی است که هیچ الگوریتمی وجود ندارد که همیشه بتواند تصمیم بگیرد که آیا دو TM دلخواه یک زبان را تشخیص می دهند یا خیر. این نتیجه توسط آلن تورینگ در کار اصلی خود در مورد محاسبه پذیری اثبات شد.
با این حال، توجه به این نکته مهم است که این نتیجه برای حالت کلی TM های دلخواه صادق است. در مورد خاصی که هر دو TM زبان های قابل تصمیم گیری را توصیف می کنند، سوال هم ارزی قابل تصمیم گیری می شود. این به این دلیل است که زبان‌های قابل تصمیم آن‌هایی هستند که برای آنها یک TM وجود دارد که می‌تواند عضویت در زبان را تعیین کند. بنابراین، اگر دو TM زبان‌های قابل تصمیم را توصیف کنند، می‌توانیم یک TM جدید بسازیم که هم ارزی آنها را تعیین می‌کند.
برای توضیح این موضوع، اجازه دهید یک مثال را در نظر بگیریم. فرض کنید دو TM M1 و M2 داریم که زبان های قابل تصمیم گیری را توصیف می کنند. ما می توانیم یک TM M جدید بسازیم که هم ارزی آنها را به صورت زیر تعیین می کند:
1. با توجه به ورودی x، M1 را روی x و M2 را روی x به طور همزمان شبیه سازی کنید.
2. اگر M1 x را می پذیرد و M2 x را می پذیرد، پس بپذیرید.
3. اگر M1 x را رد کرد و M2 x را رد کرد، پس بپذیرید.
4. در غیر این صورت رد کنید.
با ساخت، TM M یک ورودی x را می پذیرد اگر و فقط اگر هر دو M1 و M2 x را بپذیرند، یا هر دو M1 و M2 x را رد کنند. این بدان معنی است که M معادل M1 و M2 را برای هر ورودی x تعیین می کند.
در حالی که مشکل کلی تعیین هم ارزی دو TM دلخواه غیرقابل تصمیم گیری است، اگر TM ها زبان های قابل تصمیم گیری را توصیف کنند، سوال هم ارزی قابل تصمیم گیری می شود. این به این دلیل است که زبان‌های قابل تصمیم را می‌توان توسط یک TM تعیین کرد و به ما اجازه می‌دهد تا یک TM بسازیم که معادل آنها را تعیین می‌کند. تصمیم‌پذیری سؤال هم ارزی برای TMهایی که زبان‌های قابل تصمیم‌گیری را توصیف می‌کنند، بینش مهمی را در مورد پیچیدگی محاسباتی این زبان‌ها ارائه می‌کند.
سایر پرسش ها و پاسخ های اخیر در مورد قابلیت تجزیه پذیری:
- آیا می توان یک نوار را به اندازه ورودی محدود کرد (که معادل این است که هد ماشین تورینگ برای حرکت فراتر از ورودی نوار TM محدود شده است)؟
- معادل بودن انواع مختلف ماشین های تورینگ در قابلیت محاسباتی به چه معناست؟
- آیا یک زبان قابل تشخیص تورینگ می تواند زیرمجموعه ای از زبان تصمیم پذیر را تشکیل دهد؟
- آیا مشکل توقف ماشین تورینگ قابل حل است؟
- مشکل پذیرش برای اتوماتای محدود خطی با ماشین‌های تورینگ چه تفاوتی دارد؟
- مثالی از مسئله ای که می تواند توسط یک اتومات محدود خطی حل شود را بیاورید.
- مفهوم تصمیم پذیری را در زمینه اتوماتای محدود خطی توضیح دهید.
- اندازه نوار در اتوماتای محدود خطی چگونه بر تعداد پیکربندی‌های مجزا تأثیر می‌گذارد؟
- تفاوت اصلی بین اتوماتای محدود خطی و ماشین های تورینگ چیست؟
- فرآیند تبدیل ماشین تورینگ به مجموعه‌ای از کاشی‌ها برای PCP را توضیح دهید و اینکه چگونه این کاشی‌ها تاریخچه محاسبات را نشان می‌دهند.
سوالات و پاسخ های بیشتر را در Decidability مشاهده کنید