The content of this page is currently very barebones and just meant to be enough to understand p vs np. More may be added in the future.
What is a computer?
I built a machine that computes 123 + 456! Is this a computer?
Not quite, as computers must operate on some kind of input—if your machine instead took in two arbitrary three digit numbers and added them together, that would qualify as a computer. Indeed, the ability to solve a problem on different inputs is precisely what makes a computer interesting. We will now study two models for interacting with these inputs: finite-state machines and Turing machines.
Finite-state machines
As the name would suggest, a finite-state machine (FSM) is a machine that operates under a finite amount of states.
Note
Every physical computer actually qualifies as an FSM because it has a finite amount of memory and therefore can only be in a finite amount of states; more precisely, if a computer has bits of memory, it can be in at most distinct states.
In addition to these states, an FSM also has a transition table that tells it how to change states according to input. For instance, we can construct the following FSM to decide whether a given binary string has an even number of 0s:
Regular expressions
By Kleene’s theorem, FSMs are actually equivalent to regular expressions. However, it’s worth noting that modern regex engines are actually not regular expressions because they support non-regular features like backreferences and recursion.
However, a problem that an FSM would not be able to solve is determining whether an arbitrary-length binary string is a palindrome, since this task would require an unbounded amount of memory to store the first half of the string, in order to later compare it against the second. In order to tackle such tasks, we need to introduce a more powerful model of computation.
Turing machines
Turing machines are FSMs with one important added feature: read/write access to an infinite tape of external memory. Thus, when transitioning to the next state, they can perform two additional actions: write a symbol to the location currently underneath the tape head, and/or move the tape head left or right.
Non-deterministic Turing machines
Unlike deterministic Turing machines (DTMs), non-deterministic Turing machines (NDTMs) can be in multiple states at once; that is, each state can specify a set of actions (next state, write, move tape) to perform per transition rather than just a single one. The following image from Wikipedia best illustrates the difference:
