Turing Machine For Mac

Turing Machine is a free Turing machine simulator written in the Java programming language.

The Turing machine is one of the most beautiful and intriguing intellectual discoveries of the 20th century. Turing machine is a simple and useful abstract model of computation (and digital computers) that is general enough to embody any computer program.

The Turing machine forms the foundation of theoretical computer science. Because of its simple description and behavior, it is amenable to mathematical analysis.

This analysis has led to a deeper understanding of digital computers and computation, including the revelation that there are some computational problems that cannot be solved on computers at all, no matter how fast the processor, or how much memory is available.

The Turing machine converts from unary to binary. That is, if the input consists of n consecutive A's, then the Turing machine prints the number n in binary to the left of sequence of A's (and overwrites the A's with X's). In the example above, the input consists of 6 A's and the Turing machine writes the binary number 110 to the tape.

To describe how this is accomplished, we first review an algorithm for incrementing a binary integer by 1: scan the bits from right to left, changing 1's to 0's until you see a 0. Then change the 0 to a 1.

The Turing machine repeatedly knocks off one A at a time and increments the binary number. Our Turing machine mimics this strategy.

The initial state seeks out the next A, overwrites it with an X, and then transitions to the Increment state.

The Increment state increments the binary integer by one (leaving the X's alone, changing 1's to 0's, until seeing a 0 or #, which it changes to a 1), and then transitions back to the Initial state.

When all of the A's are overwritten with X's, the Cleanup state replaces all of the X's with #'s, and the transitions to the Halt state.