# Thread: Blank tape halting problem help

1. ## Blank tape halting problem help

show that there is no turing machine(TM) which given our encoding of any TM M as input will eventually halt outputting 1 if M started on a blank tape ever prints A, and outputting 0 if M started on a blank tape never prints the symbol A.

Is the best way to answer this question using a flow diagram eg

start( input encoding of M and encoding of tape T)
then ( construct encoding of M', which given our blank tape, first which converts it to T then runs M on it) then (would M' started on a BT ever halt)

ythen out put 1 or 0 if no.. but since this is the Blank tape halting problem, it leads us to a contradiction.. hence no TM exist ??

2. ## Re: Blank tape halting problem help

start( input encoding of M and encoding of tape T)
then ( construct encoding of M', which given our blank tape, first which converts it to T then runs M on it) then (would M' started on a BT ever halt)

ythen out put 1 or 0 if no..
If I understand correctly, you are reducing the halting problem to this one. I agree with the general idea, but the description needs to be a little more precise. For example, currently it does not mention the symbol A.

So, suppose that there is a Turing machine P' that solves the problem from the OP, i.e., given the code of a machine M', P' outputs 1 if M' ever prints A starting with a blank tape, and P' outputs 0 otherwise. Then we can write a machine P that solves the halting problem, as follows. Suppose P is given a machine M and a tape T. We may assume that M and T do not use A. P converts M and T into a machine M' that, starting with a blank tape, writes T and passes control to M. In addition, if M terminates, M' outputs A. This way, M terminates on T iff M' ever prints A. After converting M and T into M', P runs P' on M'. Then P outputs 1 if M terminates on T, and P outputs 0 if M does not terminates on T, i.e., P solves the halting problem.

3. ## Re: Blank tape halting problem help

oh yes i mention in it my flow diagram to be percise. But is a flow diagram sufficint to answer this question?

4. ## Re: Blank tape halting problem help

But is a flow diagram sufficint to answer this question?
This depends on your course. As long as the machine is specified in sufficient detail, I don't see why not.