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.
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.
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.
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.
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.
