ในวิทยาการคอมพิวเตอร์เชิง ทฤษฎี เครื่องจักรทัวริงเชิงความน่าจะเป็นคือเครื่องจักรทัวริงแบบไม่กำหนดที่เลือกการเปลี่ยนสถานะ ที่มี อยู่ ณ แต่ละจุดตามการกระจายความน่า จะเป็นบาง อย่าง ผลที่ตามมาคือ เครื่องจักรทัวริงเชิงความน่าจะเป็น (ซึ่งแตกต่างจากเครื่องจักรทัวริงแบบกำหนด) สามารถให้ ผลลัพธ์ แบบสุ่มได้กล่าวคือ ภายใต้ข้อมูลป้อนเข้าและคำสั่งที่กำหนด เครื่องจักรอาจมีเวลาในการทำงานที่แตกต่างกัน หรืออาจไม่หยุดทำงานเลย นอกจากนี้ อาจยอมรับข้อมูลป้อนเข้าในการทำงานครั้งหนึ่งและปฏิเสธข้อมูลป้อนเข้าเดียวกันนั้นในการทำงานอีกครั้งหนึ่ง

ในกรณีที่ความน่าจะเป็นของการเปลี่ยนสถานะเท่ากัน เครื่องจักรทัวริงเชิงความน่าจะเป็นสามารถนิยามได้ว่าเป็นเครื่องจักรทัวริงเชิง กำหนด ที่มีคำสั่ง "เขียน" เพิ่มเติม โดยที่ค่าของการเขียนนั้นมีการกระจายอย่างสม่ำเสมอในตัวอักษรของเครื่องจักรทัวริง (โดยทั่วไปคือ ความน่าจะเป็นเท่ากันของการเขียน "1" หรือ "0" ลงบนเทป) อีกหนึ่งการกำหนดรูปแบบที่นิยมใช้คือเครื่องจักรทัวริงเชิงกำหนดที่มีเทปที่บรรจุบิตสุ่มเพิ่มเติม เรียกว่า "เทปสุ่ม"

คอมพิวเตอร์ควอนตัม (หรือเครื่องจักรทัวริงควอนตัม ) เป็นอีกรูปแบบหนึ่งของการคำนวณที่มีลักษณะเป็นความน่าจะเป็นโดยเนื้อแท้

เครื่องจักรทัวริงเชิงความน่าจะเป็นเป็นเครื่องจักรทัวริงแบบไม่กำหนด ประเภทหนึ่ง ซึ่งแต่ละขั้นตอนที่ไม่กำหนดเป็นการ "โยนเหรียญ" กล่าวคือ ในแต่ละขั้นตอนจะมีสองการเคลื่อนไหวถัดไปที่เป็นไปได้ และเครื่องจักรทัวริงจะเลือกการเคลื่อนไหวที่จะทำโดยใช้ความน่าจะเป็น^{[ 1 ]}

เครื่องจักรทัวริงเชิงความน่าจะเป็นสามารถนิยามอย่างเป็นทางการได้ว่าเป็น 7-tuple โดยที่ ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})}$

