Turing Machine Design

Turing Machines

First off, you need to understand what a Turing machine is, and by Turing machine, I'm assuming you're talking about a Universal Turing Machine. This is a conceptual machine created by the Godfather of Computer Science, Alan Turing.

The machine is built up of some components. First, an infinite tape that contains input. Something like..

1-0-1-1-1-1-0-1-0-1-0

Then a set of rules..

if 1 then 0
if 0 then 1

So when the machine hits the 1, the output is 0, as per the rule. We define the machine hitting a value when the read head is set to it. The read head is like the current position in the turing machine. So it will go..

1-0-1-1
^------------Current head.

Then the next iteration:

1-0-1-1
  ^----------Current Head

This machine is actually simulating bitwise NOT functionality. You can also set a state in a turing machine, so for example:

if 1 then enter state 1
if 0 then enter state 0

Big deal right? Example suddenly, now you can do stuff like:

1. if 1 and in state 1 output 1 and enter state 0
2. if 1 and in state 0 output 0 and enter state 1
3. if 0 and in state 0 output 1 and enter state 1
4. if 0 and in state 1 output 0 and enter state 0

And we define a state as our default state. In this example, let's call it state 0. So when the machine starts, it sees a 1. Well I'm in state 0 and I've just got a 1 so I'm going to do rule number 2. Output a 0 and enter state 1. The next number is a 0. Well I'm in state 1, so I call rule number 4. See where this is going? By adding states, you really open up what you can do.

Now, a Universal Turing Machine is what's known as Turing Complete. This means that it can compute any computable sequence. Including, the specification for your assignment!

Your Assignment

So let's look at your assignment in the context of a turing machine.

The aim of the machine is to print out..

0 1 00 01 11 000 001 011 111

So we know that we need to maintain a state. We also know that the state needs to get deeper and deeper. So if you user types in 000, we need to be able to know that we have three characters to output.

And in terms of homework help, that's I'm afraid all I should be responsibly giving you. A good understanding of the turing machine, plus an understanding of what you need this to do, should result in a start in your research to a solution.