Boolean Expression for Turing Machine
Hello,
I want to express Non-Deterministic Turing Machine constraint with boolean expression.
lets say H[i,j] means the read/write head at time i at cell j
and S[i,j,k] means the symbol sk at time i in cell j
The constraint is: "Cells which aren’t being read remain the same at time t+1".
how can I describe it with boolean expression ?
Thank You
I want to express Non-Deterministic Turing Machine constraint with boolean expression.
lets say H[i,j] means the read/write head at time i at cell j
and S[i,j,k] means the symbol sk at time i in cell j
The constraint is: "Cells which aren’t being read remain the same at time t+1".
how can I describe it with boolean expression ?
Thank You
ASKER
i've been thinking may this be correct:
~H[ i, j] ^ ~S[i , j ,k] -> ~S[i+1, j, k]
which equivalent to
H[i, j] v S[i, j, k] -> ~S[i+1, j, k]
is it correct ?
~H[ i, j] ^ ~S[i , j ,k] -> ~S[i+1, j, k]
which equivalent to
H[i, j] v S[i, j, k] -> ~S[i+1, j, k]
is it correct ?
ASKER
the last line must be
H[i, j] v S[i, j, k] v ~S[i+1, j, k]
H[i, j] v S[i, j, k] v ~S[i+1, j, k]
I'm not clear about the precedence and associativity of the answers you have put forward.
I also think you need a <-> between S[i,j,k] and S[i+1,j,k] because they will be the same. You're almost there.
I also think you need a <-> between S[i,j,k] and S[i+1,j,k] because they will be the same. You're almost there.
ASKER
i would disagree with you, because <-> means equivalence and -> means implication, left part isn't equivalent to right part but logically implies the right part
Yes. An implication is necessary. But you're trying to say that all the spots that are not being read by the head will remain equivalent between the two time steps, right?
ASKER
right, they should be unchanged
So there should be an equivalence within the right part.
ASKER
you mean ~H[i, j] -> S[i, j, k] <-> S[i + 1, j, k]
I would add a set of parenthesis to make it unambiguous, but otherwise that looks right to me.
ASKER
the problem with what you suggested is that, if we transform it to SAT expression we get
H v ~(S1 xor S2)
when H = F means the head is not at cell j at time i, and S1 = T and S2 = F means the cell has changed the whole expression will evaluate to TRUE which is incorrect.
I think the correct answer is
~H[i, j] -> ( S[i, j, k] ^ S[i + 1. j. k] )
in this case it would evaluate to FALSE as should be
H v ~(S1 xor S2)
when H = F means the head is not at cell j at time i, and S1 = T and S2 = F means the cell has changed the whole expression will evaluate to TRUE which is incorrect.
I think the correct answer is
~H[i, j] -> ( S[i, j, k] ^ S[i + 1. j. k] )
in this case it would evaluate to FALSE as should be
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
oh sorry, my mistake
your answer is correct too
your answer is correct too
Break it out into an implication. for all i, j, k, when condition X is true condition Y must be true. What are conditions X and Y?