1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean expressions for Turing Machine

  1. Feb 17, 2010 #1
    I want to express Non-Deterministic Turing Machine constraint with boolean expression.
    The constraint is: "Cells which aren’t being read remain the same at time t+1".
    lets say H[i,j] means the read/write head at time i at cell j
    and S[i,j,k] means the symbol k at time i in cell j

    so the expression would be:
    ~H[i,j] ^ ~S[i,j,k] -> ~S[i+1,j,k]

    which equivalent to
    H[i,j] V S[i,j,k] V ~S[i+1,j,k]

    is this correct ?
    i saw in many lecture notes in the web very different expressions, so i'm confused for what's correct.

    Thank You
  2. jcsd
  3. Feb 17, 2010 #2
    I don't understand the algebra. H and S are range variables, aren't they? If so, how do you obtain the truth value of H when H=12, for instance?
  4. Feb 17, 2010 #3
    H and S are 2D and 3D arrays
    H[i,j] is TRUE if the read/write head at time i is scanning cell j, else FALSE
    S[i,j,k] has symbol k at time i in cell j
  5. Feb 17, 2010 #4

    By your definition S[i,j,k] = True always, and S[i+1,j,k] = False always.

    But i,j, and k are random variables aren't they? If so S[2,2,3] = True and S[1+1,2,3]=False. This is an immediate contradition.
  6. Feb 17, 2010 #5
    no it's not,
    more precisely, [tex]0 \leq k \leq[/tex] |[tex]\Sigma[/tex] | - 1, where
    [tex]\Sigma[/tex] is the alphabet.

    so S[i,j,k] means at time i, the contents of tape square j is symbol [tex]s_{k}[/tex]

    and [tex] 0 \leq i \leq p(n) [/tex] and [tex] -p(n) \leq j \leq p(n) [/tex]

    where n is input's length,
    lets say the input string is x, then [tex] x = s_{1} \cdot s_{2} \cdot ... \cdot s_{k} \cdot ...\cdot s_{n}[/tex]
  7. Feb 17, 2010 #6
    Back up a minute. Is S[i,j,k] always true?
  8. Feb 17, 2010 #7
    no, it's true if cell j contains symbol [tex]s_{k}[/tex] at time i
  9. Feb 17, 2010 #8
    I believe your problem with this is the notational conventions in use. Though, nearly universally, i,j and k are random variables.

    You might try to decipher what objects are treated as constants and what are treated as variables in any given assignments.

    I'm afraid my time is up for tonight.
  10. Feb 17, 2010 #9
    i,j,k are not random variables
  11. Feb 25, 2010 #10
    You are confused as to what constitutes a logical statement.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Boolean expressions for Turing Machine
  1. Turing machine problem (Replies: 1)

  2. Turing machine help! (Replies: 0)

  3. Boolean Expressions (Replies: 1)

  4. Boolean expression (Replies: 17)