Rem
Turing Maschine
by Christian Geißler
9.8.2007

Info: The file Tape.txt is not necessary to run the program , but it represents the input (or the 'tape' of the turing machine).
You can load your own turing programs with the function 'LoadProgram(path$)', the syntax is
[x1] , [x2] , [x3] , [y4] , [y5] , [y6]
x = if head reads false
y = if head reads true
1 = value whitch to write on the tape
2 = number of the next state/line (higher than possible or = 0 ends program)
3 = readhead movement to (0 = left , 1 = right , 2 = stay)

Example: Following 'one line program' adds 1 to the binary number on the tape:
1,0,2,0,1,1

(x1, x2, x3, y1, y2, y3)

If it reads a '0'(=false) it follows x1,x2 and x3
If it reads a '1'(=true) it follows y1,y2 and y3

So if we would have the binary number <101> (=5) on the tape , it would work like that:
machine reads the first digit (1) from the tape and follows the instruction y1 , y2 and y3 of the first(and only) program line/state
y1 = 0 , that means that the machine writes a '0' on the tape
y2 = 1 , that means that the machine switches to state 1 , but because we are already on state 1 (we have just one line , so anyway we have just one state)
y3 = 1 , that means that the head of the machine moves to the 'right' side.
So now the number on the tape is < 001 >
The head moved to the right side , so it is now on the second digit and reads a '0' and follows the instructions x1,x2 and x3 of the first (and only) state/line:
x1 = 1 , that means that the machine writes a '1' on the tape
x2 = 0 , that means that the machine switches to state 0 , and because state 0 doesn't exist, the program ends.
x3 = 2 , this means that the head of the machine doesn't move this time, but it's actually not necessary because the program already ended.
So now the number on the tape is < 011 > ( = 6). You see , the program added sucessfully 1 to the number.

But you dont just need to make real calculations with the turing machine. It can also do some other nice things , like to double the existing '1'´s.
Following code needs as input just 1'ns, like 111 ore 11111. Don't put '0's on the tape otherwise the code doesn't work properly.
0,0,2,0,2,1
0,3,1,1,2,1
1,4,0,1,3,1
0,5,0,1,4,0
1,1,1,1,5,0
code is from wikipedia.de , for more information visit:
http:/ / de.wikipedia.org / wiki / Turingmaschine
or
http:/ / en.wikipedia.org / wiki / Turing_machine
End Rem



SuperStrict

Global States:Int = 5
Global Prog:Int[0,2,3] '[State],[False=0/True=1], 0=What_to_write,1=NextState(0=end),2=Headmovement (0=none,1=left,2=right)
Global Tape:TTape

If FileType("Tape.txt")
   Tape:TTape = TTape.Create(LoadString("Tape.txt"))
Else
   Tape:TTape = TTape.Create(1)'Default if no input file exists
EndIf

LoadProgram("AddOne.txt")

Tape.Output()
RunProgram(Tape)
Tape.Output()

Tape.Save("Tape.txt")

End



Type TTape
   Field content:String
   Field pos:Int
   
   Function Create:TTape(content:String)
      Local t:TTape = New TTape
      t.content = content
      t.pos = 0
      Return t
   End Function
   
   Method Save(path:String)
      SaveString content,path
   End Method
   
   Method Write(b:Byte)
      content = Left(content , pos) + b + Mid(content , pos+2)
   End Method
   
   Method Read:Byte()
      Return Byte(Mid(content , pos+1 , 1))
   End Method
   
   Method Move(m:Byte)'0=left, 1=right
      If m = 0
         If pos > 0
            pos:- 1
         ElseIf pos = 0
            content = "0" + content
         EndIf
      ElseIf m = 1
         If pos = Len(content)
            pos:+ 1
            content:+ "0"
         Else
            pos:+ 1
         EndIf
      EndIf
   End Method
   
   Method GetPos:Int()
      Return pos
   End Method
   
   Method Output()
      Print content+" ("+BinToInt(content)+")"
   End Method
End Type


Function LoadProgram(path:String)
   Local source:TStream = ReadFile(path)
   States = 0
   While Not Eof(source)
      ReadLine(source)
      States:+ 1
   Wend
   SeekStream source,0
   Prog = New Int[States+1,2,3]
   For Local i:Int = 1 To States
      Local line:String = ReadLine(source)
      Local pos:Int
      
         pos = Instr(line , ",")
      Prog[i , 0 , 0] = Byte Left(line , pos )
         line = Mid(line , pos + 1)
         pos = Instr(line , ",")
      Prog[i , 0 , 1] = Byte Left(line , pos )
         line = Mid(line , pos + 1)
         pos = Instr(line , ",")
      Prog[i , 0 , 2] = Byte Left(line , pos )
         line = Mid(line , pos + 1)
         pos = Instr(line , ",")
      Prog[i , 1 , 0] = Byte Left(line , pos )
         line = Mid(line , pos + 1)
         pos = Instr(line , ",")
      Prog[i , 1 , 1] = Byte Left(line , pos )
         line = Mid(line , pos + 1)
      Prog[i , 1 , 2] = Byte (line)
   Next
End Function

Function RunProgram(t:TTape)
   Local State:Int = 1
   While State > 0 And State <= States
      Local b:Byte = t.read()
      t.write(Prog[State , b , 0])
      DebugLog "State:"+State+" Pos:"+t.GetPos()+" read:"+b+" write:"+Prog[State,b,0]+" SetState:"+Prog[State,b,1]+" Movement: "+Prog[State,b,2]+" => "+t.content
      t.move(Prog[State , b , 2])
      State = Prog[State,b,1]
   Wend
End Function


Function BinToInt:Int(s:String)
   'DebugStop()
   Local pos:Int = Len(s)
   Local erg:Int
   For Local i:Int = pos To 1 Step -1
      DebugLog "2^" + (pos - i) + " * " + Mid(s , Pos - i + 1 , 1) + " = " + Int(Ceil(2 ^ (pos - i) ) )
      erg:+ Int(Ceil(2^(pos-i))) * Byte(Mid(s , Pos-i+1 , 1) )
   Next
   Return erg
End Function

1,0,2,0,1,1

0,2,1,1,2,1
1,0,2,0,2,1

0,0,2,0,2,1
0,3,1,1,2,1
1,4,0,1,3,1
0,5,0,1,4,0
1,1,1,1,5,0