# 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 prove that the function is decidable through a Turing Machine that I designed.

I also don't know if I designed this TM correctly.

So Ackermann's Function is defined as $A=(m,n)$, where m,n are non-negative integers, such that $(m,n)$ are defined by the following:

\begin{cases} n+1 & m=0 \\ A(m-1,1) & m>0 ,n=0 \\ A(m-1,A(m,n-1) & m>0 , n>0 \end{cases}

So, following the instructions above I came up with a pseudocode for a TM that would tell me if the function is decidable, here's what I have:

read m
if m = 0
write n+1 into A
halt
if m > 0 and if n = 0
write m-1 to m in another TM
write 1 to n in another TM
run other TM
copy A from other TM to A
halt
if m>0 and n>0
write m to m in another TM
write n-1 to n in another TM
run other TM
copy A from other TM to A
write m-1 to m in another TM
write A to n in another TM
run other TM
copy A from other TM to A
halt


can someone tell me if this looks about right? Also, how does one decide what the initial values for the 0's and 1's are on the tape? Or are they just randomly placed?

• Where do your conditionals end? Indentation helps! Nov 27, 2016 at 9:27
• @celtschk Sorry I'll indent it properly!!! Nov 27, 2016 at 10:31
• Your "code" is essentially a literal transcription of the definition of the function. There is exactly one key point in implementing the Ackerman function: doing the recursive calls — and you hand-waved yourself out of that. You should read up a bit on how to do recursion in a TM. Nov 27, 2016 at 21:15
• @MarianoSuárez-Álvarez It seems that the whole notion of creating a TM is a little big ambiguous to me. I have read what I could find on it and I still don't quite understand it well. If you look here link on page 151, you will see what I eventually want to be able to do for the function in hand. Nov 28, 2016 at 0:09

Instead, you could implement a stack, and push $m, n-1$ to the stack; then set your TM up so that at the start of execution, it seeks to the top of the stack, then reads the top two numbers from the stack. On completion, the TM should write its output to the tape, replacing the top two numbers of the stack. Then the operation "run a copy of myself" is just "run myself from the beginning" (or goto start state), because the TM will only consume the top two values and replace them with the output.
You're reading $m$ and $n$ at the start, so the initial value on the tape should be $\mathrm{list}(m, n)$, where $\mathrm{list}$ is some function that expresses arbitrary lists of naturals as a single natural. (Then your TM should contain code to interpret that initial value correctly as a list.)
Do remember that you need to prove that your TM halts, in order to show that Ack is decidable. For that, you'll need structural induction on $\mathbb{N}^2$ in lexicographic order.