Results 1 to 2 of 2

Math Help - Can a Turing Machine(TM) know what square its at ?

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    Can a Turing Machine(TM) know what square its at ?

    For example, can a TM preform this simple task.

    Starting from an initial square, print a non-blank on the 10th square strictly to the right or left?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    A TM can keep track of its head position up to a finite limit through its internal state. For example, a machine can have 100 states (plus some). If it moves to the right, it changes from state n to state n + 1, and if it moves to the left, it changes from n to n - 1. However, if it moves beyond square 100, it can no longer keep track of its position.

    So yes, a machine can easily print a non-blank character on the 10th square to the right of the initial square.

    This sounds a lot like a finite automaton, but there is still a big difference. Yes, when the size of the input is not bounded from above, the machine eventually can't "know" precisely where it is located. However, the combination of the facts that, in addition to the internal state, a TM is guided by the current tape square, that a TM can write on the tape and that the tape is infinite makes it possible for TMs to perform all possible computations.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Non-polynomial Turing Machine
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: December 12th 2010, 12:04 AM
  2. Turing Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2010, 06:39 AM
  3. Turing machine
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 21st 2010, 07:17 AM
  4. Turing machine: help neeed
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: June 3rd 2008, 12:45 AM
  5. Turing Machine Problems
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 5th 2008, 11:27 PM

Search Tags


/mathhelpforum @mathhelpforum