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.



A subset of all languages which is uncountable?
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.


