Page 1 of 1

Ackermann function

Posted: Fri Aug 02, 2019 8:17 am
by admin

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();
    } else if (m > 0 && n === 0) {
      n = 1;
    } else if (m > 0 && n > 0) {
      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.

Re: Ackermann function

Posted: Sun Aug 04, 2019 8:14 am
by admin
I first learnt about this function via Urbit. ... 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. ... ing_System

That's 1963.

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