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
3_states_TM.PNGbusy_beaver_3_states.PNG
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
Dim HeadPos, Status As Long
'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
'-----------------------------------------------
HeadPos = 500 ' position the machine printer HeadPos at 500
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
If tape(HeadPos) = 0 Then
tape(HeadPos) = a(1,status)
HeadPos = HeadPos + a(2, status)
status = a(3, status)
If status = 9 Then '9 is for Halt
Exit For
End If
Else 'If tape(HeadPos) = 1
tape(HeadPos) = b(1,status)
HeadPos = HeadPos + b(2,status)
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)
If HeadPos > lastOne Then
lastOne = HeadPos
ElseIf HeadPos < firstOne Then
firstOne = HeadPos
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:
4_states_TM.PNG
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
Dim HeadPos, Status As Long
'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
'------------------------------------------
HeadPos = 500 ' position the machine printer HeadPosPos at 500
firstOne = 500: lastOne = 500 'keep track of lowest and hightest "1" positions
Status = 1 'begins with a machine state =1
HeadPos = 500
Status = 1
For i=1 To 1000
If tape(HeadPos) = 0 Then
tape(HeadPos) = a(1,status)
HeadPos = HeadPos + a(2,status)
status = a(3,status)
If status = 9 Then '9 is for Halt
Exit For
End If
Else 'If tape(HeadPos) = 1
tape(HeadPos) = b(1,status)
HeadPos = HeadPos + b(2,status)
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)
If HeadPos > lastOne Then
lastOne = HeadPos
ElseIf HeadPos < firstOne Then
firstOne = HeadPos
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
http://wikisend.com/download/595566/busy_beaver_TM.pdf
Bookmarks