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
Math / ScienceAlgorithms
Last Comment
khdani
8/22/2022 - Mon
NovaDenizen
This sounds like homework to me.
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?
khdani
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 ?
khdani
ASKER
the last line must be
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.
khdani
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
NovaDenizen
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?
I would add a set of parenthesis to make it unambiguous, but otherwise that looks right to me.
khdani
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
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?