Results 1 to 2 of 2

Math Help - Help on a Turing Machine Question

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    8

    Help on a Turing Machine Question

    Hello,
    Can someone please help me with this question ?

    Show that for each Turing Machine, M, there is a Turing Machine, M', which computes the same partial function as M, but which never moves left of the initially scanned square of any initial tape.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jessica.M View Post
    Hello,
    Can someone please help me with this question ?

    Show that for each Turing Machine, M, there is a Turing Machine, M', which computes the same partial function as M, but which never moves left of the initially scanned square of any initial tape.
    It does depend on how the TM is defined, I will assume that the initial tape
    consists of a sequence of cells with a number of 1's and the rest of the tape
    blank and the reading head over the left most non-blank cell.

    Suppose the reading head of TM M moves a maximum of X cells to the left of
    the initial position. Then consider a TM M' that moves the block of 1's X+1
    cells to the right (show this need never move to the left of the initial
    position), then positions the reading head over the leftmost non blank cell
    and then executes M.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing Machine Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2011, 12:14 PM
  2. Turing Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2010, 07:39 AM
  3. LOOP Turing machine
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 24th 2010, 05:15 PM
  4. Turing machine
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 21st 2010, 08:17 AM
  5. turing machine to accept a certain set
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 17th 2009, 03:15 PM

Search Tags


/mathhelpforum @mathhelpforum