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

در علوم نظری رایانه، ماشین تورینگ احتمالی  یک ماشین تورینگ غیرقطعی است که بین انتقال‌های موجود در هر نقطه به‌وسیلهٔ برخی از توزیع‌های احتمال به صورت تصادفی یکی را انتخاب می‌کند.

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

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

بنابراین مفهوم پذیرش یک رشته توسط یک ماشین تورینگ احتمالی را می‌توان به روش‌های مختلف تعریف کرد. کلاس‌های پیچیدگی زمانی متفاوتی که برای تعاریف مختلف پذیرش وجود دارند شامل 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

رده:الگوریتم‌های تصادفی
رده:ماشین تورینگ
رده:مدل‌های محاسباتی
رده:نظریه احتمالات پیچیده
رده:ویکی‌سازی رباتیک