Minimum Number of states for a Turing Machine

210 Views Asked by At

I am looking for a Turing Machine $M$ with $k$ states such that there is no other Turing Machine $M$' with fewer than $k$ states that recognizes the same language as $M$ (i.e., $L(M) = L(M')$). We suppose the tape alphabet is $\Gamma=\{0,1,b\}$ for all $TM$, hence we cannot use new symbols to represent states. Also, there's only one accepting and rejecting state and the result is written on the tape.