patternModerate
How many decidable decision problems are there?
Viewed 0 times
howaredecisiondecidablemanyproblemsthere
Problem
Is there a "intuitive" way of understanding how many possible decidable problems there are, given some formal language to describe them?
Solution
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."
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."
Context
StackExchange Computer Science Q#64895, answer score: 15
Revisions (0)
No revisions yet.