ในทฤษฎีความสามารถในการคำนวณทฤษฎีบท การเรียกซ้ำของคลีนเป็นผลลัพธ์พื้นฐานสองประการเกี่ยวกับการประยุกต์ใช้ฟังก์ชันที่คำนวณได้กับคำอธิบายของฟังก์ชันเหล่านั้น ทฤษฎีบทนี้ได้รับการพิสูจน์ครั้งแรกโดยสตีเฟน คลีนในปี 1938 ^{[ 1 ]}และปรากฏในหนังสือIntroduction to Metamathematics ของเขา ใน ปี 1952 ^{[ 2 ]}ทฤษฎีบทที่เกี่ยวข้องซึ่งสร้างจุดคงที่ของฟังก์ชันที่คำนวณได้เรียกว่าทฤษฎีบทของโรเจอร์สและเป็นผลงานของฮาร์ทลีย์ โรเจอร์ส จูเนียร์^{[ 3 ]}

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

ข้อความของทฤษฎีบทอ้างถึง การ กำหนด หมายเลขที่ยอมรับได้ ของฟังก์ชันเวียนเกิดบางส่วนโดยที่ฟังก์ชันที่สอดคล้องกับดัชนีคือ${\displaystyle \varphi }$${\displaystyle e}$${\displaystyle \varphi _{e}}$

ถ้าและเป็นฟังก์ชันบางส่วนบนจำนวนธรรมชาติ สัญลักษณ์แสดงว่า สำหรับแต่ละnนั้นและจะถูกกำหนดและเท่ากัน หรือไม่ก็และจะไม่ถูกกำหนดทั้งคู่ ${\displaystyle F}$${\displaystyle G}$${\displaystyle F\simeq G}$${\displaystyle F(n)}$${\displaystyle G(n)}$${\displaystyle F(n)}$${\displaystyle G(n)}$

กำหนดให้ฟังก์ชันบนจำนวนธรรมชาติจุดตรึงของคือดัชนีในโดเมนของซึ่ง. โปรดสังเกตว่าการเปรียบเทียบอินพุตและเอาต์พุตในที่นี้ไม่ได้พิจารณาจากค่าตัวเลข แต่พิจารณาจากฟังก์ชันเวียนเกิดบางส่วนที่เกี่ยวข้อง ${\displaystyle F}$${\displaystyle F}$${\displaystyle e}$${\displaystyle F}$${\displaystyle \varphi _{e}\simeq \varphi _{F(e)}}$

Rogers อธิบายผลลัพธ์ต่อไปนี้ว่าเป็น "เวอร์ชันที่ง่ายกว่า" ของทฤษฎีบทการเรียกซ้ำ (ครั้งที่สอง) ของ Kleene ^{[ 4 ]}

โดยพื้นฐานแล้วหมายความว่า หากเราใช้ การแปลง ที่มีประสิทธิภาพกับโปรแกรม (เช่น การแทนที่คำสั่งต่างๆ เช่น ตัวสืบทอด การกระโดด การลบบรรทัด) จะมีโปรแกรมหนึ่งเสมอที่พฤติกรรมของมันไม่เปลี่ยนแปลงไปจากการแปลงนั้น ทฤษฎีบทนี้จึงสามารถตีความได้ดังนี้: “เมื่อมีกระบวนการใดๆ ที่มีประสิทธิภาพในการแปลงโปรแกรม จะมีโปรแกรมหนึ่งเสมอที่เมื่อถูกแก้ไขโดยกระบวนการนั้นแล้ว จะทำงานเหมือนเดิมทุกประการ” หรือ: “เป็นไปไม่ได้ที่จะเขียนโปรแกรมที่เปลี่ยนแปลงพฤติกรรมเชิงขยายของทุกโปรแกรม”

การพิสูจน์นี้ใช้ฟังก์ชันคำนวณทั้งหมดเฉพาะตัวหนึ่งซึ่งกำหนดไว้ดังนี้ เมื่อกำหนดจำนวนธรรมชาติฟังก์ชันนี้จะส่งออกดัชนีของฟังก์ชันคำนวณบางส่วนที่ทำการคำนวณต่อไปนี้: ${\displaystyle h}$${\displaystyle x}$${\displaystyle h}$

