Results 1 to 1 of 1

Thread: busy beaver Turing Machine simulator

Threaded View

Previous Post Previous Post   Next Post Next Post
  1. #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
    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
    Last edited by primo; 14-03-2017 at 21:13.

Similar Threads

  1. Anti gravity machine
    By ErosOlmi in forum Science
    Replies: 2
    Last Post: 24-12-2011, 01:39
  2. Man and machine must merge
    By Charles Pegge in forum Shout Box Area
    Replies: 8
    Last Post: 16-06-2011, 09:55
  3. ARMA 2 : The animal simulator :)
    By Petr Schreiber in forum Gaming
    Replies: 12
    Last Post: 27-06-2009, 17:38
  4. DEP and machine code
    By Petr Schreiber in forum Machine Code
    Replies: 4
    Last Post: 13-03-2008, 22:13

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •