Talk:Jumpy

Wouldn't Jumpy be a linear bounded automaton, since it can only access finitely many cells on the Game of Life board.

--Fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff (talk) 20:05, 1 November 2024 (UTC)

Yes, Jumpy is merely syntax for an wikipedia:adjacency list, and execution is merely wikipedia:cycle detection. This is a linear-time operation since the input graph is guaranteed to be the wikipedia:graph of a function. The following short Python 3 program decides Jumpy programs in amortized linear time:

import sys
g = [int(l) for l in sys.stdin.readlines()]
seen = set()
i = 0
while i not in seen and i < len(g):
    seen.add(i)
    print(i, "->", g[i])
    i = g[i]

Corbin (talk) 23:51, 1 November 2024 (UTC)

The page allows programs to be infinitely long, so I think you are both right and the language is Turing-powerful regardless – it runs in time, and uses space, linear in the length of the program but this still allows it to be infinite. Figuring out the exact computational class would depend on exactly what sort of infinite programs are allowed. --ais523 00:52, 2 November 2024 (UTC)