เมื่อได้รับอินพุตให้ลองคำนวณก่อนหากการคำนวณนั้นให้ผลลัพธ์เป็นให้คำนวณและส่งคืนค่าของมัน หากมี ดังนั้น สำหรับดัชนีทั้งหมดของฟังก์ชันที่คำนวณได้บางส่วน หากถูกกำหนดไว้แล้วถ้าไม่ได้ถูกกำหนดไว้ ก็คือฟังก์ชันที่ไม่ได้ถูกกำหนดไว้ที่ใดเลย ฟังก์ชันสามารถสร้างขึ้นจากฟังก์ชันที่คำนวณได้บางส่วนที่อธิบายไว้ข้างต้นและS${\displaystyle y}$${\displaystyle \varphi _{x}(x)}$${\displaystyle e}$${\displaystyle \varphi _{e}(y)}$${\displaystyle x}$${\displaystyle \varphi _{x}(x)}$${\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}}$${\displaystyle \varphi _{x}(x)}$${\displaystyle \varphi _{h(x)}}$${\displaystyle h}$${\displaystyle g(x,y)}$ ม.น.​ ทฤษฎีบท : สำหรับแต่ละค่า จำนวนนั้นคือดัชนีของโปรแกรมที่คำนวณฟังก์ชัน${\displaystyle x}$${\displaystyle h(x)}$${\displaystyle y\mapsto g(x,y)}$

เพื่อให้การพิสูจน์เสร็จสมบูรณ์ ให้เป็นฟังก์ชันที่คำนวณได้ทั้งหมด และสร้างดังที่กล่าวมาข้างต้น ให้เป็นดัชนีของการประกอบซึ่งเป็นฟังก์ชันที่คำนวณได้ทั้งหมด ดังนั้น จึงถูก กำหนดไว้ จากนั้นโดยนิยามของแต่เนื่องจากเป็นดัชนีของและดังนั้นดังนั้นสำหรับ${\displaystyle F}$${\displaystyle h}$${\displaystyle e}$${\displaystyle F\circ h}$${\displaystyle \varphi _{e}(e)}$${\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}}$${\displaystyle h}$${\displaystyle e}$${\displaystyle F\circ h}$${\displaystyle \varphi _{e}(e)=(F\circ h)(e)=F(h(e))}$${\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}}$${\displaystyle \varphi _{n}\simeq \varphi _{F(n)}}$${\displaystyle n=h(e)}$

การพิสูจน์นี้เป็นการสร้างฟังก์ชันเรียกซ้ำบางส่วนที่ใช้ในการสร้างY combinator

ฟังก์ชันที่สำหรับทุก ๆเรียกว่า ฟังก์ชัน ที่ปราศจากจุดตรึงทฤษฎีบทจุดตรึงแสดงให้เห็นว่าไม่มีฟังก์ชันที่คำนวณได้ทั้งหมดใดที่ปราศจากจุดตรึง แต่มีฟังก์ชันที่ปราศจากจุดตรึงที่ไม่สามารถคำนวณได้จำนวนมากเกณฑ์ความสมบูรณ์ของ Arslanov ระบุว่า ระดับ Turing ที่นับได้แบบเรียกซ้ำเพียงอย่างเดียวที่คำนวณฟังก์ชันที่ปราศจากจุดตรึงคือ0′ซึ่งเป็นระดับของปัญหาการหยุดทำงาน^{[ 5 ]}${\displaystyle F}$${\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}}$${\displaystyle e}$

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

ทฤษฎีบทการเรียกซ้ำข้อที่สองสำหรับฟังก์ชันเรียกซ้ำบางส่วนใดๆจะมีดัชนีเช่นนั้น${\displaystyle Q(x,y)}$${\displaystyle p}$${\displaystyle \varphi _{p}\simeq \lambda y.Q(p,y)}$

