Stack Overflow
Stack Overflow

Questions tagged [ackermann]

A well-defined total function which is computable but not primitive recursive. It grows faster than an exponential function, or even a multiple exponential function.

55 questions
42
votes
7 answers

Theoretically can the Ackermann function be optimized?

I am wondering if there can be a version of Ackermann function with better time complexity than the standard variation. This is not a homework and I am just curious. I know the Ackermann function doesn't have any practical use besides as a…
Ξένη Γήινος
  • 2,181
  • 1
  • 9
  • 35
17
votes
2 answers

Memoization of Ackermann function

I would like to compute the A(3, 20) value of Ackermann function (see Wikipedia) which should be 2^23 - 3 = 8388605 using Data.MemoCombinators. My code is: {-# LANGUAGE BangPatterns #-} import Data.MemoCombinators as Memo ack = Memo.memo2…
Cartesius00
  • 23,584
  • 43
  • 124
  • 195
16
votes
1 answer

Why is the Ackermann function related to the amortized complexity of union-find algorithm used for disjoint sets?

Can anybody give me an intuitive explanation of why the Ackermann function http://en.wikipedia.org/wiki/Ackermann_function is related to the amortized complexity of union-find algorithm used for disjoint sets…
Tianyang Li
  • 1,755
  • 5
  • 26
  • 42
14
votes
3 answers

Error in defining Ackermann in Coq

I am trying to define the Ackermann-Peters function in Coq, and I'm getting an error message that I don't understand. As you can see, I'm packaging the arguments a, b of Ackermann in a pair ab; I provide an ordering defining an ordering function for…
Mayer Goldberg
  • 1,378
  • 11
  • 23
8
votes
4 answers

Time Complexity of ackermann function

Does anybody know the time complexity to compute the ackermann function ack(m,n) in big-O notation or to which complexity class it belongs? Just Ack(3, n) would be also sufficient. I read somewhere it is NONELEMENTARY? Thanks. Code Snippet: public…
Thorben
  • 953
  • 13
  • 28
7
votes
1 answer

Understanding Grossman & Zeitman's algorithm for computing the Ackermann function?

I've read the paper An inherently iterative computation of Ackermann's function, published by Grossman & Zeitman in which they present an algorithm which optimizes Ackermann's function. We know that the Ackermann function produces the result in the…
April Crude
  • 117
  • 7
6
votes
1 answer

haskell - hyperoperation (ackermann) function, tetration

I'm trying to write a hyperoperation function in haskell. It's usually wrritten as ackermann(a,b,n) but for partial application purposes I think it makes more sense to put n first. As such I'm calling it hypOp n a b The form I've found most natural…
jon_darkstar
  • 16,398
  • 7
  • 29
  • 37
5
votes
1 answer

Why is the Inverse Ackermann function used to describe complexity of Kruskal's algorithm?

In a class for analysis of algorithms, we are presented with this pseudocode for Kruskal's algorithm: He then states the following, for disjoint-set forests: A sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET…
Ben Palmer
  • 131
  • 2
  • 12
5
votes
2 answers

Haskell slow to compute Ackermann 4 1?

Here's an old question from 7 months ago, when stack overflowers agreed that Haskell's inefficiency in computing the Ackermann function was due to a compiler error. Ackermann very inefficient with Haskell/GHC 7 months later, this appears to be…
Bret Fontecchio
  • 629
  • 7
  • 16
4
votes
5 answers

The Ackermann Function and Recursion

I've tried to write the recursive Ackermann function in Java. But I think I've gone very very wrong somewhere! Could anyone take a look, check and maybe point my in the right direction of correcting my code? Thanks! The issue I have with the code…
mino
  • 6,978
  • 21
  • 62
  • 75
4
votes
1 answer

Why is there such a massive difference in compile time between consteval/constexpr and template metafunctions?

I was curious how far I could push gcc as far as compile-time evaluation is concerned, so I made it compute the Ackermann function, specifically with input values of 4 and 1 (anything higher than that is impractical): consteval unsigned int…
Bridge
  • 105
  • 1
  • 8
4
votes
2 answers

It is possible to compute recursive ackermann(m,n) function with args m>=4 and n>=1 in python without exceeding max recursion depth?

It is possible to compute total computable recursive function ackermann(m,n) with arguments m>=4 and n>=1 in python without exceeding max recursion depth? def ackermann(m,n): if m == 0: return n+1 if n == 0: return…
madmax80
  • 171
  • 1
  • 14
4
votes
2 answers

Can this implementation of Ackermann function be called tail recursive?

I have written following code in C. Can we call it a tail recursive implementation? #include int ackermann(unsigned int *m, unsigned int *n, unsigned int* a, int* len) { if(!*m && *len == -1) { return ++*n; } else if(!*m && *len…
Shiv
  • 1,912
  • 1
  • 15
  • 21
4
votes
1 answer

How to calculate the number of recursive calls made to the Ackerman() function in C

I tried writing this code to calculate the Ackerman value and also the number of times the function is called. However, the counter is stuck at 0 all the time. Could you help me out? /* A(m,n) = n+1, if m==0 A(m,n) = A(m-1,1), if m>0 and…
Somnath Rakshit
  • 555
  • 1
  • 6
  • 17
4
votes
1 answer

Ackermann function don't work properly in C++

In my home work of Ackermann function I have solved the problem as following int main() { int y = ack(4,1); cout<<"ans is :::: "<< y; getch(); return 0; } int ack(int m, int n) { if(m == 0) { return n+1; } …
user1463637
1
2 3 4