patternMinor
Languages of cardinality higher than $\aleph_0$
Viewed 0 times
cardinalitylanguagesthanaleph_0higher
Problem
I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or countable. Just wondering if languages of higher cardinality have been investigated. Any references would be nice.
Thank you!
EDIT: I found an answer. Infinitary logic deals with just such a question. See here. It allows formulas of infinite length, so the collection of all such formulas could be uncountable. I guess in the CS world a formula is simply a legally formed word (based on some rules). The set of all such legal formulas could be uncountable.
I'm choosing to leave this question here as it might help another beginner like myself.
EDIT 2: Another way maths allows uncountable languages is to allow uncountably many symbols in the signature (which would be a subset of alphabet in the CS world). So even if formulas (i.e. words) can only be finitely long, there can be uncountably many of them.
I've realized the question isn't so much about formal languages as it is about logic. It was due to my ignorance that I posted the question here. My humble apologies!
Thank you!
EDIT: I found an answer. Infinitary logic deals with just such a question. See here. It allows formulas of infinite length, so the collection of all such formulas could be uncountable. I guess in the CS world a formula is simply a legally formed word (based on some rules). The set of all such legal formulas could be uncountable.
I'm choosing to leave this question here as it might help another beginner like myself.
EDIT 2: Another way maths allows uncountable languages is to allow uncountably many symbols in the signature (which would be a subset of alphabet in the CS world). So even if formulas (i.e. words) can only be finitely long, there can be uncountably many of them.
I've realized the question isn't so much about formal languages as it is about logic. It was due to my ignorance that I posted the question here. My humble apologies!
Solution
In traditional Formal Language theory, all languages are countable. This is because they're defined as a subset of $\Sigma^*$, so they always contain strings of finite length, meaning we can map them to integers.
We rarely deal with finite languages, since all finite languages are regular, and therefore trivially decidable.
There has been research into the computability of functions on real numbers. The difficulty here is that in practice, there's no single way to represent arbitrary real numbers. A common method is looking at, given a real-valued function $f$, inputs $\vec{x} $ and an integer $n$,
can we use a Turing Machine to compute a representation $f(\vec{x})$ to $n$ digits of precision?
You could view a real number as justing being a function taking $0$ arguments, so a real number $r$ is can be seen as a function from $n$ to the first $n$ binary digits of $r$.
Interestingly, since Turing Machines are finite, the set of all Turing Machines is countable, so the set of all computable real numbers is countable, meaning there are many more uncomputable reals than computable ones.
For more info, see http://en.wikipedia.org/wiki/Computable_number.
Note that there's also a concept of automata on infinite words, used in formal language theory and program verification. These languages can be uncountable: an infinite sequence of $0$s and $1$s is equivalent to a subset of $\mathbb{N}$ so an automaton that accepts all such words accepts an uncountable language.
We rarely deal with finite languages, since all finite languages are regular, and therefore trivially decidable.
There has been research into the computability of functions on real numbers. The difficulty here is that in practice, there's no single way to represent arbitrary real numbers. A common method is looking at, given a real-valued function $f$, inputs $\vec{x} $ and an integer $n$,
can we use a Turing Machine to compute a representation $f(\vec{x})$ to $n$ digits of precision?
You could view a real number as justing being a function taking $0$ arguments, so a real number $r$ is can be seen as a function from $n$ to the first $n$ binary digits of $r$.
Interestingly, since Turing Machines are finite, the set of all Turing Machines is countable, so the set of all computable real numbers is countable, meaning there are many more uncomputable reals than computable ones.
For more info, see http://en.wikipedia.org/wiki/Computable_number.
Note that there's also a concept of automata on infinite words, used in formal language theory and program verification. These languages can be uncountable: an infinite sequence of $0$s and $1$s is equivalent to a subset of $\mathbb{N}$ so an automaton that accepts all such words accepts an uncountable language.
Context
StackExchange Computer Science Q#35518, answer score: 6
Revisions (0)
No revisions yet.