3
$\begingroup$

OK, so I was told in CSTheory that I should be asking here. So my question is the following:

I've taken my first course on Language Theory and we saw the "standard" classification of languages. We saw that many problems can be expressed as a membership question of a corresponding language. I'm wondering if there are any problems for which no language can be specified.

  • 2
    What is a problem? What does it mean to specify a language for a problem?2010-12-04
  • 0
    Since a language can only have a countable number of strings, that may lead somewhere. On the other hand, how would you even specify a problem that has uncountably many instances?2010-12-04
  • 0
    @Rahul Narain: Sure. For example we could move to higher type computability and ask about the problem of deciding whether a function from $\omega$ to $\omega$ ever takes the value $0$.2010-12-04

3 Answers 3

8

There are many types of "problems". Not all types of problems correspond to languages, but some do. Here are some relevant examples.

  • A decision problem is the problem of deciding membership in some set. Usually in CS the set is a set of natural numbers or strings. Any such problem can be represented as a language in the most general sense. In the notes you linked, they only consider languages on sets of strings over a finite alphabet; these languages correspond to a certain type of decision problem, which is related to the usual reducibilities such as Turing reducibility and P-time reducibility.

  • A function problem is a problem that asks you to be able to compute a specific function. For example, given an integer, produce an explicit prime factorization. These problems do not directly correspond to languages, but each function problem can be converted into the related decision problem of the graph of the function. When the underlying set is countable, this conversion preserves Turing degree.

  • A mass problem is a more general type of problem that is represented by a subset of $\omega^\omega$. The "problem" is to produce some element of the set. These problems correspond to Medvedev reducibility and Muchnik reducibility. They do not correspond to decision problems for sets of strings on finite alphabets.

  • 0
    thank you. Although I don't have the background for understanding you're answer completely, I do understand that there are problems for which a language can't be defined, which answers my question.2010-12-05
2

What is a language for you?

The canonical definition is that any set $L \subseteq \Sigma^*$ with $\Sigma$ an alphabet (i.e. finite set of symbols) is a language. There are extensions to infinite, but countable $\Sigma$.

If we assume either of those definitions, any problem on real numbers can not be represented as language, since plenty of real numbers do not have finite representations (in countable universes). That means you can not even encode your inputs properly.

In general terms, any problem that is defined on a non-countable is not representable as language (in the above terms).

1

Let $P$ be a property of objects of type $X$, i.e. of $x \in X$. Then $P$ can be expressed as membership in $$\{ x \in X : P(x) \}.$$

  • 0
    But is this set a language?2011-03-15
  • 0
    It is a language of objects of type $X$. If you want to get your definition, take $X = \Sigma^*$. However, it makes sense sometimes to consider, say, language of infinite strings.2011-03-15
  • 0
    I guess those infinite strings would have to be enumerable?2011-03-16
  • 0
    Not necessarily. That depends on your definition. You can use whatever definition you want if it makes sense (defines something). Whether you should use one definition or another depends on what you're trying to model (if it's a primary definition) or what you need in your proof or theory (if it's a secondary definition).2011-03-17
  • 0
    Sure, it is just that I have not encountered the concept of languages that are not at least enumerable. Do you have an example?2011-03-17
  • 0
    The language of all bi-infinite strings over $\{0,1\}$ containing infinitely many runs of both $0$ and $1$ of arbitrary length.2011-03-18