Search code examples
stringturing-machineslexicographic

Turing Machine Design

I recently encountered the following problem:

Give a Turing machine diagram for a Turing machine that on input a string x ∈ {0, 1}∗ halts (accepts) with its head on the left end of the tape containing the string x′ ∈ {0, 1}∗ at the left end (and blank otherwise) where x′ is the successor string of x in lexicographic order; i.e. the next string in the sequence ε, 0, 1, 00, 01, 10, 11, 000, . . . in which the strings are listed in order of increasing length with ties broken by their corresponding integer value. (Briefly document your TM.)

I am confused as to how to start designing an appropriate solution for it. Could I get a couple of pointers for firstly designing this machine, and then Turing machines in general?

Solution

  • 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.