Results 1 to 4 of 4

Math Help - Turing Machine Problem

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    Turing Machine Problem

    Show that for each TM
    M there is a TM M'which computes the same partial
    function as
    M, but which never moves left of the initially scanned square of

    any initial tape?


    Honeslty, I don't get what the question is asking me.


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    I think the question is pretty clear. Be sure to read the description of Turing machines used in your course.

    Basically, a TM with a two-way infinite tape can be simulated by a TM with two tapes that are infinite only to the right. The portion of the original TM's tape from the initial square to the left is modeled by one tape, and the portion from the initial square to the right is modeled by the second tape. In turn, a two-tape machine can be simulated by a one-tape machine. This should be described in most books about the subject, for example, in Elements of the Theory of Computation by Lewis and Papadimitriou.

    If you still have questions about the formulation of the problem, please specify which terms or concepts are not clear.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    54
    Can you show me an example? Also how do I set out an answer?

    My understanding of the question goes like this, There is a TM M, which computes a partial funtion, but what we want is a TM M' which computes the same partial function BUT never moves left of the initially scanned square.

    How would I set out my answer?

    Can I make an example?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    When proving something about Turing Machines, it is often almost impossible to write down all the details because constructing TMs for complicated computations is extremely laborious and tedious. Besides, writing a concrete TM adds little to intuitive understanding of what is going on. As a result, most proofs about TMs are hand-waving, though good proofs are still able to convince others who had enough experience with such hand-waving. This reminds me somewhat of religious traditions that are not precisely written down the way scriptures are (and, some claim, cannot be written down precisely), so that the only way to master them is to practice them under the supervision of experts.

    I'll PM you a text describing how a two-way infinite TM can be simulated first by a one-way infinite TM with two tapes and then by a one-way infinite TM with one tape.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2010, 06:39 AM
  2. Turing machine
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 21st 2010, 07:17 AM
  3. Turing machine: help neeed
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: June 3rd 2008, 12:45 AM
  4. Turing Machine Problems
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 5th 2008, 11:27 PM
  5. Help on a Turing Machine Question
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: March 23rd 2008, 03:41 AM

Search Tags


/mathhelpforum @mathhelpforum