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

ความสำคัญของฟังก์ชันเรียกซ้ำแบบดั้งเดิมอยู่ที่ข้อเท็จจริงที่ว่าฟังก์ชันที่คำนวณได้ ส่วนใหญ่ ที่ศึกษาในทฤษฎีจำนวน (และโดยทั่วไปในคณิตศาสตร์) เป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิม ตัวอย่างเช่นการบวกและการหารฟังก์ชันแฟกทอเรียลและฟังก์ชันเลขชี้กำลังและฟังก์ชันที่ส่งคืนจำนวนเฉพาะลำดับที่nล้วนเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิม^{[ 1 ]}ในความเป็นจริง การแสดงให้เห็นว่าฟังก์ชันที่คำนวณได้เป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมนั้นเพียงพอที่จะแสดงให้เห็นว่าความซับซ้อนของเวลา ของฟังก์ชันนั้น มีขอบเขตบนโดยฟังก์ชันเรียกซ้ำแบบดั้งเดิมที่มีขนาดเท่ากับอินพุต^{[ 2 ]}ดังนั้นจึงไม่ใช่เรื่องง่ายนักที่จะคิดค้นฟังก์ชันที่คำนวณได้ที่ไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม ตัวอย่างบางส่วนแสดงอยู่ในหัวข้อ§ ข้อจำกัดด้านล่าง

ในทฤษฎีความซับซ้อนของการคำนวณ กลุ่มของฟังก์ชันเรียกซ้ำแบบดั้งเดิมเรียกว่าPR ( Primitive Recursive Functions )

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

ฟังก์ชันเรียกซ้ำพื้นฐานดั้งเดิมนั้นกำหนดโดยสัจพจน์ เหล่านี้ :

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

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

ฟังก์ชัน (เวกเตอร์ค่า) ^{[ 5 ]} เรียกว่าฟังก์ชันเรียกซ้ำแบบดั้งเดิม หากสามารถเขียนได้ดังนี้ ${\displaystyle f:\mathbb {N} ^{m}\to \mathbb {N} ^{n}}$

${\displaystyle f(x_{1},\dots ,x_{m})=(f_{1}(x_{1},\dots ,x_{m}),\dots ,f_{n}(x_{1},\dots ,x_{m}))}$

โดยที่แต่ละส่วนประกอบเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิม (ค่าสเกลาร์) ^{[ 6 ]}${\displaystyle f_{i}:\mathbb {N} ^{m}\to \mathbb {N} }$

นิยามของฟังก์ชัน 2-ary ที่ใช้ในการคำนวณผลรวมของอาร์กิวเมนต์ สามารถหาได้โดยใช้ตัวดำเนินการเรียกซ้ำแบบดั้งเดิมเพื่อจุดประสงค์นี้ สมการที่รู้จักกันดี ${\displaystyle \operatorname {Add} }$${\displaystyle \rho }$

${\displaystyle {\begin{aligned}0+y&=y,\\S(x)+y&=S(x+y)\end{aligned}}}$

กล่าวคือ "ถูกเรียบเรียงใหม่ในแง่ของฟังก์ชันเรียกซ้ำแบบดั้งเดิม": ในนิยามของสมการแรกแนะนำให้เลือกเพื่อให้ได้; สมการที่สองแนะนำให้เลือกเพื่อให้ได้ดังนั้น ฟังก์ชันการบวกจึงสามารถนิยามได้เป็นตัวอย่างเช่น ในการคำนวณ ${\displaystyle \rho (g,h)}$${\displaystyle g=P_{1}^{1}}$${\displaystyle \operatorname {Add} (0,y)=g(y)=y}$${\displaystyle h=S\circ P_{2}^{3}}$${\displaystyle \operatorname {Add} (S(x),y)=h(x,\operatorname {Add} (x,y),y)=(S\circ P_{2}^{3})(x,\operatorname {Add} (x,y),y)=S(\operatorname {Add} (x,y))}$${\displaystyle \operatorname {Add} =\rho (P_{1}^{1},S\circ P_{2}^{3})}$

${\displaystyle {\begin{aligned}\operatorname {Add} (1,7)&=\rho (P_{1}^{1},S\circ P_{2}^{3})(S(0),7)&&{\text{ by Def. }}\operatorname {Add} ,S\\&=(S\circ P_{2}^{3})(0,\operatorname {Add} (0,7),7)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=S(\operatorname {Add} (0,7))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=S(\rho (P_{1}^{1},S\circ P_{2}^{3})(0,7))&&{\text{ by Def. }}\operatorname {Add} \\&=S(P_{1}^{1}(7))&&{\text{ by case }}\rho (g,h)(0,...)\\&=S(7)&&{\text{ by Def. }}P_{1}^{1}\\&=8&&{\text{ by Def. }}S.\\\end{aligned}}}$

กำหนดให้ฟังก์ชัน 1-ary จะเพิ่มค่าอาร์กิวเมนต์เป็นสองเท่า${\displaystyle \operatorname {Add} }$${\displaystyle \operatorname {Add} \circ (P_{1}^{1},P_{1}^{1})}$${\displaystyle (\operatorname {Add} \circ (P_{1}^{1},P_{1}^{1}))(x)=\operatorname {Add} (x,x)=x+x.}$

เช่นเดียวกับการบวก การคูณสามารถกำหนดได้ด้วยสูตรซึ่งจะทำให้ได้สมการการคูณที่เรารู้จักกันดี: ${\displaystyle \operatorname {Mul} =\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))}$

