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

ฟังก์ชัน McCarthy 91 ถูกกำหนดดังนี้

${\displaystyle M(n)={\begin{cases}n-10,&{\mbox{if }}n>100{\mbox{ }}\\M(M(n+11)),&{\mbox{if }}n\leq 100{\mbox{ }}\end{cases}}}$

ผลลัพธ์ของการประเมินฟังก์ชันแสดงด้วยM ( n ) = 91 สำหรับอาร์กิวเมนต์จำนวนเต็มn  ≤ 100 และM ( n ) =  n  − 10 สำหรับn > 100 ที่จริงแล้ว ผลลัพธ์ของ M(101) ก็คือ 91 เช่นกัน (101 - 10 = 91) ผลลัพธ์ทั้งหมดของ M(n) หลังจาก n = 101 จะเพิ่มขึ้นเรื่อยๆ ทีละ 1 เช่น M(102) = 92, M(103) = 93

ฟังก์ชัน 91 ถูกนำเสนอในบทความที่ตีพิมพ์โดยZohar Manna , Amir PnueliและJohn McCarthyในปี 1970 บทความเหล่านี้แสดงถึงพัฒนาการในช่วงแรกๆ ของการประยุกต์ใช้วิธีการเชิงรูปธรรมในการตรวจสอบโปรแกรมฟังก์ชัน 91 ถูกเลือกเนื่องจากเป็นฟังก์ชันแบบเรียกซ้ำซ้อนกัน (ตรงข้ามกับการเรียกซ้ำแบบเดี่ยวเช่น การกำหนดโดยใช้) ตัวอย่างนี้ได้รับความนิยมจากหนังสือของ Manna เรื่องMathematical Theory of Computation (1974) เมื่อสาขาวิธีการเชิงรูปธรรมก้าวหน้าขึ้น ตัวอย่างนี้ก็ปรากฏขึ้นซ้ำๆ ในงานวิจัย โดยเฉพาะอย่างยิ่ง มันถูกมองว่าเป็น "ปัญหาท้าทาย" สำหรับการตรวจสอบโปรแกรมอัตโนมัติ ${\displaystyle f(n)}$${\displaystyle f(n-1)}$

การทำความเข้าใจเกี่ยวกับการควบคุมการไหล แบบเรียกซ้ำส่วนท้ายนั้นง่ายกว่านี่คือคำจำกัดความที่เทียบเท่ากัน ( เท่ากันในเชิงขยาย ):

