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.
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!