## Ackermann function

From ancient engineering to the cutting-edge
Chief Operator
Posts: 18
Joined: Fri Jun 07, 2019 3:18 pm
Location: London
Contact:

### Ackermann function

https://en.wikipedia.org/wiki/Ackermann_function

My JavaScript implementations:

Code: Select all

``````function ackermann(m, n) => {
if (m === 0) return n + 1;
if (m > 0 && n === 0) return ap(m - 1, 1);
if (m > 0 && n > 0) return ap(m - 1, ap(m, n - 1));
}``````
A faster version without recursion:

Code: Select all

``````function ackermann(m, n) => {
let cm = [];
while (true) {
if (m === 0) {
if (!cm.length) return n + 1;
m = cm.pop();
++n;
} else if (m > 0 && n === 0) {
--m;
n = 1;
} else if (m > 0 && n > 0) {
--n;
cm.push(m - 1);
}
}
}``````
Even with small inputs, it churns though a massive number of computational steps, and requires a large amount of memory, on the way towards reaching the output.
Chief Operator
Posts: 18
Joined: Fri Jun 07, 2019 3:18 pm
Location: London
Contact:

### Re: Ackermann function

https://urbit.org/docs/learn/hoon/hoon- ... ackermann/

(I'm doing Hoon School now.)

I thought the statement that it is "not primitively recursive -- meaning it can not be rewritten in an iterative fashion" was supposed to mean that it couldn't be written without recursion, with a loop only. But obviously that's not what that means, or the code above would be impossible. I guess it'd be impossible to do with a for loop where we decide upfront how many iterations we'll go through. (And I know that's not the only way to use the for loop.)

It's a great example of a brief, simple program that's runs in some finite time, and (potentially) consumes a shit-ton of resources. Uselessly. See also: Bitcoin.

It's a clear demonstration of why shared computing systems can't be a free-for-all, they need to be rationed. I wonder if the earliest timesharing systems were robust enough to handle (i.e. not get completely buried, and be able to 'cleanly' stop/crash/interrupt) implementations of Ackermann.

https://en.wikipedia.org/wiki/Dartmouth ... ing_System

That's 1963.

One supposes if you try it on Ethereum you'll be burning a lot of 'gas'.