<p>Say that a Turing machine $U$ is <em>universal for a class $\mathcal{C}$ of languages</em> 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.$$</p>

<p>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"?</p>

CC BY-SA 3.0
2015-08-18T12:02:44.317Z
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
Marzio De Biasi
CC BY-SA 3.0
2015-08-18T13:28:56.920Z
There are already very small universal turing machines. For instance with 5 states and 5 symbols, or 15 states and 2 symbols (http://www.ini.uzh.ch/~tneary/tneary_Thesis.pdf). Why would universality with respect to a fixed class be interesting?
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-08-18T15:39:16.470Z
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".
vzn
CC BY-SA 3.0
2015-08-18T16:24:41.460Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2015-08-18T16:33:57.047Z
a few further thoughts. a somewhat "rare" area where # of states show up & is measured is [busy beaver research](https://en.wikipedia.org/wiki/Busy_beaver), 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 [chat]
vzn
CC BY-SA 3.0
2015-08-19T14:52:41.667Z
@MichaëlCadilhac what I'm trying to say is that extremely small TMs already satisfy the conditions of the question for any computable class of languages, and hence for CFLs and CSLs. In other words, there are so few options of sizes (n_states,n_alphabet) which do not admit a universal TM, that the question about minimum size for a given class doesn't seem to make much sense without further restrictions on the nature of the UTMs. Continue...
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-08-19T14:52:50.397Z
It is known that there is no (2,2) UTMs. But it seems to be open whether there is a (2,3) UTM. If there is such a machine, your only options would be TMs smaller than (2,2). Maybe a meaningful question would be to determine which classes these machines below (2,2) are universal for.
Mateus de Oliveira Oliveira
<fl.formal-languages><universal-turing-machines>
How much smaller can universal Turing machines get if they only need to be universal for a subclass?
Michaël Cadilhac
# How much smaller can universal Turing machines get if they only need to be universal for a subclass?

(Asked by: username_0 on 2015-08-17)

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"?

**Tags:** fl.formal-languages, universal-turing-machines
> **Comments:**
> **username_1**: 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  
> **username_2**: There are already very small universal turing machines. For instance with 5 states and 5 symbols, or 15 states and 2 symbols (http://www.ini.uzh.ch/~tneary/tneary_Thesis.pdf). Why would universality with respect to a fixed class be interesting?  
> **username_3**: 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".  
> **username_0**: 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.  
> **username_3**: a few further thoughts. a somewhat "rare" area where # of states show up & is measured is [busy beaver research](https://en.wikipedia.org/wiki/Busy_beaver), 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 [chat]  
> **username_2**: @MichaëlCadilhac what I'm trying to say is that extremely small TMs already satisfy the conditions of the question for any computable class of languages, and hence for CFLs and CSLs. In other words, there are so few options of sizes (n_states,n_alphabet) which do not admit a universal TM, that the question about minimum size for a given class doesn't seem to make much sense without further restrictions on the nature of the UTMs. Continue...  
> **username_2**: It is known that there is no (2,2) UTMs. But it seems to be open whether there is a (2,3) UTM. If there is such a machine, your only options would be TMs smaller than (2,2). Maybe a meaningful question would be to determine which classes these machines below (2,2) are universal for.  

---

## 0 answers

