Assuming the Church-Turing thesis holds, there are problems that no computing device can solve. We can prove this using a counting argument: there are no surjective function from the set of all Turing Machines to the set of all languages over \left\{0,1\right\}. That is: every mapping from TM to languages fails to cover some language. proof Suppose for contradiction all languages are recognizable, then for all L, there is as truing machine M recognizing L. Meaning, there’s some surjection R: TM \to L. Recall, Turing Machine Encoding exists, so TM \subseteq \left\{0,1\right\}^{* }; call this contained in M. Languages over \left\{0,1\right\} are SETs of strings over zeros and ones—notice, this is the POWER SET of M, so its 2^{M}. Now, no surjection for power sets, so there is no such surjection R. We have contradiction. no surjection for power sets Let L be a set and 2^{L} be its power set. Meaning: no matter what the set L is, the power set 2^{L} always has strictly larger cardinality. one proof Let f: L \to 2^{L}; suppose S = \left\{x \in L \mid x \not \in f(x)\right\} \in 2^{L} (that is, the set S contains the x \in L which isn’t in the range of f(x). For all x \in L: if x \in S, then x \not \in f(x) (by definition); if x \not \in S, then x \in f(x). Therefore, S \neq f(x). In particular this means that f is not surjective because it doesn’t map anything to the set S \in 2^{L}. another proof Russell’s Paradox Similar idea as here: suppose X is the universe of all possible sets. Frege: Let f: X \to \left\{0,1\right\}, then \left\{S \in X \mid f(S) = 1\right\} is a set (this makes sense, f is just the membership predicate of the set). Define: F = \left\{S \in X | S \not \in S\right\} — because being in S is a predicate you can track. Suppose now F \in F, then, by the definition of F, F \not \in F. Contradiction — this logical system is inconsistent. This type of argument is called a Diagonalization Arguments.