ทฤษฎีบทนี้สามารถพิสูจน์ได้จากทฤษฎีบทของโรเจอร์ส โดยให้เป็นฟังก์ชันที่(การสร้างที่อธิบายโดยS)${\displaystyle F}$${\displaystyle \varphi _{F(p)}(y)=Q(p,y)}$ ม.น.​ ทฤษฎีบท ) จากนั้นสามารถตรวจสอบได้ว่าจุดตรึงของสิ่งนี้เป็นดัชนีตามที่ต้องการ ทฤษฎีบทนี้เป็นแบบสร้างสรรค์ในแง่ที่ว่าฟังก์ชันคำนวณคงที่แปลงดัชนีสำหรับ ไป เป็น ดัชนี${\displaystyle F}$${\displaystyle p}$${\displaystyle Q}$${\displaystyle p}$

ทฤษฎีบทการเรียกซ้ำครั้งที่สองของ Kleene และทฤษฎีบทของ Rogers สามารถพิสูจน์ได้ค่อนข้างง่ายจากกันและกัน^{[ 6 ]}อย่างไรก็ตาม การพิสูจน์โดยตรงของทฤษฎีบทของ Kleene ^{[ 7 ]}ไม่ได้ใช้โปรแกรมสากล ซึ่งหมายความว่าทฤษฎีบทนี้ใช้ได้กับระบบการเขียนโปรแกรมแบบเรียกซ้ำย่อยบางระบบที่ไม่มีโปรแกรมสากล

ตัวอย่างคลาสสิกที่ใช้ทฤษฎีบทการเรียกซ้ำครั้งที่สองคือฟังก์ชันดัชนีที่สอดคล้องกันในกรณีนี้จะให้ฟังก์ชันที่คำนวณได้ซึ่งส่งออกดัชนีของตัวเองเมื่อนำไปใช้กับค่าใดๆ^{[ 8 ]} เมื่อแสดงเป็นโปรแกรมคอมพิวเตอร์ ดัชนี ดังกล่าวเรียกว่าquines${\displaystyle Q(x,y)=x}$${\displaystyle p}$

ตัวอย่างต่อไปนี้ในภาษา Lispแสดงให้เห็นว่าผลลัพธ์ในบทสรุปสามารถสร้างขึ้นได้อย่างมีประสิทธิภาพจากฟังก์ชันฟังก์ชันในโค้ดคือฟังก์ชันที่มีชื่อนั้นซึ่งสร้างขึ้นโดยS${\displaystyle p}$${\displaystyle Q}$s11 ม.น.​ ทฤษฎีบท​

Qสามารถเปลี่ยนเป็นฟังก์ชันที่มีอาร์กิวเมนต์สองตัวใดก็ได้

( setq Q ' ( lambda ( x y ) x )) ( setq s11 ' ( lambda ( f x ) ( list 'lambda ' ( y ) ( list f x 'y )))) ( setq n ( list 'lambda ' ( x y ) ( list Q ( list s11 'x 'x ) 'y ))) ( setq p ( eval ( list s11 n n )))

ผลลัพธ์ของนิพจน์ต่อไปนี้ควรเหมือนกัน${\displaystyle \varphi }$p(nil)

( eval ( list p nil ))

Q(p, nil)

( eval ( list Q p nil ))

สมมติว่าและเป็นฟังก์ชันที่คำนวณได้ทั้งหมดซึ่งใช้ในการนิยามแบบเรียกซ้ำสำหรับฟังก์ชัน: ${\displaystyle g}$${\displaystyle h}$${\displaystyle f}$

${\displaystyle f(0,y)\simeq g(y),}$

${\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),}$

