Programming Turing Machines: High-level approach
If you’ve got the hang of Turing machine procedures down, at this point you should be able to write your own with relative ease. If you aren’t comfortable with them yet, revisit the last section of the previous topic (feel free to use the comments section as a scratch pad to run examples by me). I wrote out nine procedures for the Turing machine implementation that perform bitwise operations. Before moving onto the “main attraction”, I will describe some of these operations, as well as some measures I took to make inference easier later on.
Procedure standards
As I mentioned in Part I, I use ‘>’ to mark the beginning of the tape. Some of my procedures perform an operation on two words on the same tape; I use a ‘:’ to mark the end of the first word. Any procedure that requires marking symbols to keep track of previously visited cells uses ‘*’ as the marker. As an example, I wrote a procedure that will reverse a bitstring:
; go to end of string
s1 > > r s1
s1 0 0 r s1
s1 1 1 r s1
s1 _ : l s2
; grab value to copy
s2 * * l s2
s2 0 * r s3
s2 1 * r s4
s2 > > r s5
; go to end of string on 0
s3 * * r s3
s3 0 0 r s3
s3 1 1 r s3
s3 : : r s3
s3 _ 0 l s6
; go to end of string on 1
s4 * * r s4
s4 0 0 r s4
s4 1 1 r s4
s4 : : r s4
s4 _ 1 l s6
; move left to :
s6 0 0 l s6
s6 1 1 l s6
s6 : : l s2
; delete *
s5 * l s5
s5 : l s5
s5 > > r s5
This procedure will first append a ‘:’ to the end of the tape. Then it will loop back and forth marking and copying characters in reverse order. To clean things up, the last thing it does is remove marking characters and the ‘:’ separator. To make things a bit more clear, here is the output configurations for the word “0011”:
>0011 s1
^
>0011 s1
^
>0011 s1
^
>0011 s1
^
>0011 s1
^
>0011_ s1
^
>0011: s2
^
>001*: s4
^
>001*:_ s4
^
>001*:1 s6
^
>001*:1 s2
^
>001*:1 s2
^
>00**:1 s4
^
>00**:1 s4
^
>00**:1 s4
^
>00**:1_ s4
^
>00**:11 s6
^
>00**:11 s6
^
>00**:11 s2
^
>00**:11 s2
^
>00**:11 s2
^
>0***:11 s3
^
>0***:11 s3
^
>0***:11 s3
^
>0***:11 s3
^
>0***:11 s3
^
>0***:11_ s3
^
>0***:110 s6
^
>0***:110 s6
^
>0***:110 s6
^
>0***:110 s2
^
>0***:110 s2
^
>0***:110 s2
^
>0***:110 s2
^
>****:110 s3
^
>****:110 s3
^
>****:110 s3
^
>****:110 s3
^
>****:110 s3
^
>****:110 s3
^
>****:110 s3
^
>****:110_ s3
^
>****:1100 s6
^
>****:1100 s6
^
>****:1100 s6
^
>****:1100 s6
^
>****:1100 s2
^
>****:1100 s2
^
>****:1100 s2
^
>****:1100 s2
^
>****:1100 s2
^
>****:1100 s5
^
>***:1100 s5
^
>***:1100 s5
^
>**:1100 s5
^
>**:1100 s5
^
>*:1100 s5
^
>*:1100 s5
^
>:1100 s5
^
>:1100 s5
^
>1100 s5
^
>1100 s5
^
>1100 H
^
It is important that the procedure clean up any markers or trailing symbols in Γ: the next part involves setting the input tape of one Turing machine equal to the output of another.
Chaining
It’s time to move on to bigger and better things. Let’s revisit a procedure from the previous post:
s1 > > r s1
s1 0 1 r s1
s1 1 0 r s1
s1 _ _ l s2
s2 0 1 l s3
s2 1 0 l s2
s2 > > r s3
s3 0 0 l s3
s3 1 1 l s3
s3 > > r s4
s4 0 0 r s4
s4 1 1 r s4
s4 _ l s5
This procedure takes a bitstring as input and outputs two’s complement. This procedure isn’t terribly useful on its own, but when combined with a procedure to add two numbers, we get binary subtraction. Here’s an example of the one I made; it’s a bit lengthy so I won’t paste it here.
Looking at that, you can see how these procedures comply with the standard I outlined earlier: the add procedure expects two operands (of equal length) separated by a ‘:’ with no additional characters from Γ. Our two’s complement procedure expects one operand with no additional characters from Γ.
To combine these procedures into something useful, we need a way of storing and manipulating input tapes before they are passed to the next Turing machine. Let’s say we want to perform 2 - 1; based on what we know the procedures expect, we can start constructing our inputs:
2 = 10
1 = 01
So our tape for two’s complement will start out as follows:
>01
^
After the procedure runs, we will have:
>11
^
Next, we append the 2; since we’re adding now, order is irrelevant:
>11:10
^
Our add procedure will preserve bitness, so we don’t care about overflow. If we pass this modified tape into our add procedure, it will output the following after halting:
>01
^
And just like that, we have our answer.
More power
Like most of you, when I got to this point of the project, I began wondering “just how far can I take this?” Pretty far. I wont paste the code I wrote, but I made a separate Chain() class for Turing machines. It contains the following components:
- An ordered list of procedures to run,
- A string to contain the tape passed immediately to a Turing machine,
- Four “registers” that can hold tapes for pending instructions before passing into a Turing machine,
- An integer to set global bitness (defaults to 32),
- A path to the folder containing your Turing machine procedures,
- An integer containing the index of a procedure to run next (for jumping),
- A separate tape “register” to store a value to compare other tapes to (for conditional jumps),
- An ordered list with class functions to make it operate as a stack,
- And an integer to hold the current index of the top of the stack.
With those nine things, it’s very hard to figure out what you can’t do, but some additional instructions are necessary.
Now that we’ve reached the point where we are operating on two different classes, I will be using specific words to mitigate confusion. An instruction is a command sent to the Chain() class to perform some tape operation, while a procedure is a file containing transitions for the TuringMachine() class to run. Let’s start exploring some basic procedures we need to perform common tasks. So far, I’ve only written bitwise procedures, as I am trying to simulate modern computing. Here’s a list of what I have:
- add
- and
- not
- or
- xor
- tcomp
- shl
- shr
It should be easy to understand what these procedures do based on their names. The next most important part are the instructions for chaining. Right off the bat, we need a way of sending data to the tape, so I made a put instruction. This is only one of two instructions that actually take input. Currently the put instruction will copy an integer (base 2, 10, or 16) and copy it to the tape in binary, padded with zeros to fill the bitness specified by the class variable. We also need a way of setting and getting tapes to and from the tape registers, respectively. Since we have four registers, we have four store commands (stX, where X is ‘a’, ‘b’, ‘c’, or ‘d’) and four get commands (gtX, where X is ‘a’, ‘b’, ‘c’, or ‘d’). I also created a concatenate instruction that will automate the combination of operands separated by a ‘:’ (ctXY, where X and Y are ‘a’, ‘b’, ‘c’, or ‘d’).
With these instructions, combined with our eight procedures, we can begin writing programs that look an awful lot like Assembly. Here’s a quick example of one that will perform the previous 2 - 1 example:
put 2
sta
put 1
tcomp
stb
ctab
add
For my chaining implementation, it is important to remember that I tried to make instructions pirform an operation on the input tape. For example, sta will copy the word on the input tape into the A register; put writes a word directly onto the input tape. One instruction that “skips” a step is the ctab one. This instruction will take the tape in the A register and copy it to the input tape, then append a ‘:’ and the tape from the B register (excluding the ‘>’ marker).
Jumping and the stack
I added instructions that will perform a loop backwards through the instruction list. Later, I added ways of pushing and popping the current instruction index to the stack; this allows us to do more advanced jumps and calls, like this:
; code
call 4
call 12
call 19
halt
; 4
put 1
sta
put 2
stb
ctab
add
sta
ret
; 12
put 123456789
tcomp
stb
ctab
add
sta
ret
; 19
put 987654321
tcomp
stb
ctab
add
sta
ret
call will push the index of the next instruction onto the stack, and set our indexing variable equal to the integer that you pass with the instruction (this is the second of two instructions that take input). ret will pop the top of the stack (make sure you clean it up before this, obviously) and set our indexing variable equal to what is popped. Finally, the halt command will force the chain to stop executing instructions. Without this command, the above example will perform all of its instructions twice: once when they are explicitly called, and again after call 19 returns and the chain continues its top-down execution.
Parting words
Some other things I added was an instruction in the parser that will preload some data from a configuration file. The parser assumes the path to this configuration is the first non-commented line. Here is an example:
; config path
/Users/fi6uh/.rconfig
; code
call 2
halt
; 1
put 1
sta
put 2
stb
ctab
add
sta
ret
Currently, the parser only looks for two things: your bitness value, and the path to your procedures:
bits=4
path=/Users/fi6uh/Projects/path/to/procedures/
I also added a debugging feature that will show register and stack content (and other stuff) in a fashion similar to GDB. The way the chain currently operates, it will be easy to make more useful debugging features (step, back, break, etc.) and I will do so in the near future. Some of the instructions I have added leave room for cool “exploits”, which is where I’m headed next with this project. I’ll end here for now, but expect a Part 4 in the not-too-distant future!
Challenge
If anyone is interested in using this project, I can push the whole thing to GitHub. If you want an exercise to test what I’ve demonstrated, try writing a program that will perform the string reversal algorithm I talked about in this post. As the project sits, I have no way of performing string operations; just use bitstrings for your tests. Let me know how it goes and post your woes in the comments! I’ll be trying this out as well!