탁 (기능)

컴퓨터 과학에서 탁함수는 재귀함수로 다케우치 이쿠오(太井 竹uchi ()의 이름을 딴 것이다.다음과 같이 정의된다.

${\displaystyle \tau(x,y,z)={\displaystyle{case}\tau(x-1,y,z)\tau(z-1,z,x,y)\tau(z-1,x,y)&{\text{case}}}}}$

반항하다 탁( x, y, z)   만일 y < x     탁(           탁(x-1, y, z),          탁(y-1, z, x),          탁(z-1, x, y)        )   다른     z   종지부를 찍다 종지부를 찍다 

이 함수는 재귀 최적화 언어의 벤치마크로 자주 사용된다.^[1][2][3][4]null

타크슈 vs 타라이슈

타케우치에 의한 원래의 정의는 다음과 같았다.

반항하다 타라이( x, y, z)   만일 y < x     타라이(           타라이(x-1, y, z),          타라이(y-1, z, x),          타라이(z-1, x, y)        )   다른     y          # z가 아니라!   종지부를 찍다 종지부를 찍다 

타라이는 일본어로 "돌아가다"는 たらいしし 타라이마와시의 줄임말이다.null

존 매카시는 타케우치의 이름을 따서 이 기능의 이름을 탁()이라고 지었다.^[5]null

그러나 나중에 어떤 언급에서 y는 어떻게든 z로 바뀌었다.이것은 작지만 중요한 차이점이다. 왜냐하면 원본은 게으른 평가로 큰 이득을 보기 때문이다.다른 것과 정확히 같은 방식으로 쓰여졌지만, 아래의 하스켈 코드는 훨씬 더 빨리 실행된다.null

타라이 :: 인트 -> 인트 -> 인트 -> 인트 타라이 x y z       x <= y    = y       그렇지 않으면 = 타라이(타라이 (x-1) y z)                        (타라이 (y-1) z x)                        (타라이 (z-1) x y) 

메모를 통해 이 기능을 쉽게 가속할 수 있지만 게으른 평가는 여전히 이긴다.null

타라이를 최적화하는 가장 잘 알려진 방법은 다음과 같이 상호 재귀적 도우미 기능을 사용하는 것이다.null

반항하다 가장 게으른_타라이(x, y, zx, zy, zz)   ~하지 않는 한 y < x     y   다른     가장 게으른_타라이(타라이(x-1, y, z),                   타라이(y-1, z, x),                   타라이(zx, zy, zz)-1, x, y)   종지부를 찍다 종지부를 찍다  반항하다 타라이(x, y, z)   ~하지 않는 한 y < x     y   다른     가장 게으른_타라이(타라이(x-1, y, z),                   타라이(y-1, z, x),                   z-1, x, y)   종지부를 찍다 종지부를 찍다 

다음은 C:의 타라이()의 효율적인 구현이다.

인트로 타라이(인트로 x, 인트로 y, 인트로 z) {     하는 동안에 (x > y) {         인트로 올드엑스 = x, 구식의 = y;         x = 타라이(x - 1, y, z);         y = 타라이(y - 1, z, 올드엑스);         만일 (x <= y) 부숴뜨리다;         z = 타라이(z - 1, 올드엑스, 구식의);     }     돌아오다 y; } 

z(세 번째 인수)를 평가하기 전에 (x <= y)에 대한 추가 검사를 주의하여 불필요한 재귀 평가를 피하십시오.null

참조

외부 링크

• Weisstein, Eric W. "TAK Function". MathWorld.
• TAC 함수