Penrose, Turing Machine 1


For being such a simple concept, trying to write my first Turing machine turned out to be more of a challenge than I’d expected. To recap, the basic Turing machine consists of a read/write head, an infinitely long tape, and a stepper motor for moving the tape under the head one position to the left or right. The data read from the tape will then cause the machine to do something based on its current state (i.e. – it’s a “state machine”). One example algorithm hard-coded into the machine could be:

Line 1: 00 -> 00R
Line 2: 01 -> 11R
Line 3: 10 -> 01STOP
Line 4: 11 -> 11R

In words, for line 1, if the machine is in “state 0”, and a “0” is read from the tape (i.e. – “00”), set the machine to state “0” again, write a “0” to the tape, and then move the head one position to the right.
For line 2, if the machine is in “state 0” and a “1” is read from the tape (“01”), set the machine to state “1”, write a “1” to the tape, and move the head one position to the right.
For line 3, if the machine is in “state 1”, and “0” is read from the tape (“10”), set the machine back to state “0”, write a “1” to the tape, move the head one position to the right, and then STOP the machine (AKA: R.Stop).
For line 4, if the machine is in “state 1”, and “1” is read from the tape (“11”), set the machine state to “1”, write a “1” to the tape, and then advance the head one position to the right.

Syntax:
for: state & ‘bit read’ -> ‘new state’ & ‘write bit’ & direction

The above algorithm reads a string of leading 0s on the tape, essentially ignoring them. When it hits the first 1, it changes state, then keeps reading 1s. When it hits the next zero (end of number marker), the machine writes a 1 to the tape, moves the head to the right one last time, then stops. The value generated by this machine is calculated by adding up all the 1s to the left of the head. This is a “unary” number, and the algorithm simply adds 1 to the starting number on the tape. If there were six 1s on the tape when we started, there will be seven 1s to the left of the head when we finish.

“0000111111000” – Starting data string
“00001111111” – What gets printed out before the Stop.

We can have two “stop” instructions – an R.Stop and an L.Stop. They indicate which way to move the read/write head before stopping. But, because we’re reading the output from the left of the head, there’s no point to using L.Stop, and R.Stop can then be simply abbreviated to “Stop”.

I use VBscript because it’s free, and I already know how to write in it. To emulate the tape, I just use a text string. If the read/write head reaches either end of the string, I append a “0” at that end and keep running the program. I could treat the algorithm as a series of if-statements, but for the moment I prefer to use Select Case. The main reason for this is that I’ll be changing the program structure soon anyway to make a universal Turing machine. And, it’s easier to adapt hard-coded algorithms as Case statements if I want to write a new machine.

The only real inconvenience was in having to write a function for emulating the write head, for changing characters in the middle of the string. Note that the formatting below sucks because wordpress strips out excess spaces.

‘ Turing Machine 1 – Unary Add 1
‘ Penrose program: UN+1

”””””’

tapeReel = “0000000111110000”
headPos = 1
machineState = “0”
RStop = false
tapeChr = 0

wscript.echo tapeReel & ” (” & countOnes(tapeReel) & “)”

while Not RStop
tapeChr = mid(tapeReel, headPos, 1)
fullStatement = machineState & tapeChr
action = “”

Select Case FullStatement
Case “00” action = “00R”
Case “01” action = “11R”
Case “10” action = “01STOP”
Case “11” action = “11R”
Case Else wscript.echo “No instruction provided for |” & fullStatement & “|”
End Select

if(instr(action, “STOP”) > 0) then
dummy = writeToTape(headPos, mid(action, len(action) – 4, 1))
headPos = moveHead(headPos, “R”)
RStop = true
else
machineState = left(action, len(action) – 2)
dummy = writeToTape(headPos, mid(action, len(action) – 1, 1))
headPos = moveHead(headPos, right(action, 1))
end if

wend

wscript.echo “Ping: ” & left(tapeReel, headPos – 1) & ” (” & countOnes(left(tapeReel, headPos – 1)) & “)”

Since I’m treating the tape as a text string, I need some way of marking where I am in the string (headPos), and then some function for “transporting” the head one position left or right (headPos +/- 1). Finally, I have to deal with boundary conditions. That is, what happens if I’m at the left end of the string (headPos = 1) and I have to move left, or I’m at the right end (headPos = len(tapeReel)) and I have to move right. I handle this by checking the boundaries first, and adding “0” to the end of the string as necessary to “go to the next part of the infinite tape.” I should check that I’m not exceeding VBscript’s limit on string length (64K), but that’s not a real concern for what I’m doing with this program. Either way, the tape head “moves” by incrementing or decrementing headPos.

Function moveHead(hp, dir)
ret = -1
if(hp = 1 AND dir = “L”) then
tapeReel = “0” & tapeReel
ret = 1
elseif (hp = len(tapeReel) AND dir = “R”) then
tapeReel = tapeReel & “0”
ret = hp + 1
elseif (dir = “L”) then
ret = hp – 1
elseif (dir = “R”) then
ret = hp + 1
else wscript.echo “Direction ” & dir & ” not recognized.”
end if
moveHead = ret
end Function

The more piddly part was in handling the “write to tape” section. If I was using an array (or, C++ and treating the string as a character array), I’d just overwrite the old value at wherever headPos is pointing in the string. However, VBScript doesn’t work that way, and doesn’t have a built-in function for this. So, I have to break the string in two, on either side of where headPos is pointing, then recreate the string as leftPart & newValue & rightPart. Again, though, I have to worry about the boundary conditions, where I’m at one end of the string, and if using the built-in left() or right() functions will bomb in an error.
Note that I’m using writeToTape as a procedure instead of a function. Unfortunately, VBScript requires a return value at the end, so I’m just forcing it to “true” and storing it to a dummy variable in the calling routine.

Function writeToTape(wttHP, wttVal)
lstr = “”
rstr = “”
if(wttHP = 1) then
rstr = right(tapeReel, len(tapeReel) – 1)
elseif (wttHP = len(tapeReel)) then
lstr = left(tapeReel, wttHP – 1)
else
lstr = left(tapeReel, wttHP – 1)
rstr = right(tapeReel, len(tapeReel) – wttHP)
end if
tapeReel = lstr & wttVal & rstr
writeToTape = true
end Function

I wrote countOnes() as a built-in function to the Turing machine. That is, I want the machine itself to tell me how many 1s are in a given strip of the infinite tape instead of making me count them manually. This is really useful if the input number is 138 digits long.

Function countOnes(coStr)
ret = 0
for i = 1 to len(coStr)
if(mid(coStr, i, 1) = “1”) then
ret = ret + 1
end if
next
countOnes = ret
end Function

Advertisements
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: