Question

In this exercise, you are asked to prove that the busy beaver function BB : N → N is not computable. For any integer n ≥ 1, we define TM n to be the set of all Turing machines M, such that

• M has one tape,

• M has exactly n states,

• the tape alphabet of M is {0, 1, ✷}, and

• M terminates, when given the empty string ǫ as input.

For every Turing machine M ∈ TM_n, we define f(M) to be the number of ones on the tape, after the computation of M, on the empty input string, has terminated. The busy beaver function BB : N → N is defined as BB(n) := max{f(M) : M ∈ TM_n}, for every n ≥ 1. In words, BB(n) is the maximum number of ones that any Turing machine with n states can produce, when given the empty string as input, and assuming the Turing machine terminates on this input. Prove that the function BB is not computable.

Hint: Assume that BB is computable. Then there exists a Turing machine M that, for any given n ≥ 1, computes the value of BB(n). Fix a large integer n ≥ 1. Define (in plain English) a Turing machine that, when given the empty string as input, terminates and outputs a string consisting of more than BB(n) many ones.

Answer 1

Answer:

Given that:

Prove that the busy beaver function

Step 1:

The busy beaver function is defined as

for every  

Step 2:

n : number of states

Set of Turing machines with n states and binary alphabets ( 0,1 )

empty tape (all 0's)

if machine M, when started on e, hatts with [ k ]

otherwise

Step 3:

BB is turing non computable proof of contradiction :

Suppose there in some Turing machine   , where K is the number of states of the last 3 components

Can be implemented by K states, Q has 2k states

Step 4:

is non computable

Alternative proof :

The non-computability of B(n) can also be derived from the uncomputability of

Step 5:

Suppose in computable   can be determined by running all of the finitely many Turning machines many Turing machines M with n states , starting e. If a Turing machine is still running after B(n) steps . It is a non-halter.

Step 6:

can be determined and it proved take the max.