6
$\begingroup$

Is there a "intuitive" way of understanding how many possible decidable problems there are, given some formal language to describe them?

$\endgroup$
12
$\begingroup$

There are a countable infinity of decidable problems. There must be at least a countable infinity, because all of the languages $\{a\}$, $\{aa\}$, $\{aaa\}$, ... are decidable. There cannot be more than a countable infinity, because there are only that many Turing machines (each Turing machine can be encoded as a finite string).

There can be no formal language that describes them all without also describing some undecidable problems. This is because the set of decidable languages is not recursively enumerable, but any formal language would give a way to enumerate them. At least, assuming it was decidable whether a string was in the formal language or not. And, if you can't even decide whether a string was in your formal language, it wouldn't be any better as a description than, "The set of all languages decided by Turing machines."

$\endgroup$
  • $\begingroup$ I don't understand this sentence: "This is because the set of decidable languages is not recursively enumerable, but any formal language would give a way to enumerate them." $\endgroup$ – xavierm02 Oct 20 '16 at 21:26
  • 2
    $\begingroup$ @xavierm02 I believe the reasoning is: "If a formal language were to exist, this would mean that the set is recursively enumerable. However, the set is not recursively enumerable. Therefore, a formal language does not exist." $\endgroup$ – Tanner Swett Oct 20 '16 at 22:08
  • $\begingroup$ "At least, assuming it was decidable whether a string was in the formal language or not." -- semi-decidability would be enough, wouldn't it? $\endgroup$ – Raphael Oct 20 '16 at 22:26
  • $\begingroup$ "There cannot be more than a countable infinity, because there are only that many Turing machines (each Turing machine can be encoded as a finite string)." <-- I'm not sure that follows. Surely two problems can share the same solution, i.e. be solved by the same Turing machine. In that case there could in principle be more decision problems than there are Turing machines. I think it would be better to say that whatever a "problem" is, it must be something that can be specified in a finite amount of text, and that there can only be a countable number for that reason. $\endgroup$ – Nathaniel Oct 21 '16 at 6:05
  • 2
    $\begingroup$ @Nathaniel A problem is a language, which is a set of strings. You can't have two languages decided by the same Turing machine. $\endgroup$ – David Richerby Oct 21 '16 at 8:14
0
$\begingroup$

Expanding a little bit the trivial case in which the "given language" is Turing complete: as said by David in his answer, if the "given formal language" can be represented with a string, then there are countably many programs (problems) ... the interesting questions is whether they are (all) decidable or not.

For example if you pick Presburger Arithmetic i.e. first order statements on natural numbers with addition and equality; then all "problems" (first order sentences) are decidable. For example

$\forall y .(y \neq 0) \to (\exists x . y = x + 1)$

"Intuitively" you can say that there countably many first order sentences ... but "intuitively" you cannot say "how many" (all?) of them are decidable (indeed the proof of decidability of Presburger arithmetic is quite complicated).

If the given formal language is a standard programming language in which you can only define a single variable (which can contain an arbitrarily large integer) then again all problems are decidable. But as soon as you allow 2 variables then you get a Turing complete language.

In summary: proving the decidability of a given formal language is not always a trivial task; if there are clear evidences that it is Turing complete then you "get owned" by the halting problem (or - equivalently - by the first Godel's incompleteness theorem) otherwise you can be near the border between decidability and undecidability and proving on which side you are can be very hard :-)

$\endgroup$
0
$\begingroup$

A language is a decision problem. $L \subseteq \{0,1\}^*$, a generic language, is a subset of $\Sigma^*$ (where $\Sigma$ is the alphabet).

Decidable languages are by definition countable, as every Turing Machine has a finite description.

We can prove that there is no bijective mapping between the set of all turing machines to the set of all subsets of $\Sigma^*$ (ie the set of all languages), and further, that because the set of all languages (ie the set of all subsets of $\Sigma^*$) is uncountably infinite, there are vastly more undecidable problems than there are decidable problems.

This is a direct corollary of Cantor's Theorem

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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