Zenn
Open10

Ackermann(*,*)の壁を突破したかった

Python
暇つぶし
log5log5

https://ja.wikipedia.org/wiki/アッカーマン関数

import sys

sys.setrecursionlimit(10000)


def ackermann(m, n):
    if m == 0:
        return n + 1
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))


print(ackermann(4, 1))

(4,1) を計算するには再帰深度10000でも足りない

Traceback (most recent call last):
  File "/***/main.py", line 16, in <module>
    print(ackermann(5, 0))
  File "/***/main.py", line 11, in ackermann
    return ackermann(m - 1, 1)
  File "/***/main.py", line 13, in ackermann
    return ackermann(m - 1, ackermann(m, n - 1))
  File "/***/main.py", line 13, in ackermann
    return ackermann(m - 1, ackermann(m, n - 1))
  File "/***/main.py", line 13, in ackermann
    return ackermann(m - 1, ackermann(m, n - 1))
  [Previous line repeated 993 more times]
  File "/***/main.py", line 11, in ackermann
    return ackermann(m - 1, 1)
  File "/***/main.py", line 8, in ackermann
    if m == 0:
RecursionError: maximum recursion depth exceeded in comparison

Process finished with exit code 1
log5log5

ちなみに sys.setrecursionlimit(100000) だとこう

log5log5

ショートカット戦法

import sys

sys.setrecursionlimit(10000)


def ackermann(m, n):
    if m == 0:
        return n + 1
    # 1から3まではショートカットを作る
    elif m == 1:
        return n + 2
    elif m == 2:
        return 2 * n + 3
    elif m == 3:
        return pow(2, n + 3) - 3
    # ショートカットここまで
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))


print(ackermann(4, 1))

65533

Process finished with exit code 0
log5log5

5x5の表が作れるかどうか
まあ無理なんですけどね

import sys

sys.setrecursionlimit(10000)


def ackermann(m, n):
    if m == 0:
        return n + 1
    # 1から3まではショートカットを作る
    elif m == 1:
        return n + 2
    elif m == 2:
        return 2 * n + 3
    elif m == 3:
        return pow(2, n + 3) - 3
    # ショートカットここまで
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))


for i in range(1, 5 + 1):
    for j in range(1, 5 + 1):
        print("ack(%d, %d) = %d" % (i, j, ackermann(i, j)))

結果

(4,2)の計算を最後に応答がなくなりました
計算自体は間違ってなさそう
https://www.wolframalpha.com/input/?i=ackermann(4%2C2)&lang=ja

log5log5

比較用

import sys


sys.setrecursionlimit(100000)


count = 0


def ackermann(m, n):
    global count
    count += 1
    print("count: %s" % count)
    if m == 0:
        return n + 1
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))


memo = {}


def ackermann1(m, n):
    global count
    count += 1
    print("count: %s" % count)
    if tuple([m, n]) in memo:
        return memo[tuple([m, n])]

    if m == 0:
        memo[tuple([m, n])] = n + 1
    elif n == 0:
        memo[tuple([m, n])] = ackermann1(m - 1, 1)
    else:
        memo[tuple([m, n])] = ackermann1(m - 1, ackermann1(m, n - 1))

    return memo[tuple([m, n])]


print(ackermann(3, 5))
print(ackermann1(3, 5))
log5log5

memo

import sys

sys.setrecursionlimit(100000)

memo = {}


def ackermann(m, n):
    if tuple([m, n]) in memo:
        return memo[tuple([m, n])]

    if m == 0:
        memo[tuple([m, n])] = n + 1
    elif n == 0:
        memo[tuple([m, n])] = ackermann(m - 1, 1)
    else:
        memo[tuple([m, n])] = ackermann(m - 1, ackermann(m, n - 1))

    return memo[tuple([m, n])]


for i in range(6):
    for j in range(6):
        print("ack(%s, %s) = %s" % (i, j, ackermann(i, j)))

result

ack(0, 0) = 1
ack(0, 1) = 2
ack(0, 2) = 3
ack(0, 3) = 4
ack(0, 4) = 5
ack(0, 5) = 6
ack(1, 0) = 2
ack(1, 1) = 3
ack(1, 2) = 4
ack(1, 3) = 5
ack(1, 4) = 6
ack(1, 5) = 7
ack(2, 0) = 3
ack(2, 1) = 5
ack(2, 2) = 7
ack(2, 3) = 9
ack(2, 4) = 11
ack(2, 5) = 13
ack(3, 0) = 5
ack(3, 1) = 13
ack(3, 2) = 29
ack(3, 3) = 61
ack(3, 4) = 125
ack(3, 5) = 253
ack(4, 0) = 13
ack(4, 1) = 65533

Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)
log5log5
from collections import deque


def ackermann(m, n):
    stack = deque([])
    stack.extend([m, n])

    while len(stack) > 1:
        n, m = stack.pop(), stack.pop()

        if m == 0:
            stack.append(n + 1)
        elif m == 1:
            stack.append(n + 2)
        elif m == 2:
            stack.append(2 * n + 3)
        elif m == 3:
            stack.append(2 ** (n + 3) - 3)
        elif n == 0:
            stack.extend([m - 1, 1])
        else:
            stack.extend([m - 1, m, n - 1])

    return stack[0]


print(ackermann(4, 3))

へんじがない

そりゃ 2^{2^{65536}}-3 はさすがに無理か...