คำว่า"พื้นฐาน"เดิมทีได้รับการแนะนำโดยLászló Kalmárในบริบทของทฤษฎีความสามารถในการคำนวณ [ ^{1 ] [ 2 ] เขา}ได้กำหนดคลาสของฟังก์ชันเรียกซ้ำพื้นฐาน ( "ฟังก์ชันพื้นฐานของ Kalmár" ) ว่าเป็นเซตย่อยของฟังก์ชันเรียกซ้ำแบบดั้งเดิม — โดยเฉพาะอย่างยิ่ง ฟังก์ชันที่สามารถคำนวณได้โดยใช้ชุดการดำเนินการที่จำกัด เช่น การประกอบ การบวกแบบมีขอบเขต และการคูณแบบมีขอบเขต^{[ 3 ]}ฟังก์ชันเหล่านี้เติบโตไม่เร็วกว่าหอคอยยกกำลังที่ มีความสูงคงที่ (ตัวอย่างเช่น) ไม่ใช่ฟังก์ชันเรียกซ้ำแบบดั้งเดิมทั้งหมดที่เป็นพื้นฐาน ตัวอย่างเช่นtetrationเติบโตเร็วเกินไปที่จะรวมอยู่ในคลาสพื้นฐาน ฟังก์ชันเรียกซ้ำพื้นฐานสอดคล้องกับคลาสของ ลำดับ ชั้นGrzegorczyk ^{[ 4 ]}${\displaystyle O(2^{2^{n}})}$${\displaystyle {\mathcal {E}}^{3}}$

ในทฤษฎีความซับซ้อนของการคำนวณคำว่าELEMENTARYหมายถึงกลุ่มของปัญหาการตัดสินใจที่สามารถแก้ไขได้ในเวลาแบบ elementary time — กล่าวคือ ภายในเวลาที่ถูกจำกัดด้วยจำนวนเลขชี้กำลังคงที่จำนวนหนึ่ง เขียนอย่างเป็นทางการได้ดังนี้:

${\displaystyle {\mathsf {ELEMENTARY}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}(\exp ^{k}(n^{c}))}$

โดยที่หมายถึง หอคอยเลขชี้กำลัง kระดับ (เช่น)${\displaystyle \exp ^{k}(n)}$${\displaystyle 2^{2^{\cdot ^{\cdot ^{n}}}}}$

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

นิยามของฟังก์ชันเรียกซ้ำพื้นฐานนั้นเหมือนกับนิยามของฟังก์ชันเรียกซ้ำแบบดั้งเดิมยกเว้นว่าการเรียกซ้ำแบบดั้งเดิมจะถูกแทนที่ด้วยผลรวมที่มีขอบเขตและผลคูณที่มีขอบเขต^{[ 1 ] [ 3 ] [ 5 ]}ฟังก์ชันทั้งหมดทำงานบนจำนวนธรรมชาติฟังก์ชันพื้นฐานทั้งหมดเป็นฟังก์ชันเรียกซ้ำพื้นฐาน ได้แก่:

1. ฟังก์ชันศูนย์ส่งคืนค่าศูนย์: .${\displaystyle f(x)=0}$
2. ฟังก์ชันตัวสืบทอด : . โดยทั่วไปจะใช้สัญลักษณ์เช่น. โดยการใช้ฟังก์ชันตัวสืบทอดซ้ำๆ เราสามารถทำการบวกได้${\displaystyle f(x)=x+1}$${\displaystyle S}$${\displaystyle S(x)}$
3. ฟังก์ชันการฉายภาพ : ฟังก์ชันเหล่านี้ใช้สำหรับละเว้นอาร์กิวเมนต์ ตัวอย่างเช่นเป็นฟังก์ชันการฉายภาพ${\displaystyle f(a,b)=a}$
4. ฟังก์ชันการลบ : ฟังก์ชันนี้ใช้สำหรับกำหนดเงื่อนไขและการวนซ้ำ${\displaystyle f(x,y)=\max(x-y,0)}$

จากฟังก์ชันพื้นฐานเหล่านี้ เราสามารถสร้างฟังก์ชันเรียกซ้ำพื้นฐานอื่นๆ ได้

