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.
65
questions
2
votes
0
answers
76
views
the Ackermann function must be total and unique based on one specific list of rules
This is one following question based on one question I asked before.
In mcs.pdf, it has Problem 7.25 in p251(#259).
One version of the the Ackermann function $A:\mathbb{N}^2 \to \mathbb{N}$ is ...
- 416
0
votes
1
answer
84
views
partial function version of the Ackermann function must be total
In mcs.pdf, it has Problem 7.25. (I only solve somewhat important problems referred to in the chapter contents because I have learnt one Discrete Mathematics book before and read mcs to ensure no ...
- 416
0
votes
0
answers
46
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 ...
- 1,027
1
vote
0
answers
29
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 ...
- 21.4k
0
votes
0
answers
92
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 ...
- 1,160
0
votes
1
answer
82
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 ...
1
vote
1
answer
135
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) = ...
- 6,610
3
votes
1
answer
136
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\...
- 173
0
votes
0
answers
146
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 ...
- 301
1
vote
0
answers
48
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 ...
4
votes
1
answer
257
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?...
- 140
0
votes
1
answer
163
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 ?
- 3,978
0
votes
2
answers
275
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 ...
- 431
4
votes
2
answers
377
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 ...
- 719
1
vote
1
answer
209
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,928