Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
23 views

Tetration induction proof

Problem picture Picture of given ackermann function So far, I have $$A(3,n) = A(2,A(3,n-1))$$ and then using $$A(2,n) = 2 \uparrow \uparrow n$$ I arrive at. $$A(3,n) = 2 \uparrow \uparrow A(3,n-1)$$ ...
1
vote
2answers
47 views

Is it known for which pairs of integers Ackermann 's function is commutative?

I was recently writing test for checking the termination of programs and I wanted to write some difficult condition to verify so that the solver didn't use the if-condition to simplify the goal to ...
0
votes
0answers
40 views

Is there an equation $f(k,m,n)=n$ where $n$ is the number of applications of the Ackermann function needed?

Using the definition of the Ackermann function on page 247 of this paper, (sidenote, great paper): $$ \alpha(k,m,n) = \begin{cases} m+n, & k=1 \\ m, & n=1 \\ \alpha(k-1,m,\alpha(k,m,n-1)),&...
1
vote
1answer
28 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 ...
0
votes
1answer
291 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 ...
0
votes
1answer
47 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 ...
0
votes
1answer
96 views

Ackermann Function for $(2,n)$

I've learned the Ackermann Function in my CS class but the formula looks a bit off compared to the ones I see on Wikipedia or other websites. The formula I learned was: $$f(k,1)=2,$$ $$f(1,n)=n+2, n&...
1
vote
1answer
90 views

Am I properly using induction to prove this about the Ackermann function?

Using induction, I want to prove that $ A_0^{x-1}(1) = x $ for $ x > 0 $ where $$ A_m(n) = A(m, n) $$ and $$ A_m^k(n) = \underbrace{A_m(A_m(...A_m(n)...))}_\text{k A's} $$ After proving the base ...
5
votes
3answers
1k views

Ackermann function - how to calculate the number of times it calls itself

Purely for my own amusement I've been playing around with the Ackermann function. The Ackermann function is a non primitive recursive function defined on non-negative integers by: $A(m,n) = n+1$, if ...
1
vote
1answer
284 views

How to find Ackermann(3,n)?

{ y+1 if x=0; A(x,y)= { A(x-1,1) if y=0; { A(x-1,A(x,y-1)) otherwise So I was trying to prove A(3,y) = $2^...
2
votes
0answers
82 views

Reciprocal Ackermann series

I created a function $\eta(x)$ that was defined as $$\eta(x)=\sum_{n=0}^\infty \frac{1}{\operatorname{ack}(x,2,n)}$$ Where $\operatorname{ack}(x,y,z)$ is the original Ackermann function. From what I ...
3
votes
1answer
145 views

The Ackermann hierarchy vs. the fast growing hierarchy

Suppose we've defined the Ackermann hierarchy as follows: $$A_\alpha(n)=\begin{cases}n+1,&\alpha=0\\A_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\A_\beta(1),&n=0,\alpha=\beta+1\\A_\beta(A_\alpha(...
3
votes
0answers
44 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 ...
8
votes
1answer
310 views

Ackermann function $A(m, n)$, all nonnegative integer solutions to $A(m, n) = m + n$?

The Ackermann function $A(m, n)$ is given by the recursion$$\begin{cases} A(0, n) \overset{\text{def}}{=} n + 1 \\ A(m + 1, 0) \overset{\text{def}}{=} A(m, 1) \\ A(m + 1, n + 1) \overset{\text{def}}{=}...
2
votes
1answer
240 views

Proving Ackermann's function is decidable through a Turing Machine

I am aware that Ackermann's function is total and complete, meaning it is decidable for every input, regardless of how long it takes to compute the result. I'm doing a project in which I decided to ...
1
vote
1answer
88 views

Primitively recursive functions imply total and computable but not the other way around.

I'm doing a research paper on Ackermann's function and I came up across the claim that it is not a primitive function. Now I've gone through the proof as to why that's true. But then this other claim ...
4
votes
1answer
243 views

Which is bigger? $Ackermann(G_{64}, G_{64})$ or $G_{G_{64}}$ [duplicate]

I have been playing around with the Ackermann function a bit and realized that it gets very big very fast. (Im going to use $A$ for $Ackermann$ throughout this question) Already $A(5,1)$ is (...
1
vote
1answer
91 views

Help With a proof involving the Ackermann function!

So, I'm continuing on with this computability text by Cutland, and I've reached the Ackermann function. Cutland says he will give a more rigorous proof that the function is computable later on, but ...
1
vote
1answer
63 views

Explaining the Ackermann function as A: $\mathbb N \times \mathbb N \rightarrow \mathbb N$

We have the following variation of the Ackermann function: $$A(0,m) = m+1$$ $$A(n,0) = \begin{cases}1, & \text{if } n=0 \\ 2, & \text{if } n=1 \\ 0, & \text{if }n=2 \\ 1, & \text{...
4
votes
2answers
487 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 ...
3
votes
1answer
121 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 $ ...
0
votes
0answers
71 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 ...
2
votes
2answers
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? ...
3
votes
2answers
988 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 ...
3
votes
1answer
232 views

Properties of Ackermann's function

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)...
5
votes
1answer
505 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 ...
5
votes
2answers
847 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 ...
4
votes
1answer
113 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...
3
votes
2answers
193 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 ...
2
votes
1answer
221 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 ...
2
votes
3answers
850 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 ...
10
votes
0answers
179 views

Which digit occurs most often?

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 ...