Proving Ackermann's function is decidable through a Turing Machine

Question

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 
read n 
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?

Answer 1

I don't know whether your code is correct or not (I've only glanced at it, and it's fairly early in the morning), but it's very high-level. "Run a Turing machine" is not a primitive operation in a Turing machine. If you're happy to express it in a Turing-equivalent language, rather than in a Turing machine itself, then your task is much easier.

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.