HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

How many decidable decision problems are there?

Submitted by: @import:stackexchange-cs··
0
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."

Context

StackExchange Computer Science Q#64895, answer score: 15

Revisions (0)

No revisions yet.