# Thread: busy beaver Turing Machine simulator

1. ## busy beaver Turing Machine simulator

if a Turing Machine with n possible states begins work on a tape filled with O's, what is the largest number of 1's it can print on the tape before coming to a stop? this is the problem of the busy beaver TM.
Turing Machine is made from a tape filled with zeroes, and a printer head which prints either 1 or zero on the tape and it can move left or right according to instructions (or say a program) in a control unit, the control unit can have states such as 3 states or 4 or more. the control unit itself is 2 parts , one part run if the head read 0 from the tape, the second part run if the head read 1 from the tape . look the attached picture 3_states_TM.png which equivalent to picture busy_beaver_3_states.png
look the article in the link below

i have replaced left move by -1 and R move by 1. the halt replaced by 9

3 states machine, halt after 13 iterations, and have 6 "1"'s
```Uses "Console"
Dim i, lastOne, firstOne As Long
Dim a(3,3) As Long
Dim b(3,3) As Long
Dim tape(1000) As Byte

'control Unit:
'-----------------------------------------------
'note the machine state (status) in the second column
a(1,1)= 1, 1,2 'equal to: a(1,1)=1: a(2,1)=1: a(3,1)=2
a(1,2)= 1,-1,1
a(1,3)= 1,-1,2

b(1,1)= 1,-1,3
b(1,2)= 1, 1,2
b(1,3)= 1, 9,9 ' 9 means Halt the program
'-----------------------------------------------

firstOne = 500: lastOne = 500 'keep track of lowest and hightest "1" positions
Status = 1 'begins with a machine state =1

For i=1 To 1000

status = a(3, status)
If status = 9 Then '9 is for Halt
Exit For
End If

status = b(3,status)
If status = 9 Then
Exit For
End If
End If
'find the position of the first occurence of the "1"
'last occurence of "1" is stored in lastOne variable
PrintL Join\$(tape, "", "", firstOne-10, lastOne+10)

End If
Next
PrintL Join\$(tape, "", "", firstOne-10, lastOne+10)
PrintL
PrintL "number of iterations = "+Str\$(i)
PrintL "Press a key to end program"

'---Wait for a key press
WaitKey
```
4 states machine:

1 ---- 1R2
2 ---- 1L1
3 ---- 1R9
4 ---- 1R4

1 ---- 1L2
2 ---- 0L3
3 ---- 1L4
4 ---- 0R1

iterate for 107 times, and prints 13 "1"s

```Uses "Console"
Dim i, firstOne, lastOne As Long
String onesString
Dim a(4,4) As Long
Dim b(4,4) As Long
Dim tape(1000) As Byte
'control Unit:
'------------------------------------------
'note the machine state (status) in the second column
a(1,1)= 1,1, 2 'equal to: a(1,1)=1: a(2,1)=1: a(3,1)=2
a(1,2)= 1,-1,1
a(1,3)= 1,1, 9 ' 9 means Halt the program
a(1,4)= 1,1, 4

b(1,1)= 1,-1,2
b(1,2)= 0,-1,3
b(1,3)= 1,-1,4
b(1,4)= 0, 1,1
'------------------------------------------

firstOne = 500: lastOne = 500 'keep track of lowest and hightest "1" positions
Status = 1 'begins with a machine state =1

Status = 1
For i=1 To 1000
status = a(3,status)
If status = 9 Then '9 is for Halt
Exit For
End If
status = b(3,status)
If status = 9 Then '9 is for Halt
Exit For
End If
End If

'find the position of the first occurence of the "1"
'last occurence of "1" is stored in lastOne variable
PrintL Join\$(tape, "", "", firstOne-10, lastOne+10)

End If
Next
PrintL Join\$(tape, "", "", firstOne-10, lastOne+10)
PrintL
PrintL "number of iterations = "+Str\$(i)
PrintL "Press a key to end program"
'---Wait for a key press
WaitKey
```
any other versions i will be glad
ref:
https://en.wikipedia.org/wiki/Busy_beaver