매카시 91 함수

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2015년 10월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

매카시 91 함수는 컴퓨터 과학자 존 매카시가 컴퓨터 과학 내에서 공식적인 검증을 위한 시험 사례로 정의한 재귀 함수다.

매카시 91 함수는 다음과 같이 정의된다.

${\displaystyle M(n)={\begin}n-10,&{\mbox{{}n}100{\mbox{}}\mbox{{}\mbox{}}\mbox{}),&{\mbox{}$

함수 평가 결과는 모든 정수 인수 n ≤ 100에 대해 M(n) = 91로, n > 100에 대해서는 M(n) = n - 10으로 주어진다. 실제로 M(101)의 결과도 91(101 - 10 = 91)이다. n = 101 이후 M(n)의 모든 결과는 지속적으로 1씩 증가하고 있다. 예: M(102) = 92, M(103) = 93.

역사

91 기능은 조하르 마나, 아미르 페누엘리, 존 매카시가 1970년에 발표한 논문에서 소개되었다. 이 논문들은 프로그램 검증을 위한 공식적인 방법의 적용을 향한 초기 개발을 나타낸다. 91 함수는 내포-재귀성을 위해 선택되었다(${\displaystyle f}$${\displaystyle }$(n${\displaystyle }$)$${\$displaystyle$ f$($n)}을(를${\displaystyle )}$ f (${\displaystyle \mathrm{n}}$ ${\displaystyle -}$1$)$ {\$displaystyle$ $f$$(n-1$)를 사용하여 $정의$한 것과 같은 단일 재귀와 대비된다).$$ 그 예는 마나의 저서 《수학적 계산 이론》(1974년)에 의해 대중화되었다. 형식 방법의 분야가 발전함에 따라, 이 예는 연구 문헌에 반복적으로 나타났다. 특히 자동화된 프로그램 검증을 위한 '도전 문제'로 평가된다.

꼬리-재귀 제어 흐름은 쉽게 이해할 수 있으며, 이는 등가(확장적으로 동일) 정의로 다음과 같다.

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

${\displaystyle M_{t}'(n,c)={\begin{case}n,&{\mbox{if{}c=0\\\}M_{t}'(n-10,c-1),&{\mbox{{}n}100{\mbox{{} 및 }}c\neq 0\\\M_{t}'(n+11,c+1)&#mbox{}{{n\n\leq 100{\mbox{},}, }}$

그러한 추리를 입증하기 위해 사용된 예들 중 하나로, 마나의 책에는 내포-재발 91 함수에 해당하는 꼬리-재발 알고리즘이 포함되어 있다. 91 함수의 "자동 검증"(또는 종료 증명)을 보고하는 논문의 상당수는 꼬리 회수 버전만 취급한다.

이는 상호 꼬리-재귀적 정의와 동일하다.

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

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

${\displaystyle M_{mt}"(n,c)={\begin{case}n,&#\mbox{{}c=0{\mbox{}}}{}}(n,c-1),&#mbox{}{c\neq 0}{\mbox{}}}}}$

내포된 재귀 버전에서 상호 꼬리-재귀 버전을 공식적으로 파생한 것은 1980년 미첼 완드의 기사에서 계속의 사용에 기초하여 제공되었다.

예

예 A:

M(99) = 99㎛ 100 = M(110) 이후 M(100) 110 > 100 = 100 = M(111) 이후 111 > 100 = M(101) 이후 111 > 100 = 91 이후 101 > 100 이후의 M(1101) 

예 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에서 본 것과 정확히 같다) = 111 > 100 = 91 이후부터 M(101)까지 계속 증가한다. 

코드

다음은 Lisp에서 중첩-재귀 알고리즘의 구현이다.

(반기를 들다 mc91 (n)   (묵상하다 ((<= n 100) (mc91 (mc91 (+ n 11))))         (t (- n 10)))) 

다음은 Haskell에서 중첩-재귀 알고리즘의 구현이다.

mc91 n      n > 100   = n - 10     그렇지 않으면 = mc91 $ mc91 $ n + 11 

다음은 OCaml에서 중첩-재귀 알고리즘의 구현이다.

하게 하다 읊다 mc91 n =   만일 n > 100 그때 n - 10   다른 mc91 (mc91 (n + 11)) 

다음은 OCaml에서 꼬리 회수 알고리즘의 구현이다.

하게 하다 mc91 n =   하게 하다 읊다 보조를 맞추다 n c =     만일 c = 0 그때 n     다른 만일 n > 100 그때 보조를 맞추다 (n - 10) (c - 1)     다른 보조를 맞추다 (n + 11) (c + 1)   에   보조를 맞추다 n 1 

다음은 Python에서 중첩-재귀 알고리즘의 구현이다.

반항하다 mc91(n: 인트로) -> 인트로:     """맥카시 91 함수."""     만일 n > 100:         돌아오다 n - 10     다른:         돌아오다 mc91(mc91(n + 11)) 

다음은 C:에서 중첩-재귀 알고리즘의 구현이다.

인트로 mc91(인트로 n) {     만일 (n > 100) {         돌아오다 n - 10;     } 다른 {         돌아오다 mc91(mc91(n + 11));     } } 

다음은 C:의 꼬리-재귀 알고리즘 구현이다.

인트로 mc91(인트로 n) {     돌아오다 mc91taux(n, 1); }  인트로 mc91taux(인트로 n, 인트로 c) {     만일 (c != 0) {         만일 (n > 100) {             돌아오다 mc91taux(n - 10, c - 1);         } 다른 {             돌아오다 mc91taux(n + 11, c + 1);         }     } 다른 {         돌아오다 n;     } } 

증명

라는 증거가 있다.

${\displaystyle M(n)={\begin}n-10,&{\mbox{{n}100{\mbox{}}}}}{}\mbox{}}},&#mbox{{}}}}}}$

$이{\displaystyle }$ 알고리즘은$$M {\$displaystyle$ M$}$을(를) 계산하는 데 동등한 비복구 알고리즘을 제공한다$.$

n > 100의 경우, $M{\displaystyle }$ ${\displaystyle M}$의 정의로부터 평등이 따르며$,$ n ≤ 100의 경우, 100의 강한 유도를 사용할 수 있다.

90 n 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 n 100 100. 이것은 베이스 케이스로 사용할 수 있다.

유도단계의 경우 n ≤ 89로 하고 모든 n < i ≤ 100에 대해 M(i) = 91을 가정한다.

M(n) = M(M(n + 11), 정의 = M(91), 가설, n < n + 11 ≤ 100 = 91, 베이스 케이스에 의한 n < n + 11 ≤ 100 = 91.  

이는 음수 값을 포함한 모든 n ≤ 100에 대해 M(n) = 91을 증명한다.

크누스의 일반화

도널드 크누스는 91 함수를 일반화하여 추가 파라미터를 포함시켰다.^[1] 존 코울스는 ACL2 정리 프로베른을 이용하여 크누스의 일반화된 기능이 총체적이라는 공식적인 증거를 개발했다.^[2]

참조

• Manna, Zohar; Pnueli, Amir (July 1970). "Formalization of Properties of Functional Programs". Journal of the ACM. 17 (3): 555–569. doi:10.1145/321592.321606.
• Manna, Zohar; McCarthy, John (1970). "Properties of programs and partial function logic". Machine Intelligence. 5. OCLC 35422131.
• Manna, Zohar (1974). Mathematical Theory of Computation (4th ed.). McGraw-Hill. ISBN 9780070399105.
• Wand, Mitchell (January 1980). "Continuation-Based Program Transformation Strategies". Journal of the ACM. 27 (1): 164–180. doi:10.1145/322169.322183.