1. การประกอบฟังก์ชัน (Composition) : การนำค่าจากฟังก์ชันเรียกซ้ำพื้นฐานฟังก์ชันหนึ่งไปใช้เป็นอาร์กิวเมนต์ในฟังก์ชันเรียกซ้ำพื้นฐานอีกฟังก์ชันหนึ่ง ฟังก์ชันที่กำหนดเป็นการประกอบฟังก์ชัน นั้น จะเป็นฟังก์ชันเรียกซ้ำพื้นฐานก็ต่อเมื่อ ฟังก์ชัน นั้นเป็นฟังก์ชันเรียกซ้ำพื้นฐาน และแต่ละฟังก์ชันก็เป็นฟังก์ชันเรียกซ้ำพื้นฐานเช่น กัน${\displaystyle f}$${\displaystyle f(x_{1},\ldots ,x_{n})=h{\bigl (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}){\bigr )}}$${\displaystyle h}$${\displaystyle g_{i}}$
2. การหาผลรวมแบบมีขอบเขต : เป็นการเรียกซ้ำแบบพื้นฐาน ถ้าเป็นการเรียกซ้ำแบบพื้นฐาน${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$${\displaystyle g}$
3. ผลคูณแบบมีขอบเขต : เป็นแบบเรียกซ้ำพื้นฐาน ถ้าเป็นแบบเรียกซ้ำพื้นฐาน${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}$${\displaystyle g}$

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

กล่าวอย่างเป็นทางการมากขึ้น สมมติว่า:

• ${\displaystyle f(x_{1},\dots ,x_{k})}$เป็นฟังก์ชันแบบ -ary และ${\displaystyle k}$
• ${\displaystyle g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n})}$เป็นฟังก์ชัน -ary${\displaystyle n}$

จากนั้น การซ้อนทับของฟังก์ชันเหล่านี้จะให้ฟังก์ชัน -ary ใหม่: ${\displaystyle n}$

${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n}))}$.

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

• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$^{[ 6 ]}
• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;nm,\;n^{m}\}}$^{[ 7 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;n^{2},\;2^{n}\}}$^{[ 8 ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;2^{n}\}}$^{[ 9 ]}

โดยที่หมายถึงการลบแบบตัดทอน ( monus ) ${\displaystyle n\mathbin {\dot {-}} m=\max(n-m,0)}$

ในปี 2025 Mihai Prunescu, Lorenzo Sauras-Altuzarra และ Joseph M. Shunia ได้พิสูจน์ว่าคลาสของฟังก์ชันพื้นฐาน Kalmár สามารถสร้างขึ้นแบบอุปนัยได้จากการบวก ( ), เศษจำนวนเต็ม ( ) และการยกกำลังฐานสอง ( ) ซึ่งเป็นการปรับปรุงผลลัพธ์ก่อนหน้านี้โดย Mazzanti ^{[ 7 ]}และ Marchenkov ^{[ 8 ]}พวกเขายังพิสูจน์เพิ่มเติมว่าฐานการแทนที่ที่กำหนดโดยการดำเนินการทั้งสามนี้เป็นฐานขั้นต่ำ^{[ 10 ]}คำถามที่ยังเปิดอยู่คือเป็นฐานทางเลือก หรือไม่${\displaystyle n+m}$${\displaystyle n{\bmod {m}}}$${\displaystyle 2^{n}}$${\displaystyle \{n+m,\;\lfloor n/m\rfloor ,\;2^{n}\}}$

ตัวอย่างที่ 1

ให้ ฟังก์ชัน กำหนดฟังก์ชันกำลังสองโดยการซ้อนทับเพียงอย่างเดียว^{[ 11 ]}ซึ่งแสดงให้เห็นว่าฟังก์ชันเช่นการยกกำลังสองสามารถแสดงได้โดยใช้เพียงการบวก เศษจำนวนเต็ม และการยกกำลังฐานสองผ่านการซ้อนทับ โดยไม่ จำเป็นต้องใช้การเรียกซ้ำที่ชัดเจน$${\displaystyle f(a,b)=a{\bmod {b}},\quad g_{1}(n)=2^{n+n},\quad g_{2}(n)=2^{n}+n\,.}$$$${\displaystyle h(n)=f(g_{1}(n),g_{2}(n))=2^{n+n}{\bmod {(}}2^{n}+n)}$$${\displaystyle h(n)=n^{2}}$

ตัวอย่างที่ 2

อีกตัวอย่างหนึ่งของฟังก์ชันเรียกซ้ำพื้นฐานคือเดลต้าโครเนกเกอร์ ซึ่งเป็นไปตามเงื่อนไขถ้าและเป็นไปตามเงื่อนไขอื่น $${\displaystyle \delta _{ij}=2^{(2^{i}{\bmod {(}}2^{j}+1))+(2^{j}{\bmod {(}}2^{i}+1)){\bmod {(}}2^{i}+2^{j})}{\bmod {2}}\,,}$$${\displaystyle \delta _{ij}=1}$${\displaystyle i=j}$${\displaystyle 0}$

