Avatar of khdani
khdani
Flag for Israel 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
Math / ScienceAlgorithms

Avatar of undefined
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 started with Experts Exchange in 2004 and it's been a mainstay of my professional computing life since. It helped me launch a career as a programmer / Oracle data analyst
William Peck
NovaDenizen

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?  
⚡ FREE TRIAL OFFER
Try out a week of full access for free.
Find out why thousands trust the EE community with their toughest problems.
khdani

ASKER
right, they should be unchanged
NovaDenizen

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

ASKER
you mean ~H[i, j] -> S[i, j, k] <-> S[i + 1, j, k]
Experts Exchange has (a) saved my job multiple times, (b) saved me hours, days, and even weeks of work, and often (c) makes me look like a superhero! This place is MAGIC!
Walt Forbes
NovaDenizen

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
ASKER CERTIFIED SOLUTION
NovaDenizen

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
GET A PERSONALIZED SOLUTION
Ask your own question & get feedback from real experts
Find out why thousands trust the EE community with their toughest problems.
khdani

ASKER
oh sorry, my mistake
your answer is correct too
⚡ FREE TRIAL OFFER
Try out a week of full access for free.
Find out why thousands trust the EE community with their toughest problems.