#!/usr/local/bin/vtm -L -sA -t0 -b0 -S # ##echo A busy beaver with 4 states and 2 symbols # # See http://www.logique.jussieu.fr/~michel/bbc.html # # The busy beaver problem is : # If a turning machine has n (here n=5) states, # what is the largest number of 1s it can print on a blank (0s) # tape before halting? # # -L : turn on echo # -sA : start in state 'S' # -t0 : start with tape '0' # -b0 : blank char is '0' # -S : show state at the end of each line # -V : verbose => show tape, blank, start before running # # Here's the best know machine with 4 states (A,B,C,D) and two symbols (0,1) # # Brady (1983) # s(M) = S(4,2) = 107 # sigma(M) = Sigma(4,2) = 13 # # in 0 1 # --------------------------- # | A 1RB 1LB # | B 1LA 0LC # | C 1RH 1LD # | D 1RD 0RA # # H is the "halt" state. # # Transition table is defined as # in state, in symbol, out state, out symbol, move (R or L) # A, 0, B, 1, R A, 1, B, 1, L B, 0, A, 1, L B, 1 C, 0, L C, 0, H, 1, R C, 1, D, 1, L D, 0, D, 1, R D, 1, A, 0, R # The output is # offset: tape : state # with the current machine position given by <>. # (The "offset" is just how far to shift the tape right # each time the machne tries to run off the left side.) # $ ./beaver_4.vtm # A busy beaver with 4 states and 2 symbols # 0: <0>: A # 0: 1<0>: B # 0: <1>1 : A # 1: <0>1 1 : B # 2: <0>1 1 1 : A # 2: 1<1>1 1 : B # 2: <1>0 1 1 : C # 3: <0>1 0 1 1 : D # 3: 1<1>0 1 1 : D # 3: 1 0<0>1 1 : A # 3: 1 0 1<1>1 : B # 3: 1 0<1>0 1 : C # 3: 1<0>1 0 1 : D # 3: 1 1<1>0 1 : D # 3: 1 1 0<0>1 : A # 3: 1 1 0 1<1>: B # 3: 1 1 0<1>0 : C # 3: 1 1<0>1 0 : D # 3: 1 1 1<1>0 : D # 3: 1 1 1 0<0>: A # 3: 1 1 1 0 1<0>: B # 3: 1 1 1 0<1>1 : A # 3: 1 1 1<0>1 1 : B # 3: 1 1<1>1 1 1 : A # 3: 1<1>1 1 1 1 : B # 3: <1>0 1 1 1 1 : C # 4: <0>1 0 1 1 1 1 : D # 4: 1<1>0 1 1 1 1 : D # 4: 1 0<0>1 1 1 1 : A # 4: 1 0 1<1>1 1 1 : B # 4: 1 0<1>0 1 1 1 : C # 4: 1<0>1 0 1 1 1 : D # 4: 1 1<1>0 1 1 1 : D # 4: 1 1 0<0>1 1 1 : A # 4: 1 1 0 1<1>1 1 : B # 4: 1 1 0<1>0 1 1 : C # 4: 1 1<0>1 0 1 1 : D # 4: 1 1 1<1>0 1 1 : D # 4: 1 1 1 0<0>1 1 : A # 4: 1 1 1 0 1<1>1 : B # 4: 1 1 1 0<1>0 1 : C # 4: 1 1 1<0>1 0 1 : D # 4: 1 1 1 1<1>0 1 : D # 4: 1 1 1 1 0<0>1 : A # 4: 1 1 1 1 0 1<1>: B # 4: 1 1 1 1 0<1>0 : C # 4: 1 1 1 1<0>1 0 : D # 4: 1 1 1 1 1<1>0 : D # 4: 1 1 1 1 1 0<0>: A # 4: 1 1 1 1 1 0 1<0>: B # 4: 1 1 1 1 1 0<1>1 : A # 4: 1 1 1 1 1<0>1 1 : B # 4: 1 1 1 1<1>1 1 1 : A # 4: 1 1 1<1>1 1 1 1 : B # 4: 1 1<1>0 1 1 1 1 : C # 4: 1<1>1 0 1 1 1 1 : D # 4: 1 0<1>0 1 1 1 1 : A # 4: 1<0>1 0 1 1 1 1 : B # 4: <1>1 1 0 1 1 1 1 : A # 5: <0>1 1 1 0 1 1 1 1 : B # 6: <0>1 1 1 1 0 1 1 1 1 : A # 6: 1<1>1 1 1 0 1 1 1 1 : B # 6: <1>0 1 1 1 0 1 1 1 1 : C # 7: <0>1 0 1 1 1 0 1 1 1 1 : D # 7: 1<1>0 1 1 1 0 1 1 1 1 : D # 7: 1 0<0>1 1 1 0 1 1 1 1 : A # 7: 1 0 1<1>1 1 0 1 1 1 1 : B # 7: 1 0<1>0 1 1 0 1 1 1 1 : C # 7: 1<0>1 0 1 1 0 1 1 1 1 : D # 7: 1 1<1>0 1 1 0 1 1 1 1 : D # 7: 1 1 0<0>1 1 0 1 1 1 1 : A # 7: 1 1 0 1<1>1 0 1 1 1 1 : B # 7: 1 1 0<1>0 1 0 1 1 1 1 : C # 7: 1 1<0>1 0 1 0 1 1 1 1 : D # 7: 1 1 1<1>0 1 0 1 1 1 1 : D # 7: 1 1 1 0<0>1 0 1 1 1 1 : A # 7: 1 1 1 0 1<1>0 1 1 1 1 : B # 7: 1 1 1 0<1>0 0 1 1 1 1 : C # 7: 1 1 1<0>1 0 0 1 1 1 1 : D # 7: 1 1 1 1<1>0 0 1 1 1 1 : D # 7: 1 1 1 1 0<0>0 1 1 1 1 : A # 7: 1 1 1 1 0 1<0>1 1 1 1 : B # 7: 1 1 1 1 0<1>1 1 1 1 1 : A # 7: 1 1 1 1<0>1 1 1 1 1 1 : B # 7: 1 1 1<1>1 1 1 1 1 1 1 : A # 7: 1 1<1>1 1 1 1 1 1 1 1 : B # 7: 1<1>0 1 1 1 1 1 1 1 1 : C # 7: <1>1 0 1 1 1 1 1 1 1 1 : D # 7: 0<1>0 1 1 1 1 1 1 1 1 : A # 7: <0>1 0 1 1 1 1 1 1 1 1 : B # 8: <0>1 1 0 1 1 1 1 1 1 1 1 : A # 8: 1<1>1 0 1 1 1 1 1 1 1 1 : B # 8: <1>0 1 0 1 1 1 1 1 1 1 1 : C # 9: <0>1 0 1 0 1 1 1 1 1 1 1 1 : D # 9: 1<1>0 1 0 1 1 1 1 1 1 1 1 : D # 9: 1 0<0>1 0 1 1 1 1 1 1 1 1 : A # 9: 1 0 1<1>0 1 1 1 1 1 1 1 1 : B # 9: 1 0<1>0 0 1 1 1 1 1 1 1 1 : C # 9: 1<0>1 0 0 1 1 1 1 1 1 1 1 : D # 9: 1 1<1>0 0 1 1 1 1 1 1 1 1 : D # 9: 1 1 0<0>0 1 1 1 1 1 1 1 1 : A # 9: 1 1 0 1<0>1 1 1 1 1 1 1 1 : B # 9: 1 1 0<1>1 1 1 1 1 1 1 1 1 : A # 9: 1 1<0>1 1 1 1 1 1 1 1 1 1 : B # 9: 1<1>1 1 1 1 1 1 1 1 1 1 1 : A # 9: <1>1 1 1 1 1 1 1 1 1 1 1 1 : B # 10: <0>0 1 1 1 1 1 1 1 1 1 1 1 1 : C # 10: 1<0>1 1 1 1 1 1 1 1 1 1 1 1 : H # --- with the offsets adjusted properly and zeros added left and right ---- # # 0 0 0 0 0 0 0 0 0 0 0<0>0 0 0 0 0 A # 0 0 0 0 0 0 0 0 0 0 0 1<0>0 0 0 0 B # 0 0 0 0 0 0 0 0 0 0 0<1>1 0 0 0 0 A # 0 0 0 0 0 0 0 0 0 0<0>1 1 0 0 0 0 B # 0 0 0 0 0 0 0 0 0<0>1 1 1 0 0 0 0 A # 0 0 0 0 0 0 0 0 0 1<1>1 1 0 0 0 0 B # 0 0 0 0 0 0 0 0 0<1>0 1 1 0 0 0 0 C # 0 0 0 0 0 0 0 0<0>1 0 1 1 0 0 0 0 D # 0 0 0 0 0 0 0 0 1<1>0 1 1 0 0 0 0 D # 0 0 0 0 0 0 0 0 1 0<0>1 1 0 0 0 0 A # 0 0 0 0 0 0 0 0 1 0 1<1>1 0 0 0 0 B # 0 0 0 0 0 0 0 0 1 0<1>0 1 0 0 0 0 C # 0 0 0 0 0 0 0 0 1<0>1 0 1 0 0 0 0 D # 0 0 0 0 0 0 0 0 1 1<1>0 1 0 0 0 0 D # 0 0 0 0 0 0 0 0 1 1 0<0>1 0 0 0 0 A # 0 0 0 0 0 0 0 0 1 1 0 1<1>0 0 0 0 B # 0 0 0 0 0 0 0 0 1 1 0<1>0 0 0 0 0 C # 0 0 0 0 0 0 0 0 1 1<0>1 0 0 0 0 0 D # 0 0 0 0 0 0 0 0 1 1 1<1>0 0 0 0 0 D # 0 0 0 0 0 0 0 0 1 1 1 0<0>0 0 0 0 A # 0 0 0 0 0 0 0 0 1 1 1 0 1<0>0 0 0 B # 0 0 0 0 0 0 0 0 1 1 1 0<1>1 0 0 0 A # 0 0 0 0 0 0 0 0 1 1 1<0>1 1 0 0 0 B # 0 0 0 0 0 0 0 0 1 1<1>1 1 1 0 0 0 A # 0 0 0 0 0 0 0 0 1<1>1 1 1 1 0 0 0 B # 0 0 0 0 0 0 0 0<1>0 1 1 1 1 0 0 0 C # 0 0 0 0 0 0 0<0>1 0 1 1 1 1 0 0 0 D # 0 0 0 0 0 0 0 1<1>0 1 1 1 1 0 0 0 D # 0 0 0 0 0 0 0 1 0<0>1 1 1 1 0 0 0 A # 0 0 0 0 0 0 0 1 0 1<1>1 1 1 0 0 0 B # 0 0 0 0 0 0 0 1 0<1>0 1 1 1 0 0 0 C # 0 0 0 0 0 0 0 1<0>1 0 1 1 1 0 0 0 D # 0 0 0 0 0 0 0 1 1<1>0 1 1 1 0 0 0 D # 0 0 0 0 0 0 0 1 1 0<0>1 1 1 0 0 0 A # 0 0 0 0 0 0 0 1 1 0 1<1>1 1 0 0 0 B # 0 0 0 0 0 0 0 1 1 0<1>0 1 1 0 0 0 C # 0 0 0 0 0 0 0 1 1<0>1 0 1 1 0 0 0 D # 0 0 0 0 0 0 0 1 1 1<1>0 1 1 0 0 0 D # 0 0 0 0 0 0 0 1 1 1 0<0>1 1 0 0 0 A # 0 0 0 0 0 0 0 1 1 1 0 1<1>1 0 0 0 B # 0 0 0 0 0 0 0 1 1 1 0<1>0 1 0 0 0 C # 0 0 0 0 0 0 0 1 1 1<0>1 0 1 0 0 0 D # 0 0 0 0 0 0 0 1 1 1 1<1>0 1 0 0 0 D # 0 0 0 0 0 0 0 1 1 1 1 0<0>1 0 0 0 A # 0 0 0 0 0 0 0 1 1 1 1 0 1<1 0 0 0 B # 0 0 0 0 0 0 0 1 1 1 1 0<1>0 0 0 0 C # 0 0 0 0 0 0 0 1 1 1 1<0>1 0 0 0 0 D # 0 0 0 0 0 0 0 1 1 1 1 1<1>0 0 0 0 D # 0 0 0 0 0 0 0 1 1 1 1 1 0<0>0 0 0 A # 0 0 0 0 0 0 0 1 1 1 1 1 0 1<0>0 0 B # 0 0 0 0 0 0 0 1 1 1 1 1 0<1>1 0 0 A # 0 0 0 0 0 0 0 1 1 1 1 1<0>1 1 0 0 B # 0 0 0 0 0 0 0 1 1 1 1<1>1 1 1 0 0 A # 0 0 0 0 0 0 0 1 1 1<1>1 1 1 1 0 0 B # 0 0 0 0 0 0 0 1 1<1>0 1 1 1 1 0 0 C # 0 0 0 0 0 0 0 1<1>1 0 1 1 1 1 0 0 D # 0 0 0 0 0 0 0 1 0<1>0 1 1 1 1 0 0 A # 0 0 0 0 0 0 0 1<0>1 0 1 1 1 1 0 0 B # 0 0 0 0 0 0 0<1>1 1 0 1 1 1 1 0 0 A # 0 0 0 0 0 0<0>1 1 1 0 1 1 1 1 0 0 B # 0 0 0 0 0<0>1 1 1 1 0 1 1 1 1 0 0 A # 0 0 0 0 0 1<1>1 1 1 0 1 1 1 1 0 0 B # 0 0 0 0 0<1>0 1 1 1 0 1 1 1 1 0 0 C # 0 0 0 0<0>1 0 1 1 1 0 1 1 1 1 0 0 D # 0 0 0 0 1<1>0 1 1 1 0 1 1 1 1 0 0 D # 0 0 0 0 1 0<0>1 1 1 0 1 1 1 1 0 0 A # 0 0 0 0 1 0 1<1>1 1 0 1 1 1 1 0 0 B # 0 0 0 0 1 0<1>0 1 1 0 1 1 1 1 0 0 C # 0 0 0 0 1<0>1 0 1 1 0 1 1 1 1 0 0 D # 0 0 0 0 1 1<1>0 1 1 0 1 1 1 1 0 0 D # 0 0 0 0 1 1 0<0>1 1 0 1 1 1 1 0 0 A # 0 0 0 0 1 1 0 1<1>1 0 1 1 1 1 0 0 B # 0 0 0 0 1 1 0<1>0 1 0 1 1 1 1 0 0 C # 0 0 0 0 1 1<0>1 0 1 0 1 1 1 1 0 0 D # 0 0 0 0 1 1 1<1>0 1 0 1 1 1 1 0 0 D # 0 0 0 0 1 1 1 0<0>1 0 1 1 1 1 0 0 A # 0 0 0 0 1 1 1 0 1<1>0 1 1 1 1 0 0 B # 0 0 0 0 1 1 1 0<1>0 0 1 1 1 1 0 0 C # 0 0 0 0 1 1 1<0>1 0 0 1 1 1 1 0 0 D # 0 0 0 0 1 1 1 1<1>0 0 1 1 1 1 0 0 D # 0 0 0 0 1 1 1 1 0<0>0 1 1 1 1 0 0 A # 0 0 0 0 1 1 1 1 0 1<0>1 1 1 1 0 0 B # 0 0 0 0 1 1 1 1 0<1>1 1 1 1 1 0 0 A # 0 0 0 0 1 1 1 1<0>1 1 1 1 1 1 0 0 B # 0 0 0 0 1 1 1<1>1 1 1 1 1 1 1 0 0 A # 0 0 0 0 1 1<1>1 1 1 1 1 1 1 1 0 0 B # 0 0 0 0 1<1>0 1 1 1 1 1 1 1 1 0 0 C # 0 0 0 0<1>1 0 1 1 1 1 1 1 1 1 0 0 D # 0 0 0 0 0<1>0 1 1 1 1 1 1 1 1 0 0 A # 0 0 0 0<0>1 0 1 1 1 1 1 1 1 1 0 0 B # 0 0 0<0>1 1 0 1 1 1 1 1 1 1 1 0 0 A # 0 0 0 1<1>1 0 1 1 1 1 1 1 1 1 0 0 B # 0 0 0<1>0 1 0 1 1 1 1 1 1 1 1 0 0 C # 0 0<0>1 0 1 0 1 1 1 1 1 1 1 1 0 0 D # 0 0 1<1>0 1 0 1 1 1 1 1 1 1 1 0 0 D # 0 0 1 0<0>1 0 1 1 1 1 1 1 1 1 0 0 A # 0 0 1 0 1<1>0 1 1 1 1 1 1 1 1 0 0 B # 0 0 1 0<1>0 0 1 1 1 1 1 1 1 1 0 0 C # 0 0 1<0>1 0 0 1 1 1 1 1 1 1 1 0 0 D # 0 0 1 1<1>0 0 1 1 1 1 1 1 1 1 0 0 D # 0 0 1 1 0<0>0 1 1 1 1 1 1 1 1 0 0 A # 0 0 1 1 0 1<0>1 1 1 1 1 1 1 1 0 0 B # 0 0 1 1 0<1>1 1 1 1 1 1 1 1 1 0 0 A # 0 0 1 1<0>1 1 1 1 1 1 1 1 1 1 0 0 B # 0 0 1<1>1 1 1 1 1 1 1 1 1 1 1 0 0 A # 0 <1>1 1 1 1 1 1 1 1 1 1 1 1 0 0 B # 0<0>0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 C # 0 1<0>1 1 1 1 1 1 1 1 1 1 1 1 0 0 HALT # #