1
$\begingroup$

Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all languages and remove a few.")

For instance, I thought of the set of recursive or recursively enumerable languages, but these are countable. Perhaps some set in the arithmetic hierarchy?

This is probably a very easy question, and I'm just being silly.

$\endgroup$
4
  • $\begingroup$ "Perhaps some set in the arithmetic hierarchy?" Wouldn't this be countable by what you just said about recursive languages? $\endgroup$ Nov 3, 2009 at 0:34
  • $\begingroup$ There are many easy answers, as the answers coming in so far demonstrate. What is far harder, I think, is to come up with a set of languages that arises naturally and is uncountable for a nontrivial (and interesting!) reason. $\endgroup$ Nov 3, 2009 at 1:08
  • $\begingroup$ Yes, that is a good question. A natural language that isn't constructed for the purpose of making it uncountable. $\endgroup$
    – Rune
    Nov 3, 2009 at 1:21
  • $\begingroup$ May I point you to my humble questions concerning "naturality": mathoverflow.net/questions/14281/…, very much in the vein of your "remove a few"? $\endgroup$ Mar 5, 2010 at 16:22

4 Answers 4

5
$\begingroup$

One way to take the question is to ask for a set of languages, for instance a complexity class, which is uncountable "for a good reason". In other words, that people study the class for some substantially different reason, and it's clearly convenient for it to be uncountable.

Probably the most common example is the class P/poly. This can be defined as polynomial-time computations with polynomial-length advice strings. (An advice string is any extra information that depends on the length of the input, but not on the specific value of the input.) By a famous structure theorem, it is also computations performed by polynomial-sized circuits on n input bits, without the requirement that the circuits can be built quickly by a Turing machine. This is clearly not a countable set of langauges, because anything recursive or non-recursive can be done with the input length.

On the other hand, it is a very useful class and construction. A stronger version of the P vs NP problem, inspired by circuit formulations of P vs NP, conjectures that NP is not contained in P/poly. And it is a theorem that BPP (randomized polynomial time) is contained in P/poly.

$\endgroup$
1
  • $\begingroup$ Very nice! Although I couldn't express exactly what I was looking for, you've answered what I wanted. I guess P/poly doesn't have any complete problems under any sort of Turing reduction, since there are just countably many reductions to go around. $\endgroup$
    – Rune
    Nov 3, 2009 at 13:32
3
$\begingroup$

Remember that the set of definitions writable in a finite alphabet is countable. So any set of languages where a language can be specified with a finite amount of data is countable. For example, a recursive language is specified by the Turing machine which accepts it, so the set of recursive languages is countable.

In order to get uncountable, you are going to have to allow a lot more freedom than that. For example, take any infinite language L and consider the set of all languages which are subsets of L. I'm not sure what kind of example you'd find nice, so I don't know what kind of example to give you.

$\endgroup$
1
$\begingroup$

The set of all languages which accept the empty word. Or all even words. Or all languages encoding all pairs of integers (a,b) such that a

You're not being silly, but if you want an uncountable number of languages, this means that you need to have some parameter ranging over an uncountable set. In the first two examples it was the set of all languages, in the third it was the real line.

$\endgroup$
0
$\begingroup$

The Turing degrees are an uncountable collection of sets of languages (equivalence classes under Turing reduction). So if you choose one representative (canonical in some way) language from each degree, you've got an interesting uncountable set of languages.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.