Say that a Turing machine $U$ is universal for a class $\mathcal{C}$ of languages if for any language $L \in \mathcal{C}$, there is a word $w_L$ with: $$(\forall w)\quad w \in L \Leftrightarrow U(w_L, w) \text{ accepts}\enspace.$$

What is an upper bound for the size of $U$ for the classes of regular languages, CFLs, or CSLs? What is the complexity of the function taking a grammar for a language $L$ in input and outputting $w_L$ for this upper bound? Does it change anything if the negation of "$U$ accepts" is taken to be "$U$ rejects" or "$U$ does not halt"?

  • $\begingroup$ A trivial upper bound is given by the size of the smallest universal TM (that can simulate a generic TM): in this case $w_L $ is simply the program that recognize the regular expression or the CF language L $\endgroup$ – Marzio De Biasi Aug 18 '15 at 12:02
  • 2
    $\begingroup$ There are already very small universal turing machines. For instance with 5 states and 5 symbols, or 15 states and 2 symbols (ini.uzh.ch/~tneary/tneary_Thesis.pdf). Why would universality with respect to a fixed class be interesting? $\endgroup$ – Mateus de Oliveira Oliveira Aug 18 '15 at 13:28
  • $\begingroup$ you refer to "size of U". is that # of states? # of states of TMs, another kind of "complexity", is not studied a whole lot in general in CS, it is often abstracted away... alas a lot of it is subject to constraints of "Kolmogorov complexity undecidability". $\endgroup$ – vzn Aug 18 '15 at 15:39
  • 1
    $\begingroup$ Marzio: Thanks; I'm precisely searching for a slightly better machine. Mateus: Careful there, I certainly did not say that universality with respect to a class is interesting ☺ I wouldn't be in TCS if I were only preoccupied by interesting stuff! vzn: Size of $U$ was consciously blurry, allowing for any interesting trade-off between states, symbols, and even instructions. $\endgroup$ – Michaël Cadilhac Aug 18 '15 at 16:24
  • $\begingroup$ a few further thoughts. a somewhat "rare" area where # of states show up & is measured is busy beaver research, a more "empirical" area that Neary's research (just cited by MdOO above) also impinges on. RJLipton has also commented in his blog on study/ dynamics of # of states of TMs as a somewhat open area of complexity research. more in Theoretical Computer Science Chat $\endgroup$ – vzn Aug 18 '15 at 16:33

Your Answer

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

Browse other questions tagged or ask your own question.