Let's get started with Varphi and write a program from scratch.
The objective of this tutorial is to show how to write a simple program with Varphi. We will show how to go about thinking about the algorithm, and then how to translate that algorithm into Varphi.
The input tape's representation convention will be as follows:
The output tape's representation convention will be as follows:
We would like to "merge" these two numbers to form a contiguous block with five tallies on it. One may think about this as perhaps shifting all the tallies of the left (or right) number to the right (or left) by one tape cell. The way we will implement it is by "teleporting" the left (or right) number to appear immediately to the right (or left) of the right (or left) number. This is depicted below. Again, this is by no means the most efficient way to do this, but we implement it in this way for demonstration purposes.
A way to perform such an algorithm is to transfer each individual tally to the left of the right number, one-by-one. That is, for every tally in the left number, delete it, then go to the rightmost tally of the right number and replace the blank cell to the right of it with a tally.
Let's phrase this in a more "Turing-machine-like" way. For the purposes of this algorithm, let's call the blank tape cell separating the two numbers on the input tape the middle blank. Now recall that the Turing machine's head always starts off at the leftmost tally. So, what we'll do is replace that tally with a blank, then pass all of the remaining tallies of the left number (moving the head to the right) until we hit the middle blank. Once we hit this middle blank, we'll skip it, then skip all of the tallies of the right number (again, still moving the head to the right) until we hit the first blank to the right of the right number. Then, write a tally to this blank tape cell. Now we have successfully transferred the first tally of the left number to the right place. To start working on the rest of the tallies of the left number, skip through the tallies of the right number (moving the head left this time) until we hit the middle blank. Once we hit the middle blank, we'll skip it, then skip all of the tallies of the left number (again, still moving the head to the left) until we hit the first blank to the left of the left number. Then, move the head one position to the right. If the tape cell at this tape cell is blank, then we've successfully moved all the tallies of the left number to the right of the right number. Otherwise, we still have tallies to move, and we can restart the same process we took with the initial tally we moved.
Hopefully this algorithm makes intuitive sense. However, notice how much it took us to describe it in English. Below, you'll see the equivalent Varphi algorithm, and you can judge for yourself if it makes writing such algorithms easier!
Now that we have an algorithm, we can start to write it in Varphi. You may be able to see from the algorithm's description that we need six states:
A state for replacing the leftmost tally of the left number with a blank
A state for skipping the tallies of the left number, moving towards the right
A state for skipping the tallies of the right number, moving towards the right
A state for skipping the tallies of the right number, moving towards the left
A state for skipping the tallies of the left number, moving towards the left
A halting state
Instead of describing in English the function of each state and how it connects with other states, we've decided that a Varphi program may actually be the clearest way to do this. Here's the Varphi program describing this Turing machine:
Here's a version without comments:
The Turing machine we will design for this guide performs binary addition (that is, addition of two numbers), specifically on numbers from the set of positive integers, in a more unique way (a very efficient way is given here).
To represent two positive integers and , repeat tallies, followed by a blank, followed by tallies. Leave the rest of the tape blank.
There shall only be one contiguous block of tallies, which will represent the output of the Turing machine. If there are tallies in the contiguous block, then the number being represented by the tape is .
When thinking about how to design Turing machine algorithms, it often helps to think about an example. Suppose we would like to add the positive integers and . Under the input representation convention, the input tape to the machine will look like the following:
That's it! You've just written your first Varphi program