• ${\displaystyle Q}$เป็นเซตของสถานะที่มีจำนวนจำกัด
• ${\displaystyle \Sigma }$คือตัวอักษรที่ป้อนเข้าไป
• ${\displaystyle \Gamma }$เป็นอักษรเทป ซึ่งรวมถึงสัญลักษณ์ว่าง#
• ${\displaystyle q_{0}\in Q}$คือสถานะเริ่มต้น
• ${\displaystyle A\subseteq Q}$คือเซตของสถานะที่ยอมรับ (สุดท้าย)
• ${\displaystyle \delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$คือฟังก์ชันการเปลี่ยนสถานะเชิงความน่าจะเป็นตัวแรกคือการเคลื่อนที่ไปทางซ้ายหนึ่งช่องบนเทปของเครื่องทัวริง และคือการเคลื่อนที่ไปทางขวาหนึ่งช่อง${\displaystyle L}$${\displaystyle R}$
• ${\displaystyle \delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$เป็นฟังก์ชันการเปลี่ยนผ่านเชิงความน่าจะเป็นลำดับที่สอง

ในแต่ละขั้นตอน เครื่องจักรทัวริงจะใช้ฟังก์ชันการเปลี่ยนผ่านหรือฟังก์ชันการเปลี่ยนผ่านแบบ สุ่ม ^{[ 2 ]}การเลือกนี้เกิดขึ้นโดยอิสระจากการเลือกก่อนหน้าทั้งหมด ด้วยวิธีนี้ กระบวนการเลือกฟังก์ชันการเปลี่ยนผ่านในแต่ละขั้นตอนของการคำนวณจึงคล้ายกับการโยนเหรียญ ${\displaystyle \delta _{1}}$${\displaystyle \delta _{2}}$

การเลือกฟังก์ชันการเปลี่ยนสถานะแบบสุ่มในแต่ละขั้นตอนทำให้เกิดข้อผิดพลาดในเครื่องทัวริง กล่าวคือ สตริงที่เครื่องทัวริงควรยอมรับอาจถูกปฏิเสธในบางครั้ง และสตริงที่เครื่องทัวริงควรปฏิเสธอาจถูกยอมรับในบางครั้ง เพื่อรองรับสิ่งนี้ ภาษาจะถูกกล่าวว่าได้รับการยอมรับโดยเครื่องทัวริงแบบสุ่มด้วยความน่าจะเป็นของข้อผิดพลาดถ้า: ${\displaystyle L}$${\displaystyle \epsilon }$${\displaystyle M}$

1. สตริงในนั้นหมายความว่า${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. สตริงที่ไม่อยู่ในนั้นหมายความว่า${\displaystyle w}$${\displaystyle L}$${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

เนื่องจากข้อผิดพลาดที่เกิดขึ้นจากการใช้การโยนเหรียญแบบสุ่ม การยอมรับสตริงโดยเครื่องทัวริงแบบสุ่มจึงสามารถกำหนดได้หลายวิธี หนึ่งในแนวคิดดังกล่าวซึ่งรวมถึงคลาสความซับซ้อนที่สำคัญหลายคลาสคือการอนุญาตให้มีความน่าจะเป็นของข้อผิดพลาด 1/3 ตัวอย่างเช่น คลาสความซับซ้อนBPPถูกกำหนดให้เป็นคลาสของภาษาที่เครื่องทัวริงแบบสุ่มรู้จักในเวลาพหุนามด้วยความน่าจะเป็นของข้อผิดพลาด 1/3 อีกคลาสหนึ่งที่กำหนดโดยใช้แนวคิดการยอมรับนี้คือBPLซึ่งเหมือนกับBPPแต่มีข้อจำกัดเพิ่มเติมว่าภาษาเหล่านั้นต้องสามารถแก้ไขได้ใน พื้นที่ลอการิทึม

ระดับความซับซ้อนที่เกิดขึ้นจากนิยามการยอมรับอื่นๆ ได้แก่RP , co-RPและZPPหากจำกัดเครื่องให้ใช้พื้นที่หน่วยความจำแบบลอการิทึมแทนเวลาแบบพหุนาม จะได้ระดับความซับซ้อนที่คล้ายคลึงกันคือ RL , co-RLและZPLโดยการบังคับใช้ข้อจำกัดทั้งสองอย่างจะได้ RLP , co-RLP , BPLPและZPLP

การคำนวณเชิงความน่าจะเป็นมีความสำคัญอย่างยิ่งต่อการกำหนดนิยามของระบบพิสูจน์เชิงโต้ตอบ ส่วนใหญ่ ซึ่งเครื่องตรวจสอบความถูกต้องต้องอาศัยความสุ่มเพื่อหลีกเลี่ยงการถูกคาดการณ์และหลอกลวงโดยเครื่องพิสูจน์ความถูกต้องที่มีอำนาจเหนือกว่า ตัวอย่างเช่น คลาสIPเท่ากับPSPACEแต่ถ้าเอาความสุ่มออกจากเครื่องตรวจสอบความถูกต้อง เราจะเหลือเพียงNPซึ่งยังไม่ทราบแน่ชัด แต่เชื่อกันอย่างกว้างขวางว่าเป็นคลาสที่เล็กกว่ามาก

หนึ่งในคำถามสำคัญของทฤษฎีความซับซ้อนคือ ความสุ่มเพิ่มพลังหรือไม่ กล่าวคือ มีปัญหาใดบ้างที่สามารถแก้ไขได้ในเวลาพหุนามโดยเครื่องทัวริงเชิงความน่าจะเป็น แต่ไม่สามารถแก้ไขได้โดยเครื่องทัวริงเชิงกำหนด หรือเครื่องทัวริงเชิงกำหนดสามารถจำลองเครื่องทัวริงเชิงความน่าจะเป็นทั้งหมดได้อย่างมีประสิทธิภาพโดยมีความช้าลงอย่างมากที่สุดเพียงพหุนามหรือไม่ เป็นที่ทราบกันว่าP ⊆ BPPเนื่องจากเครื่องทัวริงเชิงกำหนดเป็นเพียงกรณีพิเศษของเครื่องทัวริงเชิงความน่าจะเป็น อย่างไรก็ตาม ยังไม่แน่ชัดว่า (แต่เป็นที่สงสัยกันอย่างกว้างขวางว่า) BPP ⊆ P หรือไม่ ซึ่งหมายความว่าBPP = Pคำถามเดียวกันนี้สำหรับปริภูมิล็อกแทนเวลาพหุนาม ( L = BPLP หรือไม่ ?) เป็นที่เชื่อกันอย่างกว้างขวางว่าเป็นจริงยิ่งกว่า ในทางกลับกัน พลังที่ความสุ่มมอบให้แก่ระบบพิสูจน์แบบโต้ตอบ ตลอดจนอัลกอริทึมง่ายๆ ที่สร้างขึ้นสำหรับปัญหาที่ยาก เช่น การทดสอบความเป็นจำนวนเฉพาะในเวลาพหุนามและการทดสอบการเชื่อมต่อของกราฟในปริภูมิล็อก บ่งชี้ว่าความสุ่มอาจเพิ่มพลังได้

• อัลกอริทึมแบบสุ่ม

• เว็บไซต์ NIST เกี่ยวกับเครื่องจักรทัวริงเชิงความน่าจะเป็น