@heather You do have something to work with - you have a formal definition of what an NP-class problem is
You also have a formal definition of what a P-class problem is
So the challenge is to apply the rules of logic to either show that the definition of an NP-class problem logically implies that the problem is a P-class problem or to exhibit an NP-class problem that's provably not in P
@heather Nondeterminism is harder, so you only have to read that if you want (specially since the non-deterministic turing machine doesn't exist, so it's just a theoretical imagination)
If the turing machine was a function, and at time $k$ the value of it's function on the bit it's reading on the tape is $x$, then $x$ is the internal state of the turing machine
@heather That paper is a little hard to digest, but it get's easier
okay, and then an internal state, just the state of a specific program? but what does it mean for that to be finite...oh, does it just mean that the program has to have access to a finite amount of information
@heather It may be good to not think immediately of "circuits" or "programs". The machines of computer scientists are just abstract devices that react to input, usually no assumption is made on how they would be physically realized.
it's a theoretical model on the meaning of computability
@heather They can't access all the info in one "frame" of time. The machine needs to move around the tape to read more, it can only access what's on it's current location on the tape
@ACuriousMind, I'm just talking about whatever is in that paper, which it says is a turing machine, I'm just probably being confusing in my language =P
@heather Yes, It can read one cell of information (info is stored on an infinite tape divided into cells), and it has a finite number of internal state
@BernardMeurer All (deterministic) finite automata are Turing machines, but not all Turing machines are finite automata. I'm suddenly unsure though whether "finite state machine" is the same as what I mean by "finite automaton". Maybe I should shut up and let you explain since you know what's in the paper and I'm just reacting to what's typed into chat ;)
what does that mean? I know what a set $X$ $\times$ a set $Y$ is, the ordered pairs $(x, y)$ with $x\in X$ and $y\in Y$ (thanks to 0celo7), but how does that work with a set of information and an alphabet of symbols? what does it mean intuitively? (sorry for all the questions, btw)
@heather No worries, it's the first time in my life I'm helping someone on the h-bar lol
No one here cares about the real science
Computer science that is
A Turing machine is specified by a finite alphabet Σ, a finite set of states K with a special element s (the starting state), and a transition function δ : K × Σ → (K ∪ {halt, yes, no}) × Σ × {←,→, −}. It is assumed that Σ, K, {halt,yes,no}, and {←,→, −} are disjoint sets, and that Σ contains two special elements ., t representing the start and end of the tape, respectively. We require that for every q ∈ K, if δ(q, .) = (p, σ, d) then σ = . and d 6=←. In other words, the machine never tries to overwrite the leftmost symbol on its tape nor
I think definition 1 should be read in conjunction with definition 2, at least the definition of the configuration of the machine. You don't really understand what the heck $\delta$ is supposed to be before you know what a configuration is, imo
The set Σ∗ is the set of all finite sequences of elements of Σ. When an element of Σ∗ is denoted by a letter such as x, then the elements of the sequence x are denoted by x0, x1, x2, . . . , xn−1, where n is the length of x. The length of x is denoted by |x|.
When an element of Σ∗ is denoted by a letter such as x, then the elements of the sequence x are denoted by x0, x1, x2, . . . , xn−1, where n is the length of x.
@heather He meant that the this in "this sentence* referred to the very sentence it occurred in, so he meant to get $x_7$ of "For the english alphabet example, give me $x_7$ of this sentence" ;)
A configuration of a Turing machine is an ordered triple (x, q, k) ∈ Σ∗ × K × N, where x denotes the string on the tape, q denotes the machine’s current state, and k denotes the position of the machine on the tape.
