Ackermann function

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

Ackermann function

Post by admin » Fri Aug 02, 2019 8:17 am

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.
User avatar
admin
Chief Operator
Posts: 10
Joined: Fri Jun 07, 2019 3:18 pm
Location: London
Contact:

Re: Ackermann function

Post by admin » Sun Aug 04, 2019 8:14 am

I first learnt about this function via Urbit.

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'.
Post Reply