So let’s take a step back and ask, what is a Turing machine?

A Turing machine is just an extension of a finite state machine. Just like an FSM, a Turing machine has a finite set of states and a state relation that defines how it moves between them based on its input. The difference is that its inputs come on a strip of tape, and the machine can both read and write symbols on that tape, something like this:

The basic idea of the Turing machine is simple. Take a finite state machine. Instead of feeding ...

Start Free Trial

No credit card required