${\displaystyle {\begin{aligned}\operatorname {Mul} (0,y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(0,y)&&{\text{ by Def. }}\operatorname {Mul} \\&=C_{0}^{1}(y)&&{\text{ by case }}\rho (g,h)(0,...)\\&=0&&{\text{ by Def. }}C_{0}^{1}.\end{aligned}}}$

และ

${\displaystyle {\begin{aligned}\operatorname {Mul} (S(x),y)&=\rho (C_{0}^{1},\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(S(x),y)&&{\text{ by Def. }}\operatorname {Mul} \\&=(\operatorname {Add} \circ (P_{2}^{3},P_{3}^{3}))(x,\operatorname {Mul} (x,y),y)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Add} (\operatorname {Mul} (x,y),y)&&{\text{ by Def. }}\circ ,P_{2}^{3},P_{3}^{3}\\&=\operatorname {Mul} (x,y)+y&&{\text{ by property of }}\operatorname {Add} .\end{aligned}}}$

ฟังก์ชันก่อนหน้าทำหน้าที่เป็น "สิ่งที่ตรงกันข้าม" กับฟังก์ชันถัดไป และถูกกำหนดแบบเรียกซ้ำโดยกฎและนิยามแบบเรียกซ้ำพื้นฐานคือตัวอย่างการคำนวณ คือ${\displaystyle \operatorname {Pred} (0)=0}$${\displaystyle \operatorname {Pred} (S(n))=n}$${\displaystyle \operatorname {Pred} =\rho (C_{0}^{0},P_{1}^{2})}$

${\displaystyle {\begin{aligned}\operatorname {Pred} (8)&=\rho (C_{0}^{0},P_{1}^{2})(S(7))&&{\text{ by Def. }}\operatorname {Pred} ,S\\&=P_{1}^{2}(7,\operatorname {Pred} (7))&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=7&&{\text{ by Def. }}P_{1}^{2}.\end{aligned}}}$

ฟังก์ชันการลบแบบจำกัด (เรียกอีกอย่างว่า " monus " และใช้สัญลักษณ์ " ") สามารถกำหนดได้จากฟังก์ชันก่อนหน้า โดยเป็นไปตามสมการต่อไปนี้ ${\displaystyle \mathbin {\dot {-}} }$

${\displaystyle {\begin{aligned}y\mathbin {\dot {-}} 0&=y,\\y\mathbin {\dot {-}} S(x)&=\operatorname {Pred} (y\mathbin {\dot {-}} x).\end{aligned}}}$

เนื่องจากการเรียกซ้ำทำงานกับอาร์กิวเมนต์ตัวที่สอง เราจึงเริ่มต้นด้วยนิยามการเรียกซ้ำแบบดั้งเดิมของการลบแบบย้อนกลับ. จากนั้นการเรียกซ้ำจะทำงานบนอาร์กิวเมนต์ตัวแรก ดังนั้นนิยามการเรียกซ้ำแบบดั้งเดิมจึงสามารถหาได้เช่นเดียวกับการบวก คือ. เพื่อกำจัดลำดับอาร์กิวเมนต์ที่กลับด้าน ให้กำหนด. ตัวอย่างการคำนวณ ${\displaystyle \operatorname {RSub} (y,x)=x\mathbin {\dot {-}} y}$${\displaystyle \operatorname {RSub} =\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})}$${\displaystyle \operatorname {Sub} =\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2})}$

${\displaystyle {\begin{aligned}\operatorname {Sub} (8,1)&=(\operatorname {RSub} \circ (P_{2}^{2},P_{1}^{2}))(8,1)&&{\text{ by Def. }}\operatorname {Sub} \\&=\operatorname {RSub} (1,8)&&{\text{ by Def. }}\circ ,P_{2}^{2},P_{1}^{2}\\&=\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(S(0),8)&&{\text{ by Def. }}\operatorname {RSub} ,S\\&=(\operatorname {Pred} \circ P_{2}^{3})(0,\operatorname {RSub} (0,8),8)&&{\text{ by case }}\rho (g,h)(S(...),...)\\&=\operatorname {Pred} (\operatorname {RSub} (0,8))&&{\text{ by Def. }}\circ ,P_{2}^{3}\\&=\operatorname {Pred} (\rho (P_{1}^{1},\operatorname {Pred} \circ P_{2}^{3})(0,8))&&{\text{ by Def. }}\operatorname {RSub} \\&=\operatorname {Pred} (P_{1}^{1}(8))&&{\text{ by case }}\rho (g,h)(0,...)\\&=\operatorname {Pred} (8)&&{\text{ by Def. }}P_{1}^{1}\\&=7&&{\text{ by property of }}\operatorname {Pred} .\end{aligned}}}$

ในบางสถานการณ์ เป็นเรื่องปกติที่จะพิจารณาฟังก์ชันเรียกซ้ำแบบดั้งเดิมที่รับอินพุตเป็นทูเปิลที่ผสมตัวเลขกับค่าความจริง (นั่นคือสำหรับจริง และสำหรับเท็จ) หรือที่สร้างค่าความจริงเป็นเอาต์พุต^{[ 8 ]}สามารถทำได้โดยการระบุค่าความจริงกับตัวเลขในลักษณะที่กำหนดไว้ ตัวอย่างเช่น เป็นเรื่องปกติที่จะระบุค่าความจริงกับตัวเลขและค่าความจริงกับตัวเลขเมื่อทำการระบุนี้แล้วฟังก์ชันลักษณะเฉพาะของเซตซึ่งจะส่งคืนหรือ เสมอ สามารถมองได้ว่าเป็นตัวบ่งชี้ที่บอกว่าตัวเลขอยู่ในเซตหรือไม่การระบุตัวบ่งชี้กับฟังก์ชันตัวเลขดังกล่าวจะถือว่าใช้กันในส่วนที่เหลือของบทความนี้ ${\displaystyle t}$${\displaystyle f}$${\displaystyle t}$${\displaystyle 1}$${\displaystyle f}$${\displaystyle 0}$${\displaystyle A}$${\displaystyle 1}$${\displaystyle 0}$${\displaystyle A}$

