Results 1 to 4 of 4

Math Help - Blank tape halting problem help

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    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 ??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. flaws in a tape
    Posted in the Statistics Forum
    Replies: 6
    Last Post: July 7th 2011, 09:43 AM
  2. paper tape problem 2
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 14th 2010, 06:55 AM
  3. Halting problem reduction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 27th 2009, 11:28 AM
  4. Is Halting Problem valid for P?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 28th 2008, 10:21 PM
  5. Algebra problem... drawing a blank
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 23rd 2007, 04:57 PM

Search Tags


/mathhelpforum @mathhelpforum