5
$\begingroup$

I write this question because my professor in Algorithm Analysis briefly mentioned some property related to the countability/uncountability of the set of strings/problems/algorithms and the consequent inability to have an "algorithm that can solve it all" which I didn't fully understand...

As I understand: A decision problem $X$ is conceived of as a set of finite binary strings $s$, which are in turn conceived of as "instances" of said problem. We say $s$ is a positive instance of $X$ iff $s \in X$. As $s$ is a finite binary string, it is simply a function $f : n \to \{0, 1\}$ for some ordinal $n < \omega$. Hence, if $S_k = \{0, 1\}^k$ (i.e., the set of all functions from $k$ to $\{0, 1\}$), then $S = \bigcup_{k \in \mathbb{N}}S_k$.

It is simple to show that $S$, the set of all finite binary strings, is countably infinite: Consider $f : \mathbb{N} \longrightarrow S$ such that $f(2^k + i) = i$th element of $S_k$ and you've got yourself a nice bijection (with $k \in \mathbb{N}$ and $i = 0, \dots, 2^{k+1}-1$ —one can show that every natural $n$ can be written thus). Hence, $|S| = \aleph_0$ (i.e., it is countably infinite).

As a decision problem $X$ is a set of strings $s \in S$, it is evident that $|P| = \mathcal{P}(\mathbb{N}) = 2^{\aleph_0}$, where $P$ is the set of all decision problems (i.e., it is uncountably infinite).

Now here come my doubts: An algorithm $A$ for a decision problem $X$ was briefly disclosed as such that it recieves an input of $s$ a string and outputs $1$ iff $s \in X$. As such, $A$ would have to be conceived of as a function $f : S \longrightarrow \{0, 1\}$ and there would thus be $2^{|S|} = 2^{\aleph_0}$ many algorithms.

However, as I understand it, an algorithm is not just any arbitrary function. It must be representable via a Turing machine, which conforms to a finite tuple of finite sets (here constants and functions being taken as sets also to make matters simpler). Clearly, there are only countably infinitely many Turing machines, hence there must also be only countably infinitely many algorithms? (Additionally, I have a bit of trouble understanding the notion of encoding a whole algorithm as a single binary string —is it just an encoding of the finite-tuple-of-finite-sets Turing machine into a single binary string/number?)

Now this is where I sort of lost my professor. Yes, if the set $\mathcal{A}$ of algorithms is countably infinite, and the set $P$ of decision problems is uncountably infinite, then there is no bijection between the two, but what does this mean exactly? That there does not exist an algorithm $A \in \mathcal{A}$ for every decision problem $X \in P$ which can verify its positive instances correctly? That is, given a decision problem $X$, there may not necessarily be an algorithm $A$ which can solve it (i.e., output $1$ iff its input is an actual positive instance of $X$)?

Any help would be much appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ Yes, most problems can not be decided for the cardinality reason you mention: there are uncountably many problems but only countably many programs. Similarly, most functions $\mathbb N \to \mathbb N$ can not be computed by any program. Computability (also called recursion theory) is the discipline that studies the (un)decidability of problems. $\endgroup$
    – chi
    Dec 12, 2023 at 23:41

3 Answers 3

8
$\begingroup$

The intuitive reasoning is "there are more problems than algorithms, so it cannot be the case that, for each problem, there exists an algorithm that solves it". More formally, this can be expressed as follows:

The fact that the two sets have different cardinality implies that there is no surjective map $f$ from the smaller set $A$ to the larger set $B$; In fact, let $f$ be surjective: $$\forall y \in B . \exists x \in A . x \mapsto y $$ Since $B$ is larger than $A$, by pigeonhole principle we have that for some $x \in A$: $$ \exists y_1, y_2 \in B . (x \mapsto y_1) \wedge (x \mapsto y_2) $$ Which implies that $f$ is not, in fact, a function.

So any function from $A$ to $B$ cannot be surjective. If $A$ is the set of algorithms, and $B$ is the set of problems, this means that, if we tried to map every algorithm to the decision problem it solves, there would always be at least a problem that is not the image of any algorithm, i.e. that cannot be solved by any algorithm.