ทฤษฎีบทการเรียกซ้ำข้อที่สองสามารถใช้เพื่อแสดงว่าสมการดังกล่าวสามารถกำหนดฟังก์ชันที่คำนวณได้ โดยที่แนวคิดเรื่องความสามารถในการคำนวณไม่จำเป็นต้องอนุญาตให้มีการนิยามแบบเรียกซ้ำในเบื้องต้น (ตัวอย่างเช่น อาจกำหนดโดยการเรียกซ้ำแบบ μหรือโดยเครื่องจักรทัวริง ) การนิยามแบบเรียกซ้ำนี้สามารถแปลงเป็นฟังก์ชันที่คำนวณได้ซึ่งถือว่าเป็นดัชนีของตัวมันเอง เพื่อจำลองการเรียกซ้ำ: ${\displaystyle \varphi _{F}(e,x,y)}$${\displaystyle e}$

${\displaystyle \varphi _{F}(e,0,y)\simeq g(y),}$

${\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).}$

ทฤษฎีบทการเรียกซ้ำพิสูจน์การมีอยู่ของฟังก์ชันที่คำนวณได้ซึ่งทำให้ดังนั้น จึง สอดคล้องกับนิยามการเรียกซ้ำที่กำหนด ${\displaystyle \varphi _{f}}$${\displaystyle \varphi _{f}(x,y)\simeq \varphi _{F}(f,x,y)}$${\displaystyle f}$

การเขียนโปรแกรม แบบสะท้อนกลับ หรือแบบสะท้อนหมายถึงการใช้การอ้างอิงตนเองในโปรแกรม โจนส์นำเสนอมุมมองของทฤษฎีบทการเรียกซ้ำครั้งที่สองโดยอิงจากภาษาแบบสะท้อนกลับ^{[ 9 ]} แสดงให้เห็นว่าภาษาแบบสะท้อนกลับที่กำหนดไว้นั้นไม่ได้แข็งแกร่งกว่าภาษาที่ไม่มีการสะท้อนกลับ (เนื่องจากสามารถนำตัวแปลภาษาแบบสะท้อนกลับไปใช้งานได้โดยไม่ต้องใช้การสะท้อนกลับ) จากนั้นจึงแสดงให้เห็นว่าทฤษฎีบทการเรียกซ้ำนั้นแทบจะไม่มีความสำคัญในภาษาแบบสะท้อนกลับเลย

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

ตัวดำเนินการแจงนับ Φ แต่ละตัวจะกำหนดฟังก์ชันจากเซตของจำนวนธรรมชาติไปยังเซตของจำนวนธรรมชาติที่กำหนดโดย

${\displaystyle \Phi (X)=\{n\mid \exists A\subseteq X[(A,n)\in \Phi ]\}.}$

ตัวดำเนินการแบบเรียกซ้ำ (recursive operator)คือตัวดำเนินการแจงนับ (enumeration operator) ที่เมื่อได้รับกราฟของฟังก์ชันเรียกซ้ำบางส่วน จะส่งคืนกราฟของฟังก์ชันเรียกซ้ำบางส่วนนั้นเสมอ

จุดตรึงของตัวดำเนินการแจงนับ Φ คือเซตFที่ Φ( F ) = Fทฤษฎีบทการแจงนับข้อแรกแสดงให้เห็นว่าสามารถหาจุดตรึงได้อย่างมีประสิทธิภาพหากตัวดำเนินการแจงนับนั้นสามารถคำนวณได้

ทฤษฎีบทการเรียกซ้ำข้อแรกข้อความต่อไปนี้เป็นจริง

1. สำหรับตัวดำเนินการแจงนับที่คำนวณได้ใดๆ Φ จะมีเซตแจงนับแบบเวียนซ้ำF อยู่ ซึ่ง Φ( F ) = FและFเป็นเซตที่เล็กที่สุดที่มีคุณสมบัตินี้
2. สำหรับตัวดำเนินการเวียนเกิดใดๆ Ψ จะมีฟังก์ชันคำนวณได้บางส่วน φ ที่ทำให้ Ψ(φ) = φ และ φ คือฟังก์ชันคำนวณได้บางส่วนที่เล็กที่สุดที่มีคุณสมบัตินี้