ตัวอย่างเช่น สำหรับ述语แบบเรียกซ้ำพื้นฐาน ฟังก์ชัน 1-ary จะต้องถูกกำหนดให้เป็นเช่นนั้นถ้าและเป็นอย่างอื่น ซึ่งสามารถทำได้โดยการกำหนดจากนั้นและเช่น ${\displaystyle \operatorname {IsZero} }$${\displaystyle \operatorname {IsZero} (x)=1}$${\displaystyle x=0}$${\displaystyle \operatorname {IsZero} (x)=0}$${\displaystyle \operatorname {IsZero} =\rho (C_{1}^{0},C_{0}^{2})}$${\displaystyle \operatorname {IsZero} (0)=\rho (C_{1}^{0},C_{0}^{2})(0)=C_{1}^{0}()=1}$${\displaystyle \operatorname {IsZero} (8)=\rho (C_{1}^{0},C_{0}^{2})(S(7))=C_{0}^{2}(7,\operatorname {IsZero} (7))=0}$

โดยใช้คุณสมบัติดังกล่าว ฟังก์ชัน 2-ary สามารถกำหนดได้โดย จากนั้นถ้าและเป็นอย่างอื่น ตัวอย่างการคำนวณ ${\displaystyle x\leq y\iff x\mathbin {\dot {-}} y=0}$${\displaystyle \operatorname {Leq} }$${\displaystyle \operatorname {Leq} =\operatorname {IsZero} \circ \operatorname {Sub} }$${\displaystyle \operatorname {Leq} (x,y)=1}$${\displaystyle x\leq y}$${\displaystyle \operatorname {Leq} (x,y)=0}$

${\displaystyle {\begin{aligned}\operatorname {Leq} (8,3)&=\operatorname {IsZero} (\operatorname {Sub} (8,3))&&{\text{ by Def. }}\operatorname {Leq} \\&=\operatorname {IsZero} (5)&&{\text{ by property of }}\operatorname {Sub} \\&=0&&{\text{ by property of }}\operatorname {IsZero} \\\end{aligned}}}$

เมื่อได้นิยามของ แล้ว สามารถกำหนด述语 (preverse predicate) ได้เป็นดังนั้นจะเป็นจริง (หรือกล่าวให้แม่นยำยิ่งขึ้นคือ มีค่าเท่ากับ 1) ก็ต่อเมื่อ ${\displaystyle \operatorname {Leq} }$${\displaystyle \operatorname {Geq} =\operatorname {Leq} \circ (P_{2}^{2},P_{1}^{2})}$${\displaystyle \operatorname {Geq} (x,y)=\operatorname {Leq} (y,x)}$${\displaystyle x\geq y}$

ตัวดำเนินการ if-then-else แบบ 3 ตัวแปร ซึ่งเป็นที่รู้จักในภาษาโปรแกรม สามารถกำหนดได้โดย. จากนั้น สำหรับค่า ใดๆก็ตาม ${\displaystyle \operatorname {If} =\rho (P_{2}^{2},P_{3}^{4})}$${\displaystyle x}$

