Turing Machine in Bare Bones

The most recent release of my Bare Bones interpreter made identifiers case-insensitive, and added an optional peephole optimizer that recognizes a common idiom:

while N not 0 do;
    decr N;
    incr X;
end;

Such a loop adds N to X, clearing N in the process. Without the optimizer, this is has time complexity O(N). The optimizer replaces it with a single macro that executes in O(1). This makes the supplied example program that computes Fibonnaci numbers run much faster.

For the next release, I’ve added more sample programs, including an example of a Bare Bones translation of a two-symbol three-state Turing machine busy beaver program. The Bare Bones program demonstrates that Bare Bones can perform any action that can be performed by a Turing machine, proving that Bare Bones is universal.

Brookshear states that Bare Bones is universal by comparing it to a Turing machine, but only actually shows that it can compute two simple functions that are computable by a Turing machine. He states that “researchers have shown that the Bare Bones programming language can be used to express algorithms for computing all the Turing-computable functions,” but unfortunately he does not give any reference to publication of such results.

One way to show that a machine or language is universal is to show that it can emulate a Turing machine, or that any Turing machine program can be translated into a program for the machine or language in question. At first glance it wasn’t obvious that Bare Bones could be universal, because a Bare Bones program can only use a finite number of variables. The key to its universality is that a Bare Bones variable can contain any non-negative integer. An infinitely long one-dimensional Turing machine tape can be represented as three variables: one contains all the symbols to the left of the head, one contains the symbol at the head, and one contains all the symbols to the right of the head. For a turing machine with an alphabet of n symbols, to move the head position right, one must execute these assignments (in pseudo-code, not Bare Bones code):

LEFT := LEFT * n + HEAD;
HEAD := RIGHT mod n;
RIGHT := RIGHT / n;

Moving the head position left is done by the same assignments, with LEFT and RIGHT swapped. For a two-symbol Turing machine, the Bare Bones code to move the head position to the right is:

# LEFT := LEFT * 2;
copy LEFT to TEMP;
while TEMP not 0 do;
    incr LEFT;
    decr TEMP;
end;
# LEFT := LEFT + HEAD;
while HEAD not 0 do;
    incr LEFT;
    decr HEAD;
end;
# HEAD := RIGHT mod 2;
# RIGHT := RIGHT / 2;
copy RIGHT to TEMP;
clear RIGHT;
copy TEMP to HEAD;
decr TEMP;
while TEMP not 0 do;
    incr RIGHT;
    decr TEMP;
    copy TEMP to HEAD;
    decr TEMP;
end;

That’s the most complicated portion of the Turing machine interpreter. I might write up an explanation of the rest at some future date. For now, anyone interested in the details can look at the example Bare Bones source code for a simulation of a three-state Turing Machine busy beaver program: tm_busy_beaver_3.bb.

Note that it is not currently practical to to use my Bare Bones interpreter to simulate a Turing machine with a long tape, because the division/modulus code used to shift the tape takes O(n) operations, where n is the number of bits to the right of (or left of) the head. To make that reasonably efficient, I’ll need to extend the interpreter’s optimizer, and make the interpreter use bignum arithmetic (probably using the GMP library). Once that’s done, it would be nice to try running a universal Turing machine in Bare Bones. The smallest two-symbol UTM I’ve heard of uses 22 states.

This entry was posted in Bare Bones, Computer Science. Bookmark the permalink.

3 Responses to Turing Machine in Bare Bones

  1. Hanno says:

    Hello:

    I hear the Turing Machine is “universal” – and it may be.

    But have you ever seen useful programs like BCD to Binary, addition, move, etc. More specifically, can I construct a family of commands at a little higher level? If so, is there a construction procedure, a strategy or a compiler of sorts? Or is the generation of programs for a TM something like a Rubik’s cube with trial and errors or just even intuition?

    Thanks, and regards

    Hanno

  2. Eric says:

    Hi Hanno!

    That’s a very good question. I used to wonder how to construct non-trivial Turing Machine programs myself, as it is very difficult to do it directly, although it can be done.

    I think the easiest way is to write the program in an easier-to-use language that can be automatically translated into a Turing Machine program. For example, it should be possible, and not too difficult, to translate programs in Bare Bones (or a similar language) into equivalent Turing Machine programs. Going one step further, it would be possible to translate programs in an even easier-to-use language into Bare Bones, which could then be translated into Turing Machine programs.

    In general the way to write complex programs for a Turing Machine, or to compile other languages into Turing Machine programs, is to use a multiple tape Turing Machine. This seems a bit like cheating, until one learns that any multiple-tape Turing Machine program can fairly easily be transformed into a single-tape Turing Machine program. However, this translation (as with the others proposed above) results in a considerable loss of runtime efficiency. (Of course, the point of a Turing Machine has never been efficiency.)

    I found _Theory of Computation: Formal Languages, Automata, and Complexity_ by J. Glenn Brookshear to have better coverage of Turing Machines than I’ve seen elsewhere. It is the book in which Brookshear originally introduced the Bare Bones programming language. In chapter 4 Brookshear presents the proofs that all Bare Bones programs are partial recursive, and that Bare Bones can compute all partial recursive functions, thereby showing that Bare Bones is equivalent to a Turing machine.

    I hadn’t seen Brookshear’s proofs when I started my little project to transform Turing machine programs into Bare Bones programs; while Brookshear gives a more elegant proof of the equivalence, I give an existence proof.

    Brookshear’s book is out of print, but it’s not too hard to find it in libraries, or used copies (e.g., on Amazon).

    Best regards,
    Eric

  3. alperen says:

    Hi friends, I need your help question:Place a 1 in the variable Z if variable X is less than or equal to variable Y,and place a 0 in variable Z otherwise.(Use BARE BONES PROGRAM!)..Thank you in advance for your help ..

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>