What is a Turing Machine (TM), and what can it do?
Think about a computer for a minute. You usually don’t think about how a computer works deep down inside. The brains of the computer is the processor. You can think of the processor as a little guy inside of the computer that can do things for you. He can add, subtract, multiply, and do other simple things. Your programs are basically just a set of instructions for the processor. When your program starts running, the processor starts with the first instruction, and then keeps going until he is done. What is a program? Just about anything you use on the computer. For example, Word is a program that you use to type documents. When you start word, some of the instructions tell the processor and other parts of the computer what to display on the screen. Other instructions say what to do when you click your mouse or type on the keyboard. Now you’re wondering what this has to do with TMs. A Turing Machine is basically an abstract computer. It has the same basic parts that your computer has:
