[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/there_are_non_recognizable_languages.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "there are non-recognizable languages" type: concept related: [Surjectivity, Church Turing Thesis] source: https://www.jemoka.com/posts/kbhthere_are_non_recognizable_languages/ confidence: high status: active --- 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 \(\qty {0,1}\). 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 \qty {0,1}^{* }\); call this contained in \(M\). Languages over \(\qty {0,1}\) 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 = \qty {x \in L \mid x \not \in f(x)} \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 \qty {0,1}\), then \(\qty {S \in X \mid f(S) = 1}\) is a set (this makes sense, \(f\) is just the membership predicate of the set). Define: \(F = \qty {S \in X | S \not \in S}\) — 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.