What can a Turing machine do?
Turing’s thesis was that a Turing machine can do anything that can be described in an algorithm. In other words, it can do whatever the most modern computer can do. And vice versa, if a Turing machine can’t do something, neither can the most powerful computer. Here are some Turing machine programs you can write. They are all in the workbook. • To determine if there are an odd or even number of 1s on a tape. • To travel between two cells of the tape without stop. • Clear a 1 from and otherwise blank tape and then stop.. • Add unary numbers. Example 111+11=11111. • To convert a unary number to binary. Example 11111 to 101. How you write these programs depend on what the tape looks like when you start, and how you want it to look when you are done. The starting position of the head is also of importance. If you can improve any of the programs in the workbook, please let me know. If you like to suggest other interesting programs, I am all ears. My purpose for writing the Turing machine sim
