5
$\begingroup$

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.

$\endgroup$

migrated from cstheory.stackexchange.com Sep 29 '12 at 20:50

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ Note that what you want is closely related to Kolmogorov complexity, which is uncomputable even for a single string. Also, how would the description of the language be given to the TM as input? $\endgroup$ – Raphael Sep 29 '12 at 20:59
  • 1
    $\begingroup$ Hmmm... If you mean a function that translates $L$ into $|Q|$, then none exists. But for a specific language - construct a TM that recognizes it, and count the number of states you used.. (there are many TM's; since you don't ask about the minimal one - you can just find out yourself for a specific TM). $\endgroup$ – Ran G. Sep 29 '12 at 21:16
  • $\begingroup$ @RanG. Depending on how the (decidable) language is given, this would even work in general. Translations between different descriptions are often computable, so we can construct some TM explicitly and count the states. I understood the question to ask for the minimum, though. Chau? $\endgroup$ – Raphael Sep 30 '12 at 16:32
  • $\begingroup$ @Raphael "Kolmogorov complexity, which is uncomputable even for a single string" -- No, the Kolmogorov complexity of a single string is an integer, hence computable. $\endgroup$ – r.e.s. Oct 2 '12 at 13:59
  • $\begingroup$ @r.e.s. Mincing words there; the problem/function "given a string, compute its Kolmogorov complexity" is not computable. Therefore, I consider it unlikely that is similar measure of whole languages is computable. $\endgroup$ – Raphael Oct 2 '12 at 17:27
3
$\begingroup$

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 :-)))

$\endgroup$
2
$\begingroup$

If there is a Turing machine that can compute a given language at all, which in your case there is, then there must be at least one such machine, which the number of its states are no more than any other alike TM, i.e. You may always ask what is the minimal TM (with minimum number of states) which could accept a given language (and anticipate infinity, if the language can not be generated by an unrestricted grammar). But, as far as I know, this is a deep and difficult question and I imagine no one knows a general description of such relation, except for restricted cases. Otherwise, my hope is an expert would join this question and give us some light. (I have assumed that the number of alphabets is some constant, not subject to manipulation)

$\endgroup$
0
$\begingroup$

it has been known since Shannon 1956 that "small" (in either states or alphabets) universal Turing machines exist and there is a long history of their study, see [1] for a survey. this implies that any Turing machine can be converted to those universal Turing machines as Vor sketches out in his answer as an example. there is a systematic study of this subject in Kolmogorov complexity and the "minimal description". but basically its tightly coupled with incompleteness phenomena such that the minimum description is not really computable in general.

[1] Small universal Turing machines by Neary

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy