Boolean expressions for Turing Machine


by insectosaurus
Tags: boolean, expressions, machine, turing
insectosaurus
insectosaurus is offline
#1
Feb17-10, 03:54 AM
P: 5
Hello,
I want to express Non-Deterministic Turing Machine constraint with boolean expression.
The constraint is: "Cells which aren’t being read remain the same at time t+1".
lets say H[i,j] means the read/write head at time i at cell j
and S[i,j,k] means the symbol k at time i in cell j

so the expression would be:
~H[i,j] ^ ~S[i,j,k] -> ~S[i+1,j,k]

which equivalent to
H[i,j] V S[i,j,k] V ~S[i+1,j,k]

is this correct ?
i saw in many lecture notes in the web very different expressions, so i'm confused for what's correct.

Thank You
Phys.Org News Partner Science news on Phys.org
Scientists pinpoint when harmless bacteria became flesh-eating monsters
Asian air pollution affect Pacific Ocean storms
Rocket leak delays space station delivery launch (Update)
Phrak
Phrak is offline
#2
Feb17-10, 04:59 AM
P: 4,513
I don't understand the algebra. H and S are range variables, aren't they? If so, how do you obtain the truth value of H when H=12, for instance?
insectosaurus
insectosaurus is offline
#3
Feb17-10, 05:04 AM
P: 5
H and S are 2D and 3D arrays
H[i,j] is TRUE if the read/write head at time i is scanning cell j, else FALSE
S[i,j,k] has symbol k at time i in cell j

Phrak
Phrak is offline
#4
Feb17-10, 05:36 AM
P: 4,513

Boolean expressions for Turing Machine


OK.

By your definition S[i,j,k] = True always, and S[i+1,j,k] = False always.

But i,j, and k are random variables aren't they? If so S[2,2,3] = True and S[1+1,2,3]=False. This is an immediate contradition.
insectosaurus
insectosaurus is offline
#5
Feb17-10, 05:49 AM
P: 5
no it's not,
more precisely, [tex]0 \leq k \leq[/tex] |[tex]\Sigma[/tex] | - 1, where
[tex]\Sigma[/tex] is the alphabet.

so S[i,j,k] means at time i, the contents of tape square j is symbol [tex]s_{k}[/tex]

and [tex] 0 \leq i \leq p(n) [/tex] and [tex] -p(n) \leq j \leq p(n) [/tex]

where n is input's length,
lets say the input string is x, then [tex] x = s_{1} \cdot s_{2} \cdot ... \cdot s_{k} \cdot ...\cdot s_{n}[/tex]
Phrak
Phrak is offline
#6
Feb17-10, 06:00 AM
P: 4,513
Back up a minute. Is S[i,j,k] always true?
insectosaurus
insectosaurus is offline
#7
Feb17-10, 06:15 AM
P: 5
no, it's true if cell j contains symbol [tex]s_{k}[/tex] at time i
Phrak
Phrak is offline
#8
Feb17-10, 06:42 AM
P: 4,513
I believe your problem with this is the notational conventions in use. Though, nearly universally, i,j and k are random variables.

You might try to decipher what objects are treated as constants and what are treated as variables in any given assignments.

I'm afraid my time is up for tonight.
insectosaurus
insectosaurus is offline
#9
Feb17-10, 10:13 AM
P: 5
i,j,k are not random variables
Phrak
Phrak is offline
#10
Feb25-10, 06:13 AM
P: 4,513
You are confused as to what constitutes a logical statement.


Register to reply

Related Discussions
building a Turing machine Programming & Computer Science 14
Turing machine help! Engineering, Comp Sci, & Technology Homework 0
Complement of Universal Turing Machine - Does this exist?? Set Theory, Logic, Probability, Statistics 4
turing machine problem Engineering, Comp Sci, & Technology Homework 1
Paper Tape Turing Machine Calculus & Beyond Homework 9