Question

Show that the function \(B\left( n \right)\) cannot be computed by any Turing machine. (Hint: Assume that there is a Turing machine that computes \({\bf{B}}\left( {\bf{n}} \right)\) in binary. Build a Turing machine \({\bf{T}}\) that, starting with a blank tape, writes \({\bf{n}}\) down in binary, computes \({\bf{B}}\left( {\bf{n}} \right)\) in binary, and converts \({\bf{B}}\left( {\bf{n}} \right)\) from binary to unary. Show that for sufficiently large \({\bf{n}}\), the number of states of \({\bf{T}}\) is less than \({\bf{B}}\left( {\bf{n}} \right)\), leading to a contradiction.

Short answer

\({\bf{B}}\left( {\bf{n}} \right)\) cannot be computed by any Turing machine.

Step-by-step solution

Step \(1\): Definition

A Turing machine \(T = \left( {S,I,f,{s_0}} \right)\) consists of a finite set \(S\) of states, an alphabet \(I\) containing the blank symbol \(B\), a partial function \(f\) from \(S \ast I\) to \(S \ast I \ast \{ R,L\} \), and a starting state \({s_0}\).

Note: The partial function \(f\) is often represented as 5 -tuples.

Given: \(B\left( n \right) = \) maximum number of \(1's\)that a Turing machine with \(n\) states with alphabet \(\left\{ {1,{\bf{ }}B} \right\}\) may print on an initially blank tape.

To proof: \(B\left( n \right)\) cannot be computed by any Turing machine.

Proof of contradiction

Let’s assume, for the sake of contradiction, that there exists a Turing machine \(T\) that computes \(B\left( n \right)\) in binary.

Let \({\bf{T'}}\) then be the Turing machine that starts with a blank tape, writes \(n\) in binary, computes \(B\left( n \right)\) in binary and finally converts \(B\left( n \right)\) from binary to unary.

Since the Turing machine \(T\) exists, the Turing machine \(T'\) needs to exist as well, as there exist Turing machines that write \(n\) in binary starting with a blank tape (for example by using 1 state per 1 that needs to be written down) and there exist Turing machines that convert from binary to unary (as you remove any zeros and a 1 in the \(n\)th position is replaced by \(n\) repeated \(1's\)).

Computation of \({\bf{B}}\left( {\bf{n}} \right)\)

Since \(B\left( n \right)\) can become infinitely large and since the number of states \(k\) of \(T'\) needs to be finite (by definition of a Turing machine), the number of states of \(T'\) need to be less than \(B\left( n \right)\) at some position. Thus, there needs to exist a sufficiently large integer \(m\) such that the number of states \(k\) of \(T'\) with input \(m\) is less than \(m\).

However, by definition of \(B\left( n \right)\), you will require at least \(m\) states to compute \(B\left( m \right)\) (as \(B\left( m \right)\) is a statement about Turing machines with \(m\) states) and thus you derived a contradiction.

This then implies that our assumption "there exists a Turing machine \(T\) that computes \(B\left( n \right)\) in binary" is incorrect and thus \(B\left( n \right)\) cannot be computed by any Turing machine.

Hence, \(B\left( n \right)\) cannot be computed by any Turing machine.