ตัวอย่างเพิ่มเติม

${\displaystyle x\mathbin {\dot {-}} y=((2^{x+y}+x){\bmod {(}}2^{x+y}+y)){\bmod {(}}2^{x+y}+x)}$[ ^{12 ]​}

${\displaystyle 2xy=(x+y)^{2}\mathbin {\dot {-}} (x^{2}+y^{2})}$[ ^{13 ]​}

${\displaystyle \lfloor x/y\rfloor =(2(x+1)(x\mathbin {\dot {-}} (x{\bmod {y}}))){\bmod {(}}2(x+1)y\mathbin {\dot {-}} 1)}$[ ^{14 ]​}

${\displaystyle xy=\lfloor 2xy/2\rfloor }$[ ^{15 ]​}

${\displaystyle x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\dot {-}} x)}$[ ^{16 ]​}

ฟังก์ชัน เรียกซ้ำพื้นฐานที่ต่ำกว่าจะปฏิบัติตามคำจำกัดความข้างต้น ยกเว้นว่าไม่อนุญาตให้ใช้ผลคูณที่มีขอบเขต^{[ 3 ]}กล่าวคือ ฟังก์ชันเรียกซ้ำพื้นฐานที่ต่ำกว่าจะต้องเป็นฟังก์ชันศูนย์ ฟังก์ชันสืบทอด หรือฟังก์ชันฉายภาพ การประกอบของฟังก์ชันเรียกซ้ำพื้นฐานที่ต่ำกว่าอื่น ๆ หรือผลรวมที่มีขอบเขตของฟังก์ชันเรียกซ้ำพื้นฐานที่ต่ำกว่าอื่น

ฟังก์ชันเรียกซ้ำพื้นฐานที่ต่ำกว่ายังเรียกว่าฟังก์ชันพื้นฐานของ Skolem อีกด้วย^{[ 17 ] [ 18 ]}

ในขณะที่ฟังก์ชันเรียกซ้ำพื้นฐานอาจมีการเติบโตมากกว่าแบบเลขชี้กำลัง ฟังก์ชันเรียกซ้ำพื้นฐานที่ต่ำกว่าจะมีอัตราการเติบโตแบบพหุนาม

คลาสของฟังก์ชันพื้นฐานที่ต่ำกว่ามีคำอธิบายในแง่ของการประกอบฟังก์ชันง่ายๆ ที่คล้ายคลึงกับที่เรามีสำหรับฟังก์ชันพื้นฐาน^{[ 18 ] [ 19 ]}กล่าวคือ ฟังก์ชันที่มีขอบเขตพหุนามเป็นฟังก์ชันพื้นฐานที่ต่ำกว่าก็ต่อเมื่อสามารถแสดงได้โดยใช้การประกอบของฟังก์ชันต่อไปนี้: การฉายภาพ, , , , , ฟังก์ชันเลขชี้กำลังหนึ่งฟังก์ชัน ( หรือ) โดยมีข้อจำกัดต่อไปนี้เกี่ยวกับโครงสร้างของสูตร: สูตรสามารถมีชั้นได้ไม่เกินสองชั้นเมื่อเทียบกับเลขชี้กำลัง (ตัวอย่างเช่นมี 1 ชั้นมี 2 ชั้นมี 3 ชั้น) ในที่นี้ คือการ ดำเนิน การ AND แบบบิตของnและm${\displaystyle n+1}$${\displaystyle nm}$${\displaystyle n\mathbin {\dot {-}} m}$${\displaystyle n\wedge m}$${\displaystyle \lfloor n/m\rfloor }$${\displaystyle 2^{n}}$${\displaystyle n^{m}}$${\displaystyle xy(z+1)}$${\displaystyle (x+y)^{yz+x}+z^{x+1}}$${\displaystyle 2^{2^{x}}}$${\displaystyle n\wedge m}$

• ประถมศึกษา
• การคำนวณฟังก์ชันเบื้องต้น
• ฟังก์ชันเรียกซ้ำแบบดั้งเดิม
• ลำดับชั้นของ Grzegorczyk
• ลูป (ภาษาโปรแกรม)
• เวลาหมดอายุ