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

در نظریهٔ محاسبه پذیری، یک ماشین تورینگ احتمالی (به انگلیسی: Probabilistic turing machines) یک ماشین تورینگ غیر قطعی است که بین انتقال‌های موجود در هر نقطه بوسیلهٔ برخی از توزیع‌های احتمال به صورت تصادفی یکی را انتخاب می‌کند.

در مورد احتمال‌های برابر برای انتقال‌ها، می‌توان آن را به عنوان یک تورینگ ماشین قطعی در نظر گرفت که دارای یک حوزهٔ اضافی «نوشتن» است که در آن ارزش «نوشتن» به صورت یکنواخت روی الفبای ماشین تورینگ توزیع شده است. (به طور کلی، احتمال مساوی برای نوشتن '۱ 'یا' ۰ ' روی نوار). یکی دیگر از فرمول بندی‌های رایج یک ماشین تورینگ قطعی با یک نوار اضافی که شامل بیت‌های تصادفی است که نوار تصادفی نامیده می‌شود.

به عنوان یک نتیجه، یک ماشین تورینگ احتمالی (بر خلاف یک ماشین تورینگ قطعی) می‌تواند نتایج تصادفی داشته باشد؛ با یک ورودی معین و قرار گرفتن در یک وضعیت از ماشین، ممکن است زمان اجراهای مختلف بدست اورد یا ممکن است ماشین اصلاً متوقف نشود. به علاوه، ممکن است ورودی در یک اجرا پذیرش و همان ورودی در اجرای دیگر رد شود.

بنابراین مفهوم پذیرش یک رشته توسط یک ماشین تورینگ احتمالی را می‌توان به روش‌های مختلف تعریف کرد. کلاس‌های پیچیدگی زمانی متفاوتی که برای تعاریف مختلف پذیرش وجود دارند شامل RP, Co-RP, BPP و ZPP هستند. اگر ماشین به جای زمان چندجمله‌ای به فضای لگاریتمی محدود شود کلاس‌های مشابهRL,Co-RL, BPL, ZPL نیز بدی می ایند. با اجرای هر دو محدودیت RLP ،Co-RLP، BPLP، و ZPLP بدست می ایند.

همچنان محاسبه پذیری احتمالی برای تعریف اکثر کلاس‌های سیستم‌های اثبات تعاملی(interactive proof systems)، حیاتی است.

یکی از سوالات اصلی نظریه پیچیدگی این است که آیا تصادفی بودن قدرت را اضافه می‌کند؟ یعنی ایا مسئله‌ای وجود دارد که بتواند در زمان چندجمله‌ای توسط یک ماشین تورینگ احتمالی حل شود ولی توسط یک ماشین تورینگ قطعی نه؟ یا ماشین‌های تورینگ قطعی می‌توانند تمام ماشین‌های تورینگ احتمالی با حداکثر کاهش سرعت چندجمله‌ای را به صورت موثری شبیه‌سازی کنند؟ در حال حاضر محققان معتقدند که سؤال دوم هم ارز مفهوم P = BPP است. تصور درستی همان سؤال برای فضای لگاریتمی به جای زمان چندجمله‌ای (ایا L = BPLP است ؟) به طور گسترده‌تری مورد باور محققان است. از سوی دیگر، قدرتی که تصادفی بودن به سیستم اثبات تعاملی می‌دهد، مانند الگوریتم‌های ساده است برای مسایل سخت، که نشان می‌دهد تصادفی بودن ممکن است قدرت را اضافه کند.

جستارهای وابسته

ماشین تورینگ

منابع

NIST website on probabilistic Turing machines

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.