Primitive Recursive Functions สำหรับโปรแกรมเมอร์สายปฏิบัติ

ฟังก์ชันเรียกซ้ำพื้นฐาน: คู่มือสำหรับโปรแกรมเมอร์สายปฏิบัติ

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

Part I: สรุป

• หากโปรแกรมที่เขียนด้วยภาษาที่ Turing-complete ทำงานได้เร็วกว่า O(22N) ก็สามารถนำไปเขียนใหม่ในภาษาที่ไม่เป็น Turing-complete ได้เช่นกัน
• ปัญหาส่วนใหญ่ที่ใช้งานจริง เร็วกว่า "สองยกกำลังสองยกกำลังสอง"
• ภาษาที่ไม่เป็น Turing-complete ไม่ได้สร้างข้อจำกัดในทางปฏิบัติ
• กรณีที่โปรแกรมไม่ยอมหยุดทำงาน กับกรณีที่หยุดทำงานแต่ใช้เวลามหาศาล ถูกมองว่าเหมือนกัน

Part II: กลไกการทำงานของเครื่อง

เครื่องสถานะจำกัด (Finite State Machines)

• เครื่องสถานะจำกัดรับสตริงเป็นอินพุตและส่งกลับ "ใช่" หรือ "ไม่ใช่"
• มีจำนวนสถานะจำกัด
• ฟังก์ชันเปลี่ยนสถานะรับสถานะปัจจุบันและสัญลักษณ์อินพุตถัดไป แล้วคืนค่าสถานะใหม่
• เครื่องสถานะจำกัดไม่สามารถเข้าสู่ลูปไม่รู้จบได้
• เครื่องสถานะจำกัดมีพลังในการแสดงออกเทียบเท่ากับ regular expression

เครื่องทัวริง (Turing Machines)

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

การเขียนโปรแกรมให้เครื่องทัวริง

• เครื่องทัวริงมีเทปไม่สิ้นสุด
• เครื่องทัวริงไม่ได้รันโปรแกรมที่ผู้ใช้ส่งให้ โปรแกรมถูกฝังตายตัวอยู่ในตัวเครื่อง
• เครื่องทัวริงสากลสามารถจำลองเครื่องทัวริงอื่นได้
• เครื่องทัวริงมีความสามารถในการคำนวณเทียบเท่ากับภาษาอย่าง Python

ข้อจำกัดของเครื่องทัวริง

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

Part III: กลับมาที่ปัญหาเชิงปฏิบัติ

ฟังก์ชันเรียกซ้ำพื้นฐาน (Primitive Recursive Functions)

• ฟังก์ชันเรียกซ้ำพื้นฐานเป็นฟังก์ชันที่รับทูเพิลของจำนวนธรรมชาติเป็นอินพุตและคืนค่าจำนวนธรรมชาติ
• เริ่มจากฟังก์ชัน zero และ succ แล้วประกอบเป็นฟังก์ชันอื่น ๆ
• ไม่อนุญาตให้ใช้ recursion ทั่วไป แต่อนุญาตให้ใช้ลูปในรูปแบบที่มีข้อจำกัด
• สามารถนิยามการบวก การคูณ การยกกำลัง และการดำเนินการอื่น ๆ ได้
• สามารถนิยามตัวดำเนินการเชิงตรรกะและเงื่อนไขได้
• ใช้ตัวเลขเพื่อแทนโครงสร้างข้อมูล

สรุปของ GN⁺

• บทความนี้เขียนขึ้นเพื่อช่วยให้เข้าใจ Turing completeness และฟังก์ชันเรียกซ้ำพื้นฐาน
• อธิบายว่าการไม่เป็น Turing-complete มีความหมายในทางปฏิบัติอย่างไร
• อธิบายความแตกต่างระหว่างเครื่องสถานะจำกัดกับเครื่องทัวริง และอภิปรายข้อจำกัดของเครื่องทัวริง
• อธิบายคำนิยามและวิธีใช้ของฟังก์ชันเรียกซ้ำพื้นฐาน
• บทความนี้จะช่วยให้โปรแกรมเมอร์เข้าใจ Turing completeness และฟังก์ชันเรียกซ้ำพื้นฐานได้ดียิ่งขึ้น
• โปรเจ็กต์ที่มีความสามารถคล้ายกัน ได้แก่ "regular expression" และ "เครื่องสถานะจำกัด"