The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive.

Is it decidable whether a TM reaches some position on the tape?

I think it's a slightly different question though (?) and so I have tried to show that it isn't recursive by reduction from the halting problem.

Ignore the below if it is recursive!

So for an instance of the Halting problem we can use 2 tape TM M' as follows:

on input (code(M)code(x)) to M'

  • M' copies code(x) to tape 2
  • M' simulates M on tape 2
  • If M halts on the input x then......

I am not really sure what to do now. I thought that I could get M' to only enter a certain cell if M halts on x and then use this to show that if we could decide the problem above then we could decide the Halting problem (by seeing if M' enters that particular cell)

But I am not sure what cell I can use to guarantee that it won't have already been entered? The two tape thing is kind of confusing me -do I need to pick a cell that won't be entered on either tape 1 or tape 2?

Any help appreciated!

  • $\begingroup$ What exact definition of Turing machines are you using? If there's a single, one-way infinite tape, this is decidable. If there is a single two-way infinite tape or more than one tape, it's undecidable. $\endgroup$ Apr 27, 2014 at 21:55
  • $\begingroup$ A single one-way infinite tape I think. Is it decidable by the way described in that other question? $\endgroup$ Apr 27, 2014 at 21:57
  • $\begingroup$ Yes, that's how to show it's decidable. $\endgroup$ Apr 27, 2014 at 21:58
  • $\begingroup$ Thank you. So does my proof not work because there is no cell that you can guarantee won't be entered? $\endgroup$ Apr 27, 2014 at 21:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.