Results 1 to 3 of 3

Math Help - Turing machine notation for not on multiple symbols

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Turing machine notation for not on multiple symbols

    I am trying to draw a Turing Machine diagram where I have a state and I go to one state if the current symbol pointed to by the head is an a or b, so I have (a, b) on that edge. I need another transition for when it's not a AND not b to go to another state. I don't want to label the edge as (!a, !b) as I think this makes my machine non-deterministic since technically a would be !b and could follow this transition, same with b and !a. I am not able to find common notation for something like this. All the examples I find show a single symbol transition of something like a and then !a, but not multiple symbols like my case. Thanks for any advice.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Turing machine notation for not on multiple symbols

    There is no general accepted format for turing machine state notation, so you will need to consult your book or notes for the course (if this is for a course).

    One typical method is to denote the transition from one state to another with an arrow labeled by one or more conditions which cause that state transition: 0/1,R would mean it only transitions on zero, and when it does, it changes 0 to 1 and moves right on the tape. I would list them separately on the arrow or draw two arrows, as a/X,Y and b/X,Y, where X,Y are the new symbol and motion of the scanner.

    If you need to limit space and your instructor doesn't care about formatting, I guess you could do it like this:

    Arrow 1 label: (A \vee B)/X,Y
    Arrow 2 label: \neg (A \vee B)/X,Y
    Alternative arrow 2 label: ( \neg A \wedge \neg B)/X,Y

    These are mutually exclusive so it is still deterministic. (Though non-determinism is not your only problem; you define the wrong machine the way you describe.)

    EDIT: Note that if you're not changing the symbol on the tape to the same thing each time you pass it, you'll want to write those transitions separately or come up with a way to express "no change" as a symbol, maybe using a dash, or something else not in (alphabet \cup blank).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Turing machine notation for not on multiple symbols

    I agree that there are no standard notations for Turing Machines. I would denote a transition corresponding to not a and not b as \overline{\{a,b\}} or just \overline{a,b}. You could also use proper set-theoretic notations like \Sigma-\{a,b\}. But in any case I would add a note explaining the notation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Can a Turing Machine(TM) know what square its at ?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 17th 2011, 10:41 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 notation: sigma-star
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 8th 2010, 01:56 PM
  5. turing machine to accept a certain set
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 17th 2009, 02:15 PM

Search Tags


/mathhelpforum @mathhelpforum