${\displaystyle M_{t}(n)=M_{t}'(n,1)}$

${\displaystyle M_{t}'(n,c)={\begin{cases}n,&{\mbox{if }}c=0\\M_{t}'(n-10,c-1),&{\mbox{if }}n>100{\mbox{ and }}c\neq 0\\M_{t}'(n+11,c+1),&{\mbox{if }}n\leq 100{\mbox{ and }}c\neq 0\end{cases}}}$

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

นี่คือคำจำกัดความที่เทียบเท่ากันแบบเรียกซ้ำหาง:

${\displaystyle M_{mt}(n)=M_{mt}'(n,0)}$

${\displaystyle M_{mt}'(n,c)={\begin{cases}M_{mt}''(n-10,c),&{\mbox{if }}n>100{\mbox{ }}\\M_{mt}'(n+11,c+1),&{\mbox{if }}n\leq 100{\mbox{ }}\end{cases}}}$

${\displaystyle M_{mt}''(n,c)={\begin{cases}n,&{\mbox{if }}c=0{\mbox{ }}\\M_{mt}'(n,c-1),&{\mbox{if }}c\neq 0{\mbox{ }}\end{cases}}}$

บทความของMitchell Wand ในปี 1980 ได้นำเสนอการพิสูจน์อย่างเป็นทางการของเวอร์ชัน แบบ เรียกซ้ำที่เชื่อมโยงกันจากเวอร์ชันแบบเรียกซ้ำซ้อนกัน โดยอาศัยการใช้continuations

ตัวอย่าง ก:

M(99) = M(M(110)) เนื่องจาก 99 ≤ 100 = M(100) เนื่องจาก 110 > 100 = M(M(111)) เนื่องจาก 100 ≤ 100 = M(101) เนื่องจาก 111 > 100 = 91 เนื่องจาก 101 > 100 

ตัวอย่าง B:

M(87) = M(M(98)) = M(M(M(109))) = M(M(99)) = M(M(M(110))) = M(M(100)) = M(M(M(111))) = M(M(101)) = M(91) = M(M(102)) = M(92) = M(M(103)) = M(93) .... รูปแบบจะเพิ่มขึ้นเรื่อยๆ จนถึง M(99), M(100) และ M(101) เหมือนกับที่เราเห็นในตัวอย่าง A) ทุกประการ = M(101) เนื่องจาก 111 > 100 = 91 เนื่องจาก 101 > 100 

ต่อไปนี้คือตัวอย่างการใช้งานอัลกอริธึมแบบเรียกซ้ำซ้อนกันในภาษา Python :

def mc91 ( n : int ) -> int : if n > 100 : return n - 10 else : return mc91 ( mc91 ( n + 11 ))

ต่อไปนี้คือตัวอย่างการใช้งานอัลกอริธึมแบบเรียกซ้ำตามหาง (tail-recursive algorithm) ในภาษา Python:

def mc91 ( n : int ) -> int : return mc91taux ( n , 1 )def mc91taux ( n : int , c : int ) -> int : if c == 0 : return n elif n > 100 : return mc91taux ( n - 10 , c - 1 ) else : return mc91taux ( n + 11 , c + 1 )

ต่อไปนี้เป็นข้อพิสูจน์ว่าฟังก์ชัน McCarthy 91 เทียบเท่ากับอัลกอริทึมที่ไม่ใช้การเรียกซ้ำซึ่งกำหนดไว้ดังนี้: ${\displaystyle M}$${\displaystyle M'}$

${\displaystyle M'(n)={\begin{cases}n-10,&{\mbox{if }}n>100{\mbox{ }}\\91,&{\mbox{if }}n\leq 100{\mbox{ }}\end{cases}}}$

สำหรับn > 100 นิยามของและจะเหมือนกัน ดังนั้นความเท่าเทียมกันจึงเป็นผลมาจากนิยามของ ${\displaystyle M'}$${\displaystyle M}$${\displaystyle M}$

สำหรับn ≤ 100 สามารถใช้ การเหนี่ยวนำอย่างเข้มข้น ลงมาจาก 100 ได้:

สำหรับ 90 ≤ n ≤ 100

ตามนิยาม M(n) = M(M(n + 11)) = M(n + 11 - 10) เนื่องจาก n + 11 > 100 = M(n + 1) 

สิ่งนี้สามารถใช้เพื่อแสดงM ( n ) = M (101) = 91 สำหรับ 90 ≤ n ≤ 100:

M(90) = M(91), M(n) = M(n + 1) ได้รับการพิสูจน์แล้วข้างต้น = … = M(101) ตามคำนิยาม = 101 − 10 = 91 

M ( n ) = M (101) = 91 สำหรับ 90 ≤ n ≤ 100 สามารถใช้เป็นกรณีฐานของการเหนี่ยวนำได้

สำหรับขั้นตอนการเหนี่ยวนำลงล่าง ให้กำหนดn ≤ 89 และสมมติให้M ( i ) = 91 สำหรับทุกn < i ≤ 100 แล้ว

ตามนิยาม M(n) = M(M(n + 11)) = M(91) ตามสมมติฐาน เนื่องจาก n < n + 11 ≤ 100 = 91 ตามกรณีพื้นฐาน 

สิ่งนี้พิสูจน์ได้ว่าM ( n ) = 91 สำหรับทุกn ≤ 100 รวมถึงค่าลบด้วย

Donald Knuthได้ขยายฟังก์ชัน 91 ให้ครอบคลุมพารามิเตอร์เพิ่มเติม^{[ 1 ]} John Cowlesได้พัฒนาบทพิสูจน์อย่างเป็นทางการว่าฟังก์ชันทั่วไปของ Knuth เป็นฟังก์ชันสมบูรณ์ โดยใช้ตัวพิสูจน์ทฤษฎีบทACL2 ^{[ 2 ]}