ทฤษฎีการเรียกซ้ำครั้งแรกเรียกอีกอย่างว่าทฤษฎีจุดตรึง (ของทฤษฎีการเรียกซ้ำ) ^{[ 10 ]}นอกจากนี้ยังมีคำจำกัดความที่สามารถนำไปใช้กับฟังก์ชันการเรียกซ้ำได้ดังนี้:

ให้เป็นฟังก์ชันแบบเรียกซ้ำ แล้ว จะมีจุดตรึงน้อยที่สุดซึ่งสามารถคำนวณได้ กล่าวคือ ${\displaystyle \Phi :\mathbb {F} (\mathbb {N} ^{k})\rightarrow (\mathbb {N} ^{k})}$${\displaystyle \Phi }$${\displaystyle f_{\Phi }:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$

1)${\displaystyle \Phi (f_{\phi })=f_{\Phi }}$

2) โดยที่ถือว่า${\displaystyle \forall g\in \mathbb {F} (\mathbb {N} ^{k})}$${\displaystyle \Phi (g)=g}$${\displaystyle f_{\Phi }\subseteq g}$

3) สามารถคำนวณได้ ${\displaystyle f_{\Phi }}$

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

พิจารณาสมการเวียนเกิดสำหรับฟังก์ชันแฟกทอเรียลf : ตัวดำเนินการเวียนเกิด Φ ที่สอดคล้องกันจะมีข้อมูลที่บอกวิธีการไปยังค่าถัดไปของfจากค่าก่อนหน้า อย่างไรก็ตาม ตัวดำเนินการเวียนเกิดจะกำหนดกราฟของf จริงๆ ก่อนอื่น Φ จะมีคู่ซึ่งบ่งชี้ว่าf (0) คือ 1 อย่างแน่นอน และดังนั้นคู่ (0,1) จึงอยู่ในกราฟของ f$${\displaystyle {\begin{aligned}&f(0)=1\\&f(n+1)=(n+1)\cdot f(n)\end{aligned}}}$$${\displaystyle (\varnothing ,(0,1))}$

ต่อไป สำหรับแต่ละnและmนั้น Φ จะมีคู่ซึ่งแสดงว่า ถ้าf ( n ) คือmแล้วf ( n +1)คือ( n +1) mดังนั้นคู่( n +1, ( n +1) m )จึงอยู่ในกราฟของfซึ่งแตกต่างจากกรณีพื้นฐานf (0) = 1ตัวดำเนินการแบบเรียกซ้ำต้องการข้อมูลบางอย่างเกี่ยวกับf ( n ) ก่อนที่จะกำหนดค่าของf ( n +1 ) ${\displaystyle (\{(n,m)\},(n+1,(n+1)\cdot m))}$

ทฤษฎีบทการเรียกซ้ำข้อแรก (โดยเฉพาะส่วนที่ 1) ระบุว่ามีเซตF อยู่เซตหนึ่ง ซึ่งΦ( F ) = FเซตFจะประกอบด้วยคู่ลำดับของจำนวนธรรมชาติทั้งหมด และจะเป็นกราฟของฟังก์ชันแฟกทอเรียลfตามที่ต้องการ

ข้อจำกัดของสมการเวียนเกิดที่สามารถแปลงเป็นตัวดำเนินการเวียนเกิดได้นั้น ทำให้มั่นใจได้ว่าสมการเวียนเกิดจะกำหนดจุดตรึงที่น้อยที่สุด ได้จริง ตัวอย่างเช่น พิจารณาเซตของสมการเวียนเกิด: ไม่มีฟังก์ชันg ใด ที่สอดคล้องกับสมการเหล่านี้ เพราะสมการเหล่านี้บ่งชี้ว่าg (2) = 1 และยังบ่งชี้ว่าg (2) = 0 ด้วย ดังนั้นจึงไม่มีจุดตรึงgใดที่สอดคล้องกับสมการเวียนเกิดเหล่านี้ เป็นไปได้ที่จะสร้างตัวดำเนินการแจงนับที่สอดคล้องกับสมการเหล่านี้ แต่จะไม่ใช่ตัวดำเนินการเวียนเกิด $${\displaystyle {\begin{aligned}&g(0)=1\\&g(n+1)=1\\&g(2n)=0\end{aligned}}}$$

