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$ – David Richerby Apr 27 '14 at 21:55
  • $\begingroup$ A single one-way infinite tape I think. Is it decidable by the way described in that other question? $\endgroup$ – user1360909 Apr 27 '14 at 21:57
  • $\begingroup$ Yes, that's how to show it's decidable. $\endgroup$ – David Richerby Apr 27 '14 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$ – user1360909 Apr 27 '14 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.