ฟังก์ชันเวียนเกิดและเครื่องจักรเรจิสเตอร์

ทฤษฎีฟังก์ชันเวียนเกิดสร้างฟังก์ชันที่คำนวณได้จากชุดของการดำเนินการพื้นฐาน ในขณะที่เครื่องจักรเรจิสเตอร์คำนวณด้วยจำนวนเต็มที่เก็บไว้ในเรจิสเตอร์ ซึ่งเป็นสองแบบจำลองที่ครอบคลุมเครื่องจักรทัวริงและยืนยันความแข็งแกร่งของการคำนวณได้

Definition

ฟังก์ชันเวียนเกิดทั่วไปคือฟังก์ชันที่สร้างขึ้นจากค่าคงที่ ตัวสืบทอด (successor) และการฉาย (projections) โดยการประกอบ (composition) การเวียนเกิดแบบดั้งเดิม (primitive recursion) และการย่อขนาดแบบไม่จำกัด (unbounded minimization) ส่วนเครื่องจักรเรจิสเตอร์เป็นอุปกรณ์เชิงนามธรรมที่คำนวณโดยการเพิ่ม ลด และทดสอบเนื้อหาของชุดเรจิสเตอร์จำนวนจำกัดที่เก็บจำนวนธรรมชาติ

Scope

หัวข้อนี้ครอบคลุมฟังก์ชันเวียนเกิดแบบดั้งเดิม (primitive recursive functions) การเพิ่มการย่อขนาดแบบไม่จำกัด (unbounded minimization) เพื่อให้ได้ฟังก์ชันเวียนเกิดทั่วไป (general recursive functions) ฟังก์ชัน Ackermann ในฐานะฟังก์ชันที่คำนวณได้แต่ไม่ใช่แบบดั้งเดิม เครื่องจักรเรจิสเตอร์และเครื่องนับ (counter machines) และความเป็นสากลของพวกมัน และความเท่าเทียมกันของแบบจำลองเหล่านี้ทั้งหมดกับการคำนวณแบบทัวริง

Core questions

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

Key theories

ความเท่าเทียมกันกับการคำนวณแบบทัวริง

ฟังก์ชันเวียนเกิดทั่วไปและฟังก์ชันที่คำนวณโดยเครื่องจักรเรจิสเตอร์เป็นฟังก์ชันที่คำนวณได้แบบทัวริงอย่างแท้จริง ซึ่งเสริมสร้างวิทยานิพนธ์ Church–Turing ผ่านแบบจำลองที่นิยามในเชิงเลขคณิตและเชิงเครื่องจักรพื้นฐานอย่างแท้จริง

นอกเหนือจากการเวียนเกิดแบบดั้งเดิม

ฟังก์ชัน Ackermann เป็นฟังก์ชันทั้งหมดและคำนวณได้ แต่เติบโตเร็วเกินไปที่จะเป็นแบบเวียนเกิดดั้งเดิม ซึ่งแสดงให้เห็นว่าการค้นหาแบบไม่จำกัดเป็นสิ่งจำเป็น และฟังก์ชันเวียนเกิดดั้งเดิมเป็นคลาสย่อยที่แท้จริงของฟังก์ชันที่คำนวณได้

ความเป็นสากลของเครื่องจักรเรจิสเตอร์

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

Clinical relevance

เครื่องจักรเรจิสเตอร์จำลองเลขคณิตจำนวนเต็มของโปรเซสเซอร์จริงได้โดยตรงมากกว่าเทป การเวียนเกิดแบบดั้งเดิมสอดคล้องกับโปรแกรมที่สิ้นสุดเสมอและเป็นพื้นฐานของภาษาฟังก์ชันทั้งหมดและการวิเคราะห์การสิ้นสุด และมุมมองฟังก์ชันเวียนเกิดเชื่อมโยงการคำนวณเข้ากับรากฐานของคณิตศาสตร์

History

Gödel และ Herbrand ได้นิยามฟังก์ชันเวียนเกิดทั่วไปในช่วงต้นทศวรรษ 1930 และ Kleene ได้พัฒนาทฤษฎีนี้ รวมถึงบทบาทของการย่อขนาด Ackermann ได้แสดงฟังก์ชันที่เติบโตอย่างรวดเร็วของเขาไปก่อนหน้านี้ และ Minsky ได้แนะนำเครื่องจักรเรจิสเตอร์และเครื่องนับในทศวรรษ 1960 โดยพิสูจน์ว่าแม้แต่เครื่องจักรสองตัวนับก็เป็นสากล

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

ฟังก์ชันเวียนเกิดแบบดั้งเดิมและฟังก์ชันเวียนเกิดทั่วไปแตกต่างกันอย่างไร?

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

เครื่องจักรที่มีเพียงสองตัวนับจะทรงพลังเท่าคอมพิวเตอร์ได้อย่างไร?

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