เครื่องทัวริงมีหน่วยความจำหรือไม่?

2024 ผู้เขียน: Fiona Howard | [email protected]. แก้ไขล่าสุด: 2024-01-10 06:43

เครื่องจักรทัวริงคล้ายกับไฟไนต์ออโตมาตา/ไฟไนต์สเตทแมชชีน แต่มี ข้อได้เปรียบของหน่วยความจำไม่จำกัด … พวกมันสามารถจำลองคอมพิวเตอร์ทั่วไปได้ ปัญหาที่คอมพิวเตอร์ทั่วไปสามารถแก้ไขได้ (เมื่อมีหน่วยความจำเพียงพอ) ก็จะแก้ไขได้โดยใช้เครื่องทัวริง และในทางกลับกัน

RAM กับ TM ต่างกันอย่างไร

A เครื่องทัวริง can't เครื่อง RAM สามารถทำเลขคณิตใน O(1) (ภายใต้ข้อจำกัดบางประการ) เครื่องทัวริงทำไม่ได้ เครื่องทัวริงพหุนามจำลองเครื่อง RAM นั่นคือสำหรับค่าคงที่ c บางเครื่องที่ทำงานในเวลา O(nk) สามารถจำลองได้โดยเครื่องทัวริงที่ทำงานในเวลา O (nck)

เทปของเครื่องทัวริงไม่มีขอบเขตหรือไม่

A Turing Machine (TM) เป็นเครื่องของรัฐที่ประกอบด้วยความทรงจำสองอย่าง: เทปไม่มีขอบเขต และตารางควบคุมสถานะจำกัด เทปเก็บข้อมูลเป็นสัญลักษณ์ เครื่องมีชุดการทำงานที่เหมาะสมน้อยมาก 6 เลย (อ่าน เขียน เลื่อนซ้าย เลื่อนขวา เปลี่ยนสถานะ หยุด) บนเทป

ทำไมเครื่องทัวริงถึงทรงพลัง

เครื่องจักรทัวริงทรงพลังแค่ไหน? เครื่องทัวริงสามารถรับภาษาปกติหรือไม่มีบริบทได้ เครื่องทัวริงสามารถคำนวณเลขคณิตพื้นฐานได้ … วิทยานิพนธ์ของทัวริงระบุว่าการคำนวณใดๆ ที่สามารถทำได้โดยใช้ "วิธีการทางกล" สามารถทำได้โดยเครื่องทัวริง (ไม่สนใจประเด็นด้านประสิทธิภาพ)

เครื่องจักรทัวริงวนรอบตลอดไปได้ไหม

turing(turingDescrip) ไม่สามารถหยุดหรือวนซ้ำได้ตลอดไป; มันไม่สมเหตุสมผลเลย