khdani

asked on

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