Quiz Solutions
1. We could. Given any program, we can simulate it on an n-state Turing machine that fits the criteria of S(n). If we know S(n), then we need only run the Turing machine for S(n) steps. If the machine halts before or on the S(n)-th step, then it halts. Otherwise, it will never halt, because S(n) is the maximum number of steps a halting TM, can take before halting.
2. Because it involved looking at every possible (significantly different) 3-state machines and proving that each of the ones that did not halt within 21 steps would never halt. This is not feasibly for n's much greater than 3 because the number of possible TM's grows exponentially.
Homework Solution
Here is a MATLAB solution.
function res = busy_beaver4() Val = zeros(16,1); f_ind = 11; ind = f_ind; state = 1; while state ~= 5 if state == 1 if Val(ind,end) == 0 new = rule_a0(Val,ind); elseif Val(ind,end) == 1 new = rule_a1(Val,ind); end elseif state == 2 if Val(ind,end) == 0 new = rule_b0(Val,ind); elseif Val(ind,end) == 1 new = rule_b1(Val,ind); end elseif state == 3 if Val(ind,end) == 0 new = rule_c0(Val,ind); elseif Val(ind,end) == 1 new = rule_c1(Val,ind); end elseif state == 4 if Val(ind,end) == 0 new = rule_d0(Val,ind); elseif Val(ind,end) == 1 new = rule_d1(Val,ind); end end Val = new{1}; ind = new{2}; state = new{3}; end dim2 = size(Val); [X,Y] = meshgrid([1-1:dim2(2)-1],[1-f_ind:dim2(1)-f_ind]); pcolor(X,Y,Val) ylabel('Position on the tape, starting position = 0', 'FontSize', 12) xlabel('Number of steps taken', 'FontSize', 12) title('Visualization of Steps of 4-state Busy Beaver', 'FontSize', 18) res = Val; end % a0 -> b1r a1 -> b1l function res = rule_a0(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 1; Val = [Val,ColVal]; ind = ind + 1; res = {Val,ind,2}; end function res = rule_a1(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 1; Val = [Val,ColVal]; ind = ind - 1; res = {Val,ind,2}; end % b0 -> a1l b1 -> c0l function res = rule_b0(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 1; Val = [Val,ColVal]; ind = ind - 1; res = {Val,ind,1}; end function res = rule_b1(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 0; Val = [Val,ColVal]; ind = ind - 1; res = {Val,ind,3}; end % c0 -> h1r c1 -> d1l function res = rule_c0(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 1; Val = [Val,ColVal]; ind = ind + 1; res = {Val,ind,5}; end function res = rule_c1(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 1; Val = [Val,ColVal]; ind = ind - 1; res = {Val,ind,4}; end % d0 -> d1r d1 -> a0r function res = rule_d0(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 1; Val = [Val,ColVal]; ind = ind + 1; res = {Val,ind,4}; end function res = rule_d1(Val, ind) dim = size(Val); ColVal = Val(:,dim(2)); ColVal(ind) = 0; Val = [Val,ColVal]; ind = ind + 1; res = {Val,ind,1}; end