# 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
Math / ScienceAlgorithms

Last Comment
khdani

8/22/2022 - Mon

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

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

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

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?
khdani

right, they should be unchanged

So there should be an equivalence within the right part.
khdani

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.
khdani

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