Skip to the content.

Binary Turing Machine

Skip to Content

Table of Content


Here is the “tutorial” explaining the implementation of a Binary Turing Machine in Baguette#
The machine is based on this python machine and adapted for Baguette#, it served to implement String and Array manipulation instruction in B#.
The present page is translated from the French TIPE report.


An infinite RAM is not possible in real life, so here is the specification of the implemented machine


The code of the initialization is shown bellow
In the first line we init the initial state of the machine to “0”, we then ask the input tape to the user (the input of the program). The next line is not entirely shown, it initialize the tape as a 500 length “22…” string then the input then a 500 length “22…” string.
The most important thing here is the TARTEALARHUBARBE instruction call, it constructs a matrix of size n by p (here 100 by 3) initialized with 0 everywhere. These three matrices will store the program. Two other variable n* and i are there to control the program loop, n is the number of line of the program and i is init at 0 (this will be the variable of looping)

Program reading

To read on the standard input, we must emulate a conditional loop, the Baguette# do not implement loops natively. We will use for that goal the two predefined variable n and i, the instruction ICECREAM <string> to construct LABELS, the PAINVIENNOIS <string> instruction to JUMP to the designed label, and finally a conditional test, SABLE <condition> <label>

Here is the algorithm of the program reading loop

This algorithm implemented gives twenty-three lines of code available on GitHub
Once this algorithm is completed we have read the whole program

One Step

We then need to implement a step of the program. We will also use a LABEL to separate this from the main code and allow the future run-loop to work. The labels are not properly functions, the scopes of the whole program is shared regardless where we are, this allows us to approximately emulate how functions works with labels. The most used instruction will be TARTEAUXFRAISES, which is the access of the n-th element of an array.

A step should do these steps

The implementation in Baguette# of this code is available on GitHub, until the 58th line. This piece of code is only performing one step. We now need to implement the main loop.

The Main Loop

Now we have a step of the machine, we need to repeat the steps until the machine state is H. We will see in the examples what happens what the program do when it is confronted to a never ending program/input for a program which does not always end.

Here again we have a conditional loop to implement. We will again use a LABEL and a conditional test IF.

Which can translates to “while machine state is not “H”, call step”.
Finally, we need to add a JUMP to “run” just after the initialization, to launch the program :



Left Bit Shift

The left bit shift is a binary multiplication by two, it’s “translating the bits” of one rank towards the left, effectively adding a 0 at the end of the binary input.

We can do it with the following algorithm:

In an automata (transition are from machine state to machine state labelled by tape reading) it gives that

and in form of a program readable by the Turing Machine we have


Executing it gives

Binary Add

A binary adder is way more complex, the program adapted for the turing machine is seventeen lines long (and will not be properly explained here), in short, it uses the second number as a counter to add one by one to the first number until the counter is at 0.

The automata representation gives this :

The whole program is available on the GitHub.

The execution for the addition of 10 and 8 (in binary 1010 and 1000) gives 10010 which is 16+2 = 18.

Infinite loop

Let the following program


It writes nothing, stays on the same cell, and alternate between state 0 and 1, thus never passing to state H and never finishing.
Executing it makes the interpreter print a lot of error codes until it stops executing the program and loop back to the REPL.