${\displaystyle {\begin{aligned}\operatorname {If} (S(x),y,z)&=\rho (P_{2}^{2},P_{3}^{4})(S(x),y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{3}^{4}(x,\operatorname {If} (x,y,z),y,z)&&{\text{ by case }}\rho (S(...),...)\\&=y&&{\text{ by Def. }}P_{3}^{4}\end{aligned}}}$

และ

${\displaystyle {\begin{aligned}\operatorname {If} (0,y,z)&=\rho (P_{2}^{2},P_{3}^{4})(0,y,z)&&{\text{ by Def. }}\operatorname {If} \\&=P_{2}^{2}(y,z)&&{\text{ by case }}\rho (0,...)\\&=z&&{\text{ by Def. }}P_{2}^{2}.\end{aligned}}}$

กล่าวคือจะคืนค่า then-part ( ) หาก if-part ( ) เป็นจริง และคืนค่า else-part ( ) ในกรณีอื่น ๆ ${\displaystyle \operatorname {If} (x,y,z)}$${\displaystyle y}$${\displaystyle x}$${\displaystyle z}$

โดยอาศัยฟังก์ชันดังกล่าว เราสามารถกำหนดตัวเชื่อมตรรกะได้อย่างง่ายดาย ตัวอย่างเช่น การกำหนด จะได้นั่นคือเป็นจริงก็ต่อเมื่อและ เป็นจริง ทั้งคู่( การเชื่อมตรรกะของและ) ${\displaystyle \operatorname {If} }$${\displaystyle \operatorname {And} =\operatorname {If} \circ (P_{1}^{2},P_{2}^{2},C_{0}^{2})}$${\displaystyle \operatorname {And} (x,y)=\operatorname {If} (x,y,0)}$${\displaystyle \operatorname {And} (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

ในทำนองเดียวกันและนำไปสู่คำจำกัดความที่เหมาะสมของการเชื่อมแบบ "หรือ " และการปฏิเสธ : และ${\displaystyle \operatorname {Or} =\operatorname {If} \circ (P_{1}^{2},C_{1}^{2},P_{2}^{2})}$${\displaystyle \operatorname {Not} =\operatorname {If} \circ (P_{1}^{1},C_{0}^{1},C_{1}^{1})}$${\displaystyle \operatorname {Or} (x,y)=\operatorname {If} (x,1,y)}$${\displaystyle \operatorname {Not} (x)=\operatorname {If} (x,0,1)}$

โดยใช้ฟังก์ชันข้างต้น, และนิยามนี้ จะใช้ในการ ตรวจ สอบความเท่าเทียมกัน ที่จริงแล้วจะเป็นจริงก็ต่อเมื่อเท่ากับ${\displaystyle \operatorname {Leq} }$${\displaystyle \operatorname {Geq} }$${\displaystyle \operatorname {And} }$${\displaystyle \operatorname {Eq} =\operatorname {And} \circ (\operatorname {Leq} ,\operatorname {Geq} )}$${\displaystyle \operatorname {Eq} (x,y)=\operatorname {And} (\operatorname {Leq} (x,y),\operatorname {Geq} (x,y))}$${\displaystyle x}$${\displaystyle y}$

ในทำนองเดียวกัน นิยามนี้ใช้หลักการแสดงเงื่อนไข "น้อยกว่า" และใช้หลักการแสดงเงื่อนไข "มากกว่า" ${\displaystyle \operatorname {Lt} =\operatorname {Not} \circ \operatorname {Geq} }$${\displaystyle \operatorname {Gt} =\operatorname {Not} \circ \operatorname {Leq} }$

การยกกำลังและการทดสอบความเป็นจำนวนเฉพาะเป็นการเรียกซ้ำแบบดั้งเดิม เมื่อกำหนดฟังก์ชันเรียกซ้ำแบบดั้งเดิม, , , และฟังก์ชันที่ส่งคืนค่าของเมื่อและค่าของในกรณีอื่น ๆ จะเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิม ${\displaystyle e}$${\displaystyle f}$${\displaystyle g}$${\displaystyle h}$${\displaystyle g}$${\displaystyle e\leq f}$${\displaystyle h}$

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

ตัวอย่างและคำจำกัดความต่อไปนี้มาจากKleene 1974หน้า 222–231 หลายตัวอย่างปรากฏพร้อมกับการพิสูจน์ ส่วนใหญ่ยังปรากฏในชื่อที่คล้ายกัน ไม่ว่าจะเป็นการพิสูจน์หรือเป็นตัวอย่าง ในBoolos, Burgess & Jeffrey 2002หน้า 63–70 พวกเขาเพิ่มลอการิทึม lo(x, y) หรือ lg(x, y) ขึ้นอยู่กับการพิสูจน์ที่แน่นอน

ต่อไปนี้ เครื่องหมาย " ' " เช่น a' เป็นเครื่องหมายดั้งเดิมที่มีความหมายว่า "ผู้สืบทอดของ" ซึ่งโดยทั่วไปมักคิดว่าเป็น " +1" เช่น a +1 = _def a' ฟังก์ชัน 16–20 และ #G มีความน่าสนใจเป็นพิเศษในแง่ของการแปลง述语แบบเรียกซ้ำดั้งเดิมไปเป็น และแยก述语เหล่านั้นออกจากรูปแบบ "ทางคณิตศาสตร์" ที่แสดงเป็นจำนวนเกอเดล

1. การบวก: a+b
2. การคูณ: a×b
3. การยกกำลัง: a ^b
4. แฟกทอเรียล a! : 0! = 1, a'! = a!×a'
5. pred(a): (ตัวก่อนหน้าหรือการลดค่า): ถ้า a > 0 แล้ว a−1 มิฉะนั้น 0
6. การลบที่ถูกต้อง a ∸ b: ถ้า a ≥ b แล้ว a−b มิฉะนั้น 0
7. ขั้นต่ำ(a ₁ , ... a _n )
8. ค่าสูงสุด(a ₁ , ... a _n )
9. ผลต่างสัมบูรณ์: | a−b | = _def (a ∸ b) + (b ∸ a)
10. ~sg(a): NOT[signum(a)]: ถ้า a=0 แล้ว 1 มิฉะนั้น 0
11. sg(a): signum(a): ถ้า a=0 แล้ว 0 มิฉะนั้น 1
12. a | b: (a หาร b ลงตัว): ถ้า b=k×a สำหรับ k บางค่า แล้ว 0 มิฉะนั้น 1
13. เศษเหลือ (a, b): ตัวเลขที่เหลือหาก b หาร a ไม่ลงตัว เรียกอีกอย่างว่า MOD(a, b)
14. a = b: sg | a − b | (ตามธรรมเนียมของคลีนน์ จะใช้ 0 แทน ค่าจริงและ1 แทนค่าเท็จ ปัจจุบัน โดยเฉพาะในคอมพิวเตอร์ ธรรมเนียมที่ใช้กันทั่วไปคือแบบกลับกัน คือใช้ 1 แทนค่า จริงและ 0 แทน ค่าเท็จซึ่งเท่ากับเปลี่ยน sg เป็น ~sg ในที่นี้และในข้อถัดไป)
15. a < b: sg( a' ∸ b )
16. Pr(a): a เป็นจำนวนเฉพาะ Pr(a) = _def a>1 & NOT(มีอยู่ c) _1<c<a [ c|a ]
17. pi _:จำนวนเฉพาะลำดับที่ i+1
18. (a) _i : เลขชี้กำลังของ p _iใน a: x ที่ไม่ซ้ำกันซึ่ง p _i ^x |a & NOT(p _i ^x' |a)
19. lh(a): "ความยาว" หรือจำนวนของเลขชี้กำลังที่ไม่เป็นศูนย์ใน a
20. lo(a, b): (ลอการิทึมของ a ฐาน b): ถ้า a, b > 1 แล้ว x ที่มากที่สุดที่ทำให้ b ^x | a มิฉะนั้น 0

ต่อไปนี้ ตัวย่อx = _def x ₁ , ... x _n ; อาจมีการใช้ตัวห้อยหากความหมายต้องการ

• #A: ฟังก์ชัน φ ที่สามารถนิยามได้อย่างชัดเจนจากฟังก์ชัน Ψ และค่าคงที่ q ₁ , ... q _nเรียกว่าฟังก์ชันเรียกซ้ำแบบดั้งเดิมใน Ψ
• #B: ผลรวมอันจำกัด Σ _y<z ψ( x , y) และผลิตภัณฑ์ Π _y<z ψ( x , y) เป็นการเรียกซ้ำแบบดั้งเดิมใน ψ
• #C:述语P ที่ได้จากการแทนที่ฟังก์ชัน χ ₁ ,..., χ _mด้วยตัวแปรตามลำดับของ述语 Q นั้นเป็น 述语แบบเรียกซ้ำดั้งเดิมใน χ ₁ ,..., χ _m , Q
• #D:述语ต่อไปนี้ เป็น述语แบบเรียกซ้ำพื้นฐานใน Q และ R:

• NOT_Q( x ) .
• Q หรือ R: Q( x ) VR( x ),
• Q และ R: Q( x ) & R( x ),
• Q บ่งชี้ R: Q( x ) → R( x )
• Q เทียบเท่ากับ R: Q( x ) ≡ R( x )

• #E:述语ต่อไปนี้ เป็น述语แบบเรียกซ้ำพื้นฐานใน述语R:

• (Ey) _y<z R( x , y) โดยที่ (Ey) _y<zหมายถึง "มี y อย่างน้อยหนึ่งตัวที่น้อยกว่า z ซึ่งทำให้"
• (y) _y<z R( x , y) โดยที่ (y) _y<zหมายถึง "สำหรับทุก y ที่น้อยกว่า z จะเป็นจริงว่า"
• μy _y<z R( x , y) คือตัวดำเนินการ μy _y<z R( x , y) ซึ่งเป็น รูปแบบ ที่มีขอบเขตของตัวดำเนินการหาค่าต่ำสุดหรือตัวดำเนินการมิว ( mu-operator ) โดยนิยามว่า "ค่าต่ำสุดของ y ที่น้อยกว่า z ซึ่งทำให้ R( x , y) เป็นจริง หรือ z หากไม่มีค่าดังกล่าว"

• #F: นิยามตามกรณี: ฟังก์ชันที่นิยามไว้ดังนี้ โดยที่ Q ₁ , ..., Q _mเป็นเงื่อนไข ที่แยกจากกันโดยสิ้นเชิง (หรือ "ψ( x ) จะมีค่าตามที่กำหนดโดยเงื่อนไขแรกที่ใช้ได้") เป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมใน φ ₁ , ..., Q ₁ , ... Q _m :

φ( x ) =

• φ ₁ ( x ) ถ้า Q ₁ ( x ) เป็นจริง
• . . . . . . . . . . . . . . . . . . .
• φ _m ( x ) ถ้า Q _m ( x ) เป็นจริง
• φ _m+1 ( x ) มิฉะนั้น

• #G: ถ้า φ สอดคล้องกับสมการ:

ถ้า φ(y, x ) = χ(y, COURSE-φ(y; x ₂ , ... x _n ), x ₂ , ... x _nแล้ว φ จะเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมใน χ ค่า COURSE-φ(y; x _{2 ถึง n} ) ของฟังก์ชันลำดับค่าจะเข้ารหัสลำดับค่า φ(0, x _{2 ถึง n} ), ..., φ(y-1, x _{2 ถึง n} ) ของฟังก์ชันดั้งเดิม

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

ฟังก์ชันเรียกซ้ำแบบดั้งเดิมทุกฟังก์ชันเป็นฟังก์ชันเรียกซ้ำแบบสมบูรณ์ แต่ฟังก์ชันเรียกซ้ำแบบสมบูรณ์ทั้งหมดไม่จำเป็นต้องเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมเสมอไปฟังก์ชัน Ackermann A ( m , n ) เป็นตัวอย่างที่รู้จักกันดีของฟังก์ชันเรียกซ้ำแบบสมบูรณ์ (อันที่จริงคือฟังก์ชันสมบูรณ์ที่พิสูจน์ได้) ซึ่งไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม มีการกำหนดลักษณะของฟังก์ชันเรียกซ้ำแบบดั้งเดิมเป็นเซตย่อยของฟังก์ชันเรียกซ้ำแบบสมบูรณ์โดยใช้ฟังก์ชัน Ackermann การกำหนดลักษณะนี้ระบุว่าฟังก์ชันเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมก็ต่อเมื่อมีจำนวนธรรมชาติmที่ทำให้สามารถคำนวณฟังก์ชันได้โดยเครื่องจักร Turing ที่หยุดทำงาน ภายใน A( m , n ) หรือน้อยกว่าขั้นตอนเสมอ โดยที่ nคือผลรวมของอาร์กิวเมนต์ของฟังก์ชันเรียกซ้ำแบบดั้งเดิม^{[ 9 ]}

คุณสมบัติสำคัญอย่างหนึ่งของฟังก์ชันเรียกซ้ำแบบดั้งเดิมคือ ฟังก์ชันเหล่านี้เป็น เซตย่อย ที่สามารถแจงนับได้แบบเรียกซ้ำของเซตของฟังก์ชันเรียกซ้ำ ทั้งหมด (ซึ่งตัวมันเองไม่สามารถแจงนับได้แบบเรียกซ้ำ) หมายความว่ามีฟังก์ชันเรียกซ้ำเพียงฟังก์ชันเดียวf ( m , n ) ที่แจงนับฟังก์ชันเรียกซ้ำแบบดั้งเดิม ได้แก่:

• สำหรับฟังก์ชันเรียกซ้ำแบบดั้งเดิมเอกภาคg ทุกฟังก์ชัน จะมีmที่ทำให้g ( n ) = f ( m , n ) สำหรับทุกnและ
• สำหรับทุกค่าmฟังก์ชันh ( n ) = f ( m , n ) เป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิม
• ฟังก์ชันเรียกซ้ำแบบดั้งเดิมที่มีอาร์กิวเมนต์สองตัวขึ้นไปสามารถเข้ารหัสเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมแบบเอกภาคได้โดยใช้ฟังก์ชันจับคู่ เรียกซ้ำแบบดั้งเดิม ที่มีตัวผกผันเรียกซ้ำแบบดั้งเดิมสองตัว

ฟังก์ชัน fสามารถสร้างขึ้นได้อย่างชัดเจนโดยการทำซ้ำวิธีการสร้างฟังก์ชันเรียกซ้ำแบบดั้งเดิมที่เป็นไปได้ทั้งหมด ดังนั้นจึงพิสูจน์ได้ว่าเป็นฟังก์ชันสมบูรณ์ เราสามารถใช้ การหา ค่าเฉพาะเพื่อแสดงว่าfไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิมในตัวมันเอง: หากเป็นเช่นนั้นh ( n ) = f ( n , n )+1 ก็จะเป็นเช่นนั้นด้วย แต่ถ้าสิ่งนี้เท่ากับฟังก์ชันเรียกซ้ำแบบดั้งเดิมบางฟังก์ชัน จะมีmที่ทำให้h ( n ) = f ( m , n ) สำหรับทุกnและจากนั้นh ( m ) = f ( m , m ) ซึ่งนำไปสู่ข้อขัดแย้ง

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

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

ฟังก์ชันเรียกซ้ำแบบดั้งเดิมที่มีอาร์กิวเมนต์เดียว (เช่น ฟังก์ชันเอกภาค) สามารถแจงนับได้ด้วยวิธีการคำนวณ การแจงนับนี้ใช้คำจำกัดความของฟังก์ชันเรียกซ้ำแบบดั้งเดิม (ซึ่งโดยพื้นฐานแล้วเป็นเพียงนิพจน์ที่มีการประกอบและการดำเนินการเรียกซ้ำแบบดั้งเดิมเป็นตัวดำเนินการ และฟังก์ชันเรียกซ้ำแบบดั้งเดิมพื้นฐานเป็นอะตอม) และสามารถสันนิษฐานได้ว่ามีคำจำกัดความทุกคำเพียงครั้งเดียว แม้ว่าฟังก์ชัน เดียวกัน จะปรากฏหลายครั้งในรายการ (เนื่องจากคำจำกัดความจำนวนมากกำหนดฟังก์ชันเดียวกัน อันที่จริง การประกอบโดยใช้ฟังก์ชันเอกลักษณ์จะสร้างคำจำกัดความของฟังก์ชันเรียกซ้ำแบบดั้งเดิมใดๆ ได้เป็นอนันต์) ซึ่งหมายความว่าคำจำกัดความที่ i ของฟังก์ชันเรียกซ้ำแบบดั้งเดิมในการแจงนับนี้สามารถกำหนดได้อย่างมีประสิทธิภาพจากอันที่จริง หากใช้การกำหนดหมายเลขของ Gödelเพื่อเข้ารหัสคำจำกัดความเป็นตัวเลขคำจำกัดความที่ i ในรายการนี้จะคำนวณได้จากฟังก์ชันเรียกซ้ำแบบดั้งเดิมของให้แทนฟังก์ชันเรียกซ้ำแบบดั้งเดิมเอกภาคที่กำหนดโดยคำจำกัดความนี้ ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle f_{n}}$

ตอนนี้ให้กำหนด "ฟังก์ชันประเมินผล" ที่มีอาร์กิวเมนต์สองตัว โดยใช้. เห็นได้ชัดว่าเป็นฟังก์ชันสมบูรณ์และคำนวณได้ เนื่องจากเราสามารถกำหนดนิยามของ ได้อย่างมีประสิทธิภาพและเนื่องจากเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมจึงเป็นฟังก์ชันสมบูรณ์และคำนวณได้ ดังนั้น จึงถูกกำหนดและคำนวณได้อย่างมีประสิทธิภาพเสมอ อย่างไรก็ตาม อาร์กิวเมนต์แนวทแยงจะแสดงให้เห็นว่าฟังก์ชันที่มีอาร์กิวเมนต์สองตัวนั้นไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม ${\displaystyle ev}$${\displaystyle ev(i,j)=f_{i}(j)}$${\displaystyle ev}$${\displaystyle f_{i}}$${\displaystyle f_{i}}$${\displaystyle f_{i}(j)}$${\displaystyle ev}$

สมมติว่าเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิม ฟังก์ชันเอกภาคที่กำหนดโดยก็จะเป็นฟังก์ชันเรียกซ้ำแบบดั้งเดิมเช่นกัน เนื่องจากถูกกำหนดโดยการประกอบจากฟังก์ชันตัวสืบทอดและแต่ปรากฏอยู่ในลำดับการแจงนับ ดังนั้นจึงมีจำนวนบางจำนวนที่แต่ตอนนี้กลับเกิดข้อขัดแย้ง${\displaystyle ev}$${\displaystyle g}$${\displaystyle g(i)=S(ev(i,i))}$${\displaystyle ev}$${\displaystyle g}$${\displaystyle n}$${\displaystyle g=f_{n}}$${\displaystyle g(n)=S(ev(n,n))=S(f_{n}(n))=S(g(n))}$

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

นอกจากนี้ ยังมีตัวอย่างอื่นๆ ของฟังก์ชันเรียกซ้ำโดยสมบูรณ์แต่ไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม ดังนี้:

• ฟังก์ชันที่รับค่าmไปยังAckermann ( m , m ) เป็นฟังก์ชันเรียกซ้ำแบบสมบูรณ์เอกภาคที่ไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม
• ทฤษฎีบท ปารีส-แฮร์ริงตันเกี่ยวข้องกับฟังก์ชันเรียกซ้ำทั้งหมดที่ไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม
• หน้าที่ของ ซูดาน
• ฟังก์ชันกูดสไตน์

แทนที่จะใช้ คำจำกัดความแบบเดิม จะใช้ ฟังก์ชันศูนย์แบบ 0-ary เพียงฟังก์ชันเดียวเป็นฟังก์ชันพื้นฐานที่ส่งค่ากลับเป็นศูนย์เสมอ และสร้างฟังก์ชันคงที่จากฟังก์ชันศูนย์ ฟังก์ชันตัวสืบทอด และตัวดำเนินการประกอบ ${\displaystyle C_{n}^{k}}$${\displaystyle C_{0}^{0}}$

Robinson ^{[ 10 ]} พิจารณาข้อจำกัดต่างๆ ของกฎการเรียกซ้ำ หนึ่งในนั้นคือ กฎการวนซ้ำที่เรียกว่าซึ่งฟังก์ชันhไม่สามารถเข้าถึงพารามิเตอร์x _iได้ (ในกรณีนี้ เราอาจสมมติโดยไม่เสียความเป็นทั่วไปว่าฟังก์ชันgเป็นเพียงเอกลักษณ์ เนื่องจากกรณีทั่วไปสามารถหาได้โดยการแทนที่):

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(y,f(y,x)).\end{aligned}}}$

เขาพิสูจน์แล้วว่าคลาสของฟังก์ชันเรียกซ้ำแบบดั้งเดิมทั้งหมดสามารถหาได้ด้วยวิธีนี้

^{ข้อจำกัดอีกประการหนึ่งที่ Robinson [ 10 ]}พิจารณาคือการเรียกซ้ำแบบบริสุทธิ์โดยที่hไม่สามารถเข้าถึงตัวแปรเหนี่ยวนำy ได้ :

${\displaystyle {\begin{aligned}f(0,x_{1},\ldots ,x_{k})&=g(x_{1},\ldots ,x_{k}),\\f(S(y),x_{1},\ldots ,x_{k})&=h(f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k}).\end{aligned}}}$

Gladstone ^{[ 11 ]}พิสูจน์แล้วว่ากฎนี้เพียงพอที่จะสร้างฟังก์ชันเรียกซ้ำแบบดั้งเดิมทั้งหมด Gladstone ^{[ 12 ]}ปรับปรุงสิ่งนี้เพื่อให้แม้แต่การรวมกันของข้อจำกัดทั้งสองนี้ กล่าวคือ กฎ การวนซ้ำบริสุทธิ์ด้านล่าง ก็เพียงพอแล้ว:

${\displaystyle {\begin{aligned}f(0,x)&=x,\\f(S(y),x)&=h(f(y,x)).\end{aligned}}}$

การปรับปรุงเพิ่มเติมเป็นไปได้: Severin ^{[ 13 ]}พิสูจน์ว่าแม้แต่กฎการวนซ้ำบริสุทธิ์ที่ไม่มีพารามิเตอร์กล่าวคือ

${\displaystyle {\begin{aligned}f(0)&=0,\\f(S(y))&=h(f(y)),\end{aligned}}}$

เพียงพอที่จะสร้าง ฟังก์ชันเรียกซ้ำแบบเอก ภาค ทั้งหมดได้ หากเราขยายเซตของฟังก์ชันเริ่มต้นด้วยการลบแบบตัดทอนx ∸ yเราจะได้ ฟังก์ชันเรียกซ้ำแบบปฐมภูมิ ทั้งหมดหากเราเพิ่ม + เป็นฟังก์ชันเริ่มต้นเพิ่มเติม

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

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

ตัวอย่างของภาษาโปรแกรมแบบเรียกซ้ำขั้นพื้นฐาน คือ ภาษาที่มีตัวดำเนินการทางคณิตศาสตร์พื้นฐาน (เช่น + และ − หรือการบวกและการลบ) เงื่อนไขและการเปรียบเทียบ (ถ้า-แล้ว, เท่ากับ, น้อยกว่า) และลูปที่มีขอบเขต เช่นลูป for พื้นฐาน ซึ่งมีขอบเขตบนที่ทราบหรือคำนวณได้สำหรับลูปทั้งหมด (FOR i FROM 1 TO n โดยที่ i และ n ไม่สามารถเปลี่ยนแปลงได้โดยตัวลูป) ภาษาโปรแกรมแบบเรียกซ้ำขั้นพื้นฐานไม่อนุญาตให้ใช้ โครงสร้างควบคุมที่มีความทั่วไปมากกว่า เช่นลูป whileหรือ IF-THEN บวกGOTO

ภาษาLOOPซึ่งนำเสนอในบทความปี 1967 โดยAlbert R. MeyerและDennis M. Ritchie [ ^{14 ] เป็น}ภาษาดังกล่าว พลังการคำนวณของมันสอดคล้องกับฟังก์ชันเรียกซ้ำแบบดั้งเดิม รูปแบบหนึ่งของภาษา LOOP คือBlooPของDouglas HofstadterในGödel, Escher, Bachการเพิ่มลูปที่ไม่จำกัด (WHILE, GOTO) ทำให้ภาษานี้เป็นภาษาเรียกซ้ำทั่วไปและสมบูรณ์แบบทัวริงเช่นเดียวกับภาษาการเขียนโปรแกรมคอมพิวเตอร์ในโลกแห่งความเป็นจริงทั้งหมด

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

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

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

ถ้าTเป็นทฤษฎีเลขคณิตที่สอดคล้องกับสมมติฐานบางประการ โดยมีประโยค Gödel G _Tแล้ว PRA จะพิสูจน์การบ่งชี้ Con( T )→ G _Tได้

ในทำนองเดียวกัน ผลลัพธ์ทางไวยากรณ์จำนวนมากในทฤษฎีการพิสูจน์สามารถพิสูจน์ได้ใน PRA ซึ่งหมายความว่ามีฟังก์ชันเรียกซ้ำแบบดั้งเดิมที่ดำเนินการแปลงทางไวยากรณ์ที่สอดคล้องกันของการพิสูจน์

ในทฤษฎีการพิสูจน์และทฤษฎีเซตมีความสนใจในการพิสูจน์ความสอดคล้องแบบจำกัด (finitistic consistency proofs) กล่าวคือ การพิสูจน์ความสอดคล้องที่ตัวมันเองยอมรับได้ในเชิงจำกัด การพิสูจน์ดังกล่าวแสดงให้เห็นว่าความสอดคล้องของทฤษฎีTบ่งชี้ถึงความสอดคล้องของทฤษฎีSโดยการสร้างฟังก์ชันเวียนเกิดแบบดั้งเดิม (primitive recursive function) ที่สามารถแปลงการพิสูจน์ความไม่สอดคล้องใดๆ จากSไปเป็นการพิสูจน์ความไม่สอดคล้องจากTได้ เงื่อนไขที่เพียงพอประการหนึ่งสำหรับการพิสูจน์ความสอดคล้องที่จะเป็นแบบจำกัดคือ ความสามารถในการทำให้เป็นทางการใน PRA ตัวอย่างเช่น ผลลัพธ์ความสอดคล้องจำนวนมากในทฤษฎีเซตที่ได้มาจากการบังคับ (forcing)สามารถแปลงใหม่เป็นการพิสูจน์เชิงไวยากรณ์ที่สามารถทำให้เป็นทางการใน PRA ได้

นิยามแบบเรียกซ้ำได้ถูกนำมาใช้ในทางคณิตศาสตร์อย่างเป็นทางการมาก่อนแล้ว แต่การสร้างการเรียกซ้ำแบบดั้งเดิมนั้นสืบย้อนไปถึงทฤษฎีบทที่ 126 ของRichard Dedekind ในหนังสือ Was sind und was sollen die Zahlen? (1888) งานชิ้นนี้เป็นงานแรกที่พิสูจน์ว่าการสร้างแบบเรียกซ้ำบางอย่างกำหนดฟังก์ชันที่ไม่ซ้ำกัน^{[ 15 ] [ 16 ] [ 17 ]}

เลขคณิตแบบเรียกซ้ำดั้งเดิม ได้รับการเสนอครั้งแรกโดยThoralf Skolem ^{[ 18 ]}ในปี พ.ศ. 2466

คำศัพท์ปัจจุบันถูกบัญญัติโดยRózsa Péter (1934) หลังจากที่Ackermannได้พิสูจน์ในปี 1928 ว่าฟังก์ชันที่ปัจจุบันตั้งชื่อตามเขานั้นไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิม ซึ่งเป็นเหตุการณ์ที่กระตุ้นให้เกิดความจำเป็นในการเปลี่ยนชื่อสิ่งที่ก่อนหน้านี้เรียกว่าฟังก์ชันเรียกซ้ำ^{[ 16 ] [ 17 ]}

• ลำดับชั้นของ Grzegorczyk
• การเรียกซ้ำ (วิทยาการคอมพิวเตอร์)
• ฟังก์ชันเรียกซ้ำแบบดั้งเดิม
• การเรียกซ้ำสองครั้ง
• ฟังก์ชันเซตแบบเรียกซ้ำดั้งเดิม
• ฟังก์ชันเชิงลำดับแบบเรียกซ้ำดั้งเดิม
• เสียงเรียกหาง