# Questions tagged [ackermann-function]

An example of a total computable function that is not primitive recursive; appears in the literature in many variants. The original three argument variant can be used to define the Ackermann numbers.

33 questions
39 views

### proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values

my question is involving the Ackermannfunction. Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following ...
38 views

36 views

### Ackermann function property for positive $n$

Ackermann's function is: $A(0,y) = y + 1$ $A(x+1,0)= A(x,1)$ $A(x+1,y+1)= A(x,A(x+1,y)$ which is a total computable function but not a primitive recursive one. Why is the following property ...
374 views

### Ackermann function proof by Induction

I'm currently studying discrete mathematics and i've been given an assignment to prove the following: $A(1, n) = n +2$ for all $n \geq 0$ with induction. But i am somewhat unsure if i've done it ...
49 views

### Ackermann Function for $f(2,n)$ as compared to $f(5,1)$

I started learning the Ackermann Function in my CS class and we started off with $$f(5,1)=2$$ or $$f(5,2)=f(4,f(5,1))=f(4,2)=f(3,f(4,1))=f(3,2)=f(2,f(3,1))=f(2,2)=f(1,f(2,1))=f(1,2)=4$$Then we had to ...
125 views

45 views

### Is there an “efficient” algorithm to compute hyperexponentation?

Preface: understand that this should all be modulo some fixed $m$; otherwise the numbers become so ridiculously large that the question makes no sense. That said, I'll leave $m$ off the notation to ...
316 views

550 views

### Mathematically, how does one find the value of the Ackermann function in terms of n for a given m?

Looking at the Wikipedia page, there's the table of values for small function inputs. I understand how the values are calculated by looking at the table, and how it's easy to see that 5,13,29,61,125 ...
131 views

### Prove $A(x,y)= 2[x](y+3)-3$. Where A is the Ackermann-Peter function and [x] is x-th hyperoperator.

I've successfully proven $A(x,y)$ for some fixed x and any y with induction but I'm having a hard time proving this for any x and y. I think the next useful step would be proving $A(x,0)= 2[x]3-3$ ...
80 views

### Is it true that Ackermann's function cannot be implemented without recursion? [duplicate]

Yesterday I got sucked into a bingewatch of Computerphile's and Numberphile's videos on youtube. In particular I ended up watching some on Ackermann's function. While I knew already this function (and ...
40 views

### The number of logarithm applications to get from n below 1

Let $L(n)$ to be a number of logarithms that you need to apply on $n$ until you get below 1: $$0 \leq \log\cdots\log n < 1 \\ \uparrow \\ L(n)\mbox{-times}$$ Is there a name for this function? ...
1k views

### Ackermann's function is $\mu$-recursive

In my book there is the following proof that Ackermann's function is $\mu$-recursive: We propose to show that Ackermann's funcition is $\mu$-recursive. The first part of the job is to devise a ...
I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)... 1answer 533 views ### The Ackermann's function “grows faster” than any primitive recursive function I am looking at the proof that the Ackermann's function is not primitive recursive. At the part: "We will prove that Ackermann's function is not primitive recursive by showing that it "grows ... 2answers 890 views ### Example$x$,$y$and$z$values for$x\uparrow^\alpha y=z$where$\alpha\in \Bbb R-\Bbb N\uparrow^n$and$G(n,\cdot,\cdot)$are notations for hyperoperation. http://en.m.wikipedia.org/wiki/Hyperoperation$n$is the hyperoperations rank. Can example$x$,$y$and$z$values be provided ... 1answer 116 views ### Ackermann Function - Book recommendation What books would you recommend me for the topic "Ackermann Function" ?? I will have a presentation at the end of the semester for this topic and I would get some information... 2answers 222 views ### Most “simple”$\mu$-recursive function that is not primitive recursive Maybe the most prominent example of a$\mu$-recursive function that is not primitive recursive is the Ackermann function. But writing it out as a$\mu$-recursive function ("breaking it all the way ... 1answer 223 views ### Growth rate of$f(f(n))$, where$f(n)$is the ackermann-function. Let $$f(n)\ :=\ n \uparrow^n n$$ and $$g(n)\ :=f(f(n))\ =\ f(n)\uparrow ^{f(n)} f(n)=n\uparrow^n n \uparrow^ {n \uparrow ^n n} n\uparrow ^n n$$ So,$g(n)$is$f(n)$applied twice. What is the ... 3answers 885 views ### Is the inverse ackermann function the slowest growing function that goes to infinity? Actually, this is not precisely my question. If$a(x)$is the inverse ackermann function, then obviously$a(a(x))$grows slower than$a(x)$, as does$\log(a(x))\$, and so on. But is there a function f ...
Is there any method to calculate, which digit occurs most often in the number $$4 \uparrow \uparrow \uparrow \uparrow 4\ ,$$ the fourth Ackermann-number ? Or would it be necessary to calculate the ...