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.
63
questions
0
votes
0
answers
45
views
Is it true that "A function is primitive recursive iff the order needed to prove the induction is at most $\omega$ ."
At the end of this question a user states
A function is recursive primitive iff the order needed to prove the induction is at most $\omega$.
Intuitively this makes sense, but is it true? Ackerman is ...
9
votes
3
answers
4k
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 ...
1
vote
0
answers
28
views
Are all binary operations on this binary tree distinct?
Consider the set $\mathbb{Z}_+$ of positive integers $\{1,2,3,4,...\}$. Consider the binary operation $*$ of exponentiation on that set. I now define an infinite binary tree, constructed recursively ...
0
votes
0
answers
91
views
Solve $^y{x} =$ $^x{y}$ over the real numbers
Let $x, y \in \mathbb{R}^{+}$ be such that $x \neq y$ and assume $n \in \mathbb{N}-\{0\}$.
Now, referring to the well-known hyperoperation sequence $x[n]y$, we have that $x[1]y=x+y$ and we know that ...
0
votes
1
answer
77
views
Is Ackermann's Function Bijective?
I have been trying to understand the more rigorous side of mathematics and especially functions, and I came across Ackermann's Function recently. I was wondering if A(x,y) is bijective among the ...
25
votes
4
answers
13k
views
Ackermann Function primitive recursive
I am reading the wikipedia page on ackermann's function, http://en.wikipedia.org/wiki/Ackermann_function
And I am having trouble understanding WHY ackermann's function is an example of a function ...
1
vote
1
answer
118
views
Is this double recursion necessarily primitive recursive?
Suppose $f,g,h : \mathbb{N} \rightarrow \mathbb{N}$ are primitive recursive functions. Consider the function $\phi : \mathbb{N}^2 \rightarrow \mathbb{N}$ recursively defined as follows.
$$
\phi(0,n) = ...
4
votes
1
answer
245
views
Can you define functions which are not primitive recursive, yet total, in Type Theory? [closed]
Ackermann's function is total but not primitive recursive.
Can one define Ackermann's function in Type Theory,
ie:
Can you define functions which are not primitive recursive, yet total, in Type Theory?...
2
votes
1
answer
123
views
Understanding recursion over higher order types
I'm reading this answer which defines Ackermann function via higher order recursion https://mathoverflow.net/a/47098
First we define an iteration function $g\colon\mathbb{N}\times\mathbb{N^N}\to\...
1
vote
4
answers
91
views
Finding formulas for a recursive function from $\Bbb{N} \times \Bbb{N}$ to $\Bbb{N}$
Define $B: \Bbb{N} \times \Bbb{N} \to \Bbb{N}$ by the recursive formula:
$$B(0,x) = x+1$$
$$B(y+1,0) = B(y,1)$$
$$B(y +1,x +1) = B(y, B(y +1,x))$$
The assignment asks me to find simple formulas for $B(...
0
votes
0
answers
137
views
Show that the Ackermann function is primitive recursive for every $x \in \mathbb{N}$
Show that for every $x \in \mathbb{N}$ the function $A_x(y) = A(x,y)$ is primitive recursive, with $A(x,y): \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ being the Ackermann function
I need some ...
1
vote
0
answers
47
views
Confusing recursive function definition
I'm reading through https://plato.stanford.edu/entries/recursive-functions/ and came across a confusing part:
One means of doing so is to first use recursion on the type ℕ→ℕ—a
simple form of ...
0
votes
1
answer
157
views
Ackerman function
I have a very elementary question:
here
on the page 7, 4th line
why
$$ A_{k+1} (n+1) = A_k (A_{k+1} (n))$$
Is it trivial or do we need induction ?
0
votes
2
answers
257
views
A sequence that grows faster than the ackermann function?
Ackermann's function and all the up-arrow notation is based on exponentiating. We know for a fact that the factorial function grows faster than any power law so why not build an iterative sequence ...
0
votes
1
answer
296
views
Tetration induction proof
The triple arrow-up denotes power towers in which the number of levels themselves is a power tower with a number of levels that is a power tower, and so on. For example,
$$\begin{align}
a\uparrow\...
4
votes
2
answers
350
views
Generalized Recursion vs. Turing Completeness
$\newcommand{\NN}{\mathbb N}\newcommand{\UU}{\mathcal U}$I'm currently reading through Homotopy Type Theory: Univalent Foundations of Mathematics. In Exercise 1.10, we construct the Ackermann function ...
1
vote
1
answer
164
views
Prove that $\operatorname{ack}(3,y)=2^{y+3}-3$.
Prove that:
$$\operatorname{ack}(3,y)=2^{y+3}-3$$
where $\operatorname{ack}$ refers to the Ackermann function.
Here's what I have so far.
This statement can be prove by induction over $y$.
Induction ...
1
vote
2
answers
601
views
Ackermann Function: Proof that n < A(m, n) for all m, n in N
I've been stuck at this problem for a while now and can't get it solved. The prof wants me to proof n < A(m,n) for all m and n being positive Integers.
More details on the Ackermann Function:
$$(1) ...
0
votes
2
answers
178
views
Closed form of inverse Ackermann function for $kx$, such as $\alpha(kx) = f(k) \alpha(x)$ or $\alpha(kx) < f(k) \alpha(x)$?
Let Ackermann function $A(m,n)$ be defined as
\begin{align}
&A(0,n) = n+1,\\
&A(m+1,0) = A(m,1),\\
&A(m+1,n+1) = A(m, A(m+1,n)),~n,m\in \mathbb{N},\\
\end{align}
and the inverse Ackermann ...
1
vote
1
answer
387
views
Show the original Ackermann function is non-primitive recursive
There are a couple of questions here which show that the modern Ackermann function $A(i, x)$ is not primitive recursive. This new Ackermann function defined by Péter is a simplification of the ...
2
votes
1
answer
253
views
How to get the last $n$ digits of Ackermann function?
The Ackerman function is defined as follows:
$$A(m,n)=
\begin{cases}
n+1,& m= 1\\
A(m-1,1), & m>0, n=0\\
A(m-1, A(m,n-1)), &m,n>0
\end{cases}$$
Is it possible to get the last ...
1
vote
0
answers
92
views
Where to find/what is full μ-expression for Ackermann function?
Can you point me to full description of the Ackermann function in terms of standard μ-opertor and primitive recursion? I understand that to define it completely down to primitive terms (numerals, ...
6
votes
1
answer
89
views
Question about unclear definition of Ackermann-Péter function in Stanford Encyclopedia of Philosophy
I'm reading Recursive Functions at Stanford Encyclopedia of Philosophy (section 1.4). The following paragraph defines function β which is then used to define variant of Ackermann-Péter function:
What ...
4
votes
1
answer
260
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 ...
2
votes
1
answer
204
views
Proving a modified Ackermann function using induction
So I have 2 functions:
$$
a(0,y) = y+ 1\\
a(x, 0) = a(x-1,1)\\
a(x,y) = a(x-1,a(x,y-1))
$$
And:
$$
c(0,n) = 0\\
c(1,n) = n^2 + n +1\\
c(m,0) = c(m-1,1)\\
c(m,n) = c(m-1,c(m,n-1))
$$
And then I have:...
3
votes
1
answer
519
views
Ackermann function in terms of higher order recursion
Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition
\begin{equation*}
A(m,n)=\left\{
\begin{array}{ll}
n+1 & \text{if $m=0$} \\
A(m-1,...
0
votes
3
answers
5k
views
Ackermann function
I have trouble with a question i need to use the function of Ackermann, I need to show that Ack(2,3) = 9.
...
8
votes
2
answers
381
views
Ackermann function and $f_\omega$
The Wikipedia page of Ackermann function states that Ackermann function is "roughly comparable" to $f_\omega$ in fast-growing hierarchy.
Is there some standard way to make the "roughly comparable" ...
2
votes
2
answers
415
views
Ackermann-Péter Function: Proof by induction, power tower
So I have this Ackermann function:
$$
A(0,y) = y+ 1\\
A(x, 0) = A(x-1,1)\\
A(x,y) = A(x-1,A(x,y-1))
$$
And I have another function:
$$
d(n) = 2^{2^{.^{.^{.^{.^{2}}}}}}
$$
while the height of the ...
0
votes
0
answers
33
views
Non-primitive recursive functions [duplicate]
For my school project i have chosen to do analyze Ackermann function as well as other functions that are recursive but not primitively recursive. I cannot seem to find good material on this, what i ...
1
vote
1
answer
1k
views
Ackermann Function: Prove that $A(m, n + 1) > A(m, n)$ whenever $m$ and $n$ are nonnegative integers.
So I've been trying to solve the exercises out of Discrete Mathematics and Its Applications by Kenneth H. Rosen, and found myself to be stuck at this problem for quite a long time. The Ackermann ...
9
votes
2
answers
814
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}}{=}...
3
votes
0
answers
346
views
Ackermann function is not primitive recursive [duplicate]
The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$
I want to show that the function of ackermann is primitive ...
1
vote
1
answer
128
views
Just how slowly does $\alpha^*(n)$ grow?
In his paper Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture, Seth Petrie proves that a particular series of operations on a splay tree take amortized time $\alpha^*(n)$, where $\...
5
votes
0
answers
126
views
Extending Knuth up-arrow/hyperoperations to non-positive values [duplicate]
So... I had the silly idea to extend Knuth's up-arrow notation so that it included zero and negative arrows. It is normally defined as $$\begin{align*} a \uparrow b & = a^b \\ a \uparrow^n b & ...
0
votes
2
answers
3k
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 ...
2
votes
2
answers
206
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 ...
0
votes
0
answers
60
views
Is there an equation $f(k,m,n)=n$ where $n$ is the number of applications of the Ackermann function needed? [duplicate]
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)),&...
3
votes
1
answer
594
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)...
1
vote
1
answer
349
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{...
1
vote
1
answer
224
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 ...
1
vote
2
answers
81
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 ...
1
vote
1
answer
204
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
1
answer
97
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
1
answer
805
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&...
8
votes
3
answers
9k
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
1
answer
1k
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^...
1
vote
0
answers
170
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
1
answer
546
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(n-...
2
votes
3
answers
2k
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 ...