How to calculate the number of states in designing a Turing machine?

I would like to ask how to determine the number of states when designing a Turing machine from the description for a language? For example:

$\qquad \displaystyle L = \{wcw \mid w \in \{0,1\}^*\}.$

I mean how to know how many states are there in the set $Q$, with the information from the description of that language.

I think that given a decidable language $L$, you can always build a 2-states TM that recognizes it.

Indeed there exists a 2 state Universal Turing Machine $UTM_{2U}$ (with alphabet $|\Sigma| \geq 18$).

If $TM_i$ decides $L$ then $UTM_{2U}(i,x)$ decides $L$; so you can build a 2-states $TM_{2L}$ hard encoding $i$ in $UTM_{2U}$ but keeping only two states; the idea is:

• add $2|i||\Sigma|^{|i|}*|\Sigma|$ symbols to the alphabet that will represent the possible combinations of (state, head position, tape content, first symbol $\alpha$ of $x = \alpha x'$ on the tape) of $UTM_{2U}$ on input $(i,\alpha x')$

• adjust the transition table of $TM_{2L}$ in order to simulate the behaviour of $UTM_{2U}$ on the first $|i|+1$ characters of the tape using only the first cell of the tape (that initially will contain $\alpha$).

EDIT (alternate take :)

Given a generic $TM_L$ that recognizes $L$ there is an easier way to build an equivalent 2-states $TM_{2L}$.

I'll try to sketch its construction (anybody wants to check if it is correct? :)

Idea: simulate $TM_L$ using the tape to store at the same time the alphabet symbol of the original tape, plus the current state and head position of $TM_L$.

A single cell of the tape is a 5-tuple:

[(direction)(symbol)(current_state)(state_to_copy)]

that represents:

direction: 0 = we are scanning the tape from left to right
           1 = we are scanning the tape from right to left
symbol:    symbol from the alphabet of TM_L
current_state: if > 0 then the head position of TM_L is here and
               the state is current_state
state_to-copy: if > 0 then we are copying the next state to
               the left or right according to direction

Using the direction flag we can move from left to right and "execute" the
$TM_L$ transitions that moves the head to the right (i.e. we can copy the next head/state
to the right), then we can go back and "execute" the $TM_L$ transitions that moves
the head to the left (i.e. we can copy the next head/state to the left).

The transition table with two states is built in the following way:

STATE0

...from LEFT to RIGHT

// scan left to right until we found the cell with the head
Read(0, X, 0, 0)  -> Write(1, X, 0, 0)    stay in STATE0 and move R

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then add the
// following transition  which will start the copy of Qj on the right cell
Read(0, A, Qi, 0) -> Write(0, B, 0, Qj-1) enter STATE1 and move R

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then
// add the following transition (we will process it later):
Read(0, A, Qi, 0) -> Write(1, A, Qi, 0)   stay in STATE0 and move R

// if we are copying a state to the right continue:
Read(0, X, 0, Qj) -> Write(0, X, 0, Qj-1) enter STATE1 and move R

// when we reach a blank symbol, start moving from right to left
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move L

... from RIGHT to LEFT

// scan right to left until we found the cell with the head
Read(1, X, 0,  0) -> Write(0, X, 0, 0)    stay in STATE0 and move L

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then add the
// following transition which will start the copy of Qj on the left cell
Read(1, A, Qi, 0) -> Write(1, B, 0, Qj-1) enter STATE1 and move L

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then
// add the following transition (we will process it later):
Read(1, A, Qi, ) -> Write(0, A, Qi, 0)    stay in STATE0 and move R

// if we are copying a state to the left continue:
Read(1, X, 0, Qj) -> Write(1, X, 0, Qj-1) enter STATE1 and move L

// when we reach a blank symbol, start moving from left to right
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move R

STATE1

// we are copying the head/state to the right
Read(0, Y, Qk, 0) -> Write(0, Y, Qk+1, 0) enter STATE0 and move L

// we are copying the head/state to the left
Read(1, Y, Qk, 0) -> Write(1, Y, Qk+1, 0) enter STATE0 and move R

The 5-tuple (direction)(symbol)(current_state)(state_to_copy) must be encoded using a single symbol of $TM_{2L}$, so its alphabet size is:

$|\Sigma_{2L}| = 2 \times |\Sigma_L| \times |Q_L| \times |Q_L|$

P.S. with the same technique (if it is correct) a generic UTM can be converted to a 2-states UTM ... unfortunately we are not in 1956 :-)))

StackExchange Computer Science Q#4801, answer score: 3