patternMinor
Small doubt concerning cardinality of set of problems and algorithms?
Viewed 0 times
concerningcardinalitydoubtalgorithmssmallandproblemsset
Problem
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, he
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, he
Solution
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.
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.
Context
StackExchange Computer Science Q#163441, answer score: 8
Revisions (0)
No revisions yet.