ฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิม

ในทฤษฎีการคำนวณ (Computability Theory) ฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิม (Primitive Recursive Function) คือฟังก์ชันที่สามารถคำนวณได้ด้วยโปรแกรมคอมพิวเตอร์ที่ใช้ลูปแบบ "for" เท่านั้น ซึ่งหมายความว่าจำนวนรอบของการทำงานในทุกลูปจะถูกกำหนดไว้ล่วงหน้าก่อนที่จะเริ่มการทำงานของลูปนั้นๆ

ฟังก์ชันประเภทนี้เป็นเซตย่อย (Subset) ของฟังก์ชันรีเคอร์ซีฟทั่วไป (General Recursive Functions) ที่เป็นฟังก์ชันรวม (Total Functions) ความสำคัญของฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิมอยู่ที่การที่ฟังก์ชันส่วนใหญ่ที่ใช้ในการศึกษาด้านทฤษฎีจำนวนและคณิตศาสตร์ทั่วไปเป็นฟังก์ชันประเภทนี้ เช่น การบวก การหาร แฟกทอเรียล ฟังก์ชันเลขชี้กำลัง และฟังก์ชันที่คืนค่าจำนวนเฉพาะลำดับที่ n

ในทางทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เซตของฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิมจะถูกแทนด้วยสัญลักษณ์ PR การพิสูจน์ว่าฟังก์ชันหนึ่งเป็นฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิมนั้น สามารถทำได้โดยการแสดงให้เห็นว่าความซับซ้อนทางเวลา (Time Complexity) ของฟังก์ชันนั้นมีขอบเขตบน (Upper Bound) ที่ถูกจำกัดด้วยฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิมของขนาดอินพุต

นิยามและโครงสร้าง

ฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิมจะรับอาร์กิวเมนต์เป็นจำนวนธรรมชาติ (จำนวนเต็มที่ไม่เป็นลบ: {0, 1, 2, ...}) ในจำนวนที่แน่นอน และคืนค่าเป็นจำนวนธรรมชาติ หากฟังก์ชันรับอาร์กิวเมนต์ n ตัว จะเรียกว่าเป็นฟังก์ชัน n-ary

ฟังก์ชันพื้นฐาน (Basic Primitive Recursive Functions)

ฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิมถูกสร้างขึ้นจากสัจพจน์ของฟังก์ชันพื้นฐาน ดังนี้:

• ฟังก์ชันค่าคงที่ (Constant Functions) $C_{n}^{k}$: สำหรับจำนวนธรรมชาติ $n$ และ $k$ ใดๆ ฟังก์ชัน $k$-ary ที่นิยามโดย $C_{n}^{k}(x_{1}, \ldots, x_{k}) = n$ เป็นฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิม

  

  

  

  

• ฟังก์ชันสืบเนื่อง (Successor Function) $S$: ฟังก์ชัน 1-ary ที่คืนค่าตัวถัดไปของอาร์กิวเมนต์ ตามสัจพจน์ของเปอาโน (Peano postulates) คือ $S(x) = x + 1$ ซึ่งเป็นฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิม

  

• ฟังก์ชันโปรเจกชัน (Projection Functions) $P_{i}^{k}$: สำหรับจำนวนธรรมชาติ $i, k$ โดยที่ $1 \leq i \leq k$ ฟังก์ชัน $k$-ary ที่นิยามโดย $P_{i}^{k}(x_{1}, \ldots, x_{k}) = x_{i}$ เป็นฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิม

  

  

  

  

ตัวดำเนินการในการสร้างฟังก์ชันที่ซับซ้อนขึ้น

เราสามารถสร้างฟังก์ชันรีเคอร์ซีฟแบบดั้งเดิมที่ซับซ้อนขึ้นได้โดยใช้ตัวดำเนินการดังนี้:

• ตัวดำเนินการคอมโพสิชัน (Composition Operator $\circ$): หรือเรียกว่าตัวดำเนินการแทนที่ (Substitution Operator) หากมีฟังก์ชัน $m$-ary $h$ และฟังก์ชัน $k$-ary $g_{1}, \ldots, g_{m}$ ผลลัพธ์ที่ได้คือฟังก์ชัน $f$ โดยที่ $f(x_{1}, \ldots, x_{k}) = h(g_{1}(x_{1}, \ldots, x_{k}), \ldots, g_{m}(x_{1}, \ldots, x_{k}))$
• ตัวดำเนินการรีเคอร์ชันแบบดั้งเดิม (Primitive Recursion Operator $\rho$): หากมีฟังก์ชัน $k$-ary $g$ และฟังก์ชัน $(k+2)$-ary $h$ ผลลัพธ์ที่ได้คือฟังก์ชัน $(k+1)$-ary $f$ ซึ่งนิยามโดย: $f(0, x_{1}, \ldots, x_{k}) = g(x_{1}, \ldots, x_{k})$ และ $f(S(y'), x_{1}, \ldots, x_{k}) = h(y', f(y', x_{1}, \ldots, x_{k}), x_{1}, \ldots, x_{k})$

ในเชิงการตีความ ฟังก์ชัน $f$ จะทำงานเสมือนลูป for ที่เริ่มจาก 0 ไปจนถึงค่าของอาร์กิวเมนต์ตัวแรก โดยที่ $g$ ทำหน้าที่เป็นค่าเริ่มต้น และ $h$ ทำหน้าที่เป็นส่วนของเนื้อหาลูป (Loop Body) ที่คำนวณค่าในแต่ละรอบโดยใช้ผลลัพธ์จากรอบก่อนหน้า