$\endgroup$
7
  • 2
    $\begingroup$ Actually there are infinitely much more unsolvable problem than solvable ones since the image of the countable set of algorithms is a countable subset of the set of problems. In a certain sense, the quantity of solvable problems is negligible lol $\endgroup$
    – SilvioM
    Dec 12, 2023 at 10:38
  • 1
    $\begingroup$ @SilvioM True :) $\endgroup$ Dec 12, 2023 at 12:38
  • 4
    $\begingroup$ @SilvioM On the one hand, I find that insight deeply disturbing, but on the other hand, I guess it means we can be thankful for any algorithm that does solve a problem, and shouldn't take it for granted that one exists. $\endgroup$
    – kutschkem
    Dec 13, 2023 at 8:05
  • 1
    $\begingroup$ @kutschkem I don't lose sleep over the fact that "most" numbers can't be written out explicitly, and I see no difference with decidability. The "majority" of undecidable problems are equally alien as those unrepresentable numbers. $\endgroup$
    – Passer By
    Dec 14, 2023 at 4:58
  • $\begingroup$ 'intuitive reasoning is "there are more problems than algorithms"' Note however that if your intuition about "a problem" is that it needs to be definable with a finite LaTeX code (or in some more formal language), there are only countably finite "problems", and this cardinality argument doesn't give anything. The existence of decision problems that can't be defined is very nonintuitive (well, as nonintuitive as indefinable real numbers) $\endgroup$
    – JiK
    Dec 14, 2023 at 11:16
6
$\begingroup$

Correct. There are only countably many algorithms (only countably many Turing machines). Yes, this proves that there exists at least one decision problem that cannot be decided by any algorithm (in fact, that there are infinitely many of them).

Some decision problems have an algorithm that "solve" them; some do not.

$\endgroup$
3
$\begingroup$

Additionally, I have a bit of trouble understanding the notion of encoding a whole algorithm as a single binary string —is it just an encoding of the finite-tuple-of-finite-sets Turing machine into a single binary string/number?

Yes.

First of all, the word "binary" in that sentence is irrelevant. If you can encode the elements of a set as strings, then you can encode the elements of this set as binary strings. Indeed, if you have two alphabets A and B, assuming A and B each have a number of symbols which is finite and greater than or equal to 2, then it's trivial to write a conversion function that converts A strings into B strings. In fact, right now I am typing this post, which is a string in the alphabet {'A', 'B', ..., 'Z', 'a', 'b', ..., 'z', ' ', '.', ',', etc.}, and this post is going to be stored on a computer, even though it is well-known that computers just use 0 and 1 internally. So this post is going to be turned into a binary string! A combination of 0 and 1 represent A, another combination represent B, etc. It's easy to convert from the big alphabet {'A', 'B', ...} to the small alphabet {0, 1}.

Second, now that we don't need to care about binary and can use any alphabet we want, representing a Turing machine as a string can be done in many ways. We're just looking for textual encryption of Turing machines; or using another word, textual descriptions of Turing machines. You just have to find a language that can uniquely describe every Turing machine. Which comes down to listing the states, and listing the transitions, for instance by writing a list of "(state, symbol) -> (new state)".

In fact, many programming languages have been proven to be Turing-complete, so the argument can be done using any programming language of your liking instead of Turing machines. Choose your favourite programming language. A program in this language is just a finite string of symbols, so the number of possible programs is countable. (Not all finite strings of symbols are valid programs, but the set of valid programs is a subset of the set of all finite strings of symbols, and a subset of a countable set is also at-most-countable).

For instance, brainfuck is Turing-complete. A valid program in brainfuck is a finite string of +-><.,[] characters such that the [] are balanced. So the number of possible brainfuck programs is countable, which means that only a countable number of problems can be decided by brainfuck programs.

$\endgroup$
2
  • 1
    $\begingroup$ Re: "Indeed, if you have two alphabets A and B, assuming A and B each have a number of symbols which is finite and greater than or equal to 2, then it's trivial to write a conversion function that converts A strings into B strings": Indeed. It's also straightforward if one or both have only one symbol. (The least-trivial case is that A has multiple symbols and B has only one, but even that case is straightforward -- just sort all languages in A* by length and then lexicographic order, and map the nth language in A* to the length-n language in B*.) $\endgroup$
    – ruakh
    Dec 14, 2023 at 0:11
  • $\begingroup$ @ruakh I purposefully restricted to finite and at least 2. Otherwise, yes, conversions might be possible, including in the case of infinite (countable) alphabets, but I wouldn't call those conversions "trivial". $\endgroup$
    – Stef
    Dec 14, 2023 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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