Turing machine

แนวคิดในวิทยาการคอมพิวเตอร์

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

จาก Automata สู่ Turing Machine

Finite Automata: หน่วยความจำจำกัด รองรับ regular language
Pushdown Automata: หน่วยความจำแบบ stack รองรับ context-free language
Turing Machine: หน่วยความจำไม่จำกัด (เทปอนันต์) แก้ปัญหาที่คำนวณได้ทุกประเภท

ภาพประกอบของ Alan Turing

แผนภาพแสดงการทำงานของ Turing Machine

Turing Machine

ภาพประกอบห้องครัวที่มีพ่อครัวกำลังทำตามสูตรอาหาร เปรียบเทียบกับการทำงานของ Turing Machine

ครัวและพ่อครัวในฐานะ Turing Machine

Turing Machine กับความสามารถในการคำนวณ

คำถาม: เราสามารถทำนายได้หรือไม่ว่าโปรแกรมจะหยุดทำงานหรือรันไปตลอดกาลสำหรับ input ที่กำหนด?
ข้อค้นพบของ Turing: ไม่มีอัลกอริทึมสากลที่แก้ปัญหานี้ได้สำหรับทุกโปรแกรม
ผลลัพธ์: Halting Problem เป็นปัญหาที่ตัดสินไม่ได้ บางปัญหาไม่มีวิธีแก้เชิงอัลกอริทึม
ผลกระทบ: ข้อจำกัดด้านการคำนวณส่งผลต่อวิทยาการเข้ารหัสและ AI

แผนภาพแสดง Halting Problem คืออะไร

แนวคิดในวิทยาการคอมพิวเตอร์