การพิสูจน์ส่วนที่ 1 ของทฤษฎีบทการเรียกซ้ำข้อแรกได้มาจากการวนซ้ำตัวดำเนินการแจงนับ Φ โดยเริ่มต้นจากเซตว่าง ก่อนอื่น สร้างลำดับF สำหรับ ให้F เป็นเซตว่าง ดำเนินการแบบอุปนัย สำหรับแต่ละkให้F เป็นสุดท้ายเลือกF เป็น ส่วนที่เหลือของการพิสูจน์ประกอบด้วยการตรวจสอบว่าFสามารถแจงนับได้แบบเรียกซ้ำและเป็นจุดตรึงที่เล็กที่สุดของ Φ ลำดับF ที่ใช้ในการพิสูจน์นี้สอดคล้องกับสายโซ่ Kleene ในการพิสูจน์ทฤษฎีบท จุดตรึงของ Kleene${\displaystyle k=0,1,\ldots }$${\displaystyle F_{k}\cup \Phi (F_{k})}$${\textstyle \bigcup F_{k}}$

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

เมื่อเปรียบเทียบกับทฤษฎีการเรียกซ้ำครั้งที่สอง ทฤษฎีการเรียกซ้ำครั้งแรกจะให้ข้อสรุปที่แข็งแกร่งกว่า แต่เฉพาะเมื่อสมมติฐานที่แคบกว่าเป็นไปตามเงื่อนไขเท่านั้น โรเจอร์สใช้คำว่าทฤษฎีการเรียกซ้ำแบบอ่อนสำหรับทฤษฎีการเรียกซ้ำครั้งแรก และทฤษฎีการเรียกซ้ำแบบแข็งสำหรับทฤษฎีการเรียกซ้ำครั้งที่สอง^{[ 3 ]}

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

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

ในบริบทของทฤษฎีการกำหนดหมายเลขของเขาErshov แสดงให้เห็นว่าทฤษฎีบทการเรียกซ้ำของ Kleene ใช้ได้กับการกำหนดหมายเลขที่สมบูรณ์ก่อน ใด ๆ^{[ 11 ]}การกำหนดหมายเลขของ Gödel เป็นการกำหนดหมายเลขที่สมบูรณ์ก่อนบนเซตของฟังก์ชันที่คำนวณได้ ดังนั้นทฤษฎีบททั่วไปจึงให้ทฤษฎีบทการเรียกซ้ำของ Kleene เป็นกรณีพิเศษ^{[ 12 ]}

เมื่อกำหนดหมายเลขที่สมบูรณ์แล้ว สำหรับฟังก์ชันที่คำนวณได้บางส่วนที่มีพารามิเตอร์สองตัว จะมีฟังก์ชันที่คำนวณได้ทั้งหมดที่มีพารามิเตอร์หนึ่งตัวอยู่ด้วย ซึ่งทำให้ ${\displaystyle \nu }$${\displaystyle f}$${\displaystyle t}$

${\displaystyle \forall n\in \mathbb {N} :\nu \circ f(n,t(n))=\nu \circ t(n).}$

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

• Jockusch, CG ; Lerman, M.; Soare, RI ; Solovay, RM (1989). "เซตที่แจงนับได้แบบเรียกซ้ำโมดูลการกระโดดซ้ำและการขยายเกณฑ์ความสมบูรณ์ของ Arslanov" วารสารตรรกศาสตร์เชิงสัญลักษณ์ 54 ( 4): 1288– 1323. doi : 10.1017/S0022481200041104 . ISSN  0022-4812 . JSTOR  2274816 . S2CID  32203705 .

• บทความเรื่อง "ฟังก์ชันเรียกซ้ำ"โดยPiergiorgio Odifreddiในสารานุกรมปรัชญาแห่งสแตนฟอร์ดปี 2012