2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Where do your conditionals end? Indentation helps! $\endgroup$
    – celtschk
    Nov 27, 2016 at 9:27
  • $\begingroup$ @celtschk Sorry I'll indent it properly!!! $\endgroup$ Nov 27, 2016 at 10:31
  • $\begingroup$ 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. $\endgroup$ Nov 27, 2016 at 21:15
  • $\begingroup$ @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. $\endgroup$ Nov 28, 2016 at 0:09

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So let me see if i understand this correctly. In order to prove that the function is decidable I need to code up the Tm and implement it using a stack to hold m, and n-1. That much I understand but, by implementing and running the function through my TM it would tell me if it halts or not right ? So I don't understand the need to further prove, with structural induction that it does indeed halt. Could you clarify that a little for me. What does running list(m,n) initially do ? $\endgroup$ Nov 27, 2016 at 10:45
  • $\begingroup$ Determining whether an arbitrary TM halts is in general impossible, so you need some specific reason why this one should always halt. "I ran it for some inputs and it halted" is not sufficient; I don't see how you're proving that it always halts. list(m,n) simply puts the values m and n onto the stack - for example, the tape might have two possible symbols 0 and 1. Then list(m,n) might write 111…10111…1, where there are m 1's then a 0 then n 1's. (That's only one way of coding up a list of integers; there are much more efficient ways.) $\endgroup$ Nov 27, 2016 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .