Boolean expressions for Turing Machine

Click For Summary

Discussion Overview

The discussion revolves around expressing constraints of Non-Deterministic Turing Machines using boolean expressions. Participants explore the definitions and implications of the symbols used in the expressions, particularly focusing on the behavior of the read/write head and the symbols in the cells over time.

Discussion Character

  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant proposes a boolean expression to represent the constraint that cells not being read remain unchanged at the next time step.
  • Another participant questions the algebraic representation, specifically how to determine the truth value of the head position when it is treated as a range variable.
  • Clarifications are made regarding the nature of H and S as 2D and 3D arrays, respectively, with definitions provided for their meanings at specific indices.
  • Concerns are raised about the consistency of the truth values assigned to S[i,j,k] and S[i+1,j,k], suggesting potential contradictions in the definitions.
  • A participant emphasizes the constraints on the indices and the alphabet size, attempting to clarify the notation used in the expressions.
  • There is a discussion about whether i, j, and k should be considered random variables, with differing opinions on this characterization.
  • One participant suggests that confusion arises from the notational conventions and the distinction between constants and variables in the context of the discussion.
  • Another participant asserts that i, j, and k are not random variables, indicating a disagreement on this point.
  • A final comment challenges the understanding of logical statements within the context of the discussion.

Areas of Agreement / Disagreement

Participants express differing views on the nature of the variables involved and the correctness of the proposed boolean expressions. There is no consensus on the definitions or the implications of the expressions, leading to an unresolved discussion.

Contextual Notes

Participants have not reached a common understanding regarding the definitions of the symbols and the logical statements involved. The discussion includes various interpretations of the notation and its implications for the boolean expressions.

insectosaurus
Messages
5
Reaction score
0
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
 
Physics news on Phys.org
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?
 
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
 
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.
 
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]
 
Back up a minute. Is S[i,j,k] always true?
 
no, it's true if cell j contains symbol [tex]s_{k}[/tex] at time i
 
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.
 
i,j,k are not random variables
 
  • #10
You are confused as to what constitutes a logical statement.
 

Similar threads

Comp Sci Why is NTM Time Complexity Guessing Polynomial?
  • · Replies 2 ·
Replies
2
Views
2K
Comp Sci Problem on undecidable problems
  • · Replies 6 ·
Replies
6
Views
3K
Engineering Current density calculation in anisotropic ferromagnetic film
  • · Replies 7 ·
Replies
7
Views
2K
Comp Sci Validating Braces Placement for Expression Evaluation
  • · Replies 10 ·
Replies
10
Views
2K
MHB Is this a Gödel number of a Turing machine?
  • · Replies 3 ·
Replies
3
Views
2K
Engineering Recursive implementation of an FIR Filter
  • · Replies 2 ·
Replies
2
Views
2K
Is this a Turing-complete machine?
  • · Replies 2 ·
Replies
2
Views
2K
Three phase AC concepts and problems
  • · Replies 2 ·
Replies
2
Views
6K
Is Alan Turing given too much credit when it comes to computers?
  • · Replies 29 ·
Replies
29
Views
6K
Current flowing through resistor in RLC circuit (C in parallel with L)
  • · Replies 19 ·
Replies
19
Views
3K