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

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