Click here to return to the main page
DOI: 10.6084/m9.figshare.25434994
This paper presents my Post-Kantian interpretation of Gödel's incompleteness theorem, and related ones on unsolvability by Church and Turing. All of them are seen from a linguistic point of view.
At first, the intended title was “Gödel, Post, and Turing”, abbreviated GPT as the popular IA model.
However, in the end, the main result was that every Turing complete language is Gödel incomplete, so the definitive title introduced itself to me.
Cantor's diagonal argument makes clear that the concept set is equivalent to the concept predicate: Each predicate expresses a set by determining what is in and what is out of it. As we see in the paper, Gödel incompleteness theorem shows the limitations of this fundamental concept, which had been already questioned by Russell's paradox.
In order to better compare Cantor (1891) with Gödel (1930), I have adapted the notation of Cantor's diagonal argument to conform to Gödel's incompleteness notation, except when I did not follow Gödel, which was only once: I prefer $R_p(n)$ to his $[R(p);n]$, where $R_p$ is the $p$-th formalized predicate, and then $R_p(n)$ denotes the formula which arises from $R_p$ by substitution of $n$ for the free variable of the predicate.
When using the same notation, it seems that a contradiction arises: Cantor showed that the predicates are not enumerable, while Gödel say they are. However, they are not talking exactly about the same thing: Gödel does not refer to an unqualified predicate, but to a „Klassenzeichen“, which Davis (1965) translates as a “class-expression”, that is, to a formalized predicate. Formalized predicates are predicates, and formalized predicates can be enumerated; this resolves the conundrum! Note that formalized predicates are those that can be expressed in the formal system, which is an ad hoc and very peculiar language.
Gödel had to invent a Turing complete language in order to prove his incompleteness theorem. It was an ad hoc and very peculiar language, and Turing clarified many details, as Gödel himself acknowledged, as related by Davis (1982), pages 12–13.
Nevertheless, Gödel was not convinced by the available evidence, and remained unwilling to endorse the equivalence of effective calculability, either with recursiveness or with λ-definablity. He insisted (as Church later reported to Kleene) that it was “thoroughly unsatisfactory” to define the effectively calculable functions to be some particular class without first showing that “the generally accepted properties” of the notion of effective calculability necessarily lead to this class. As we shall see, it was not until Turing's work became known that Gödel was willing to concede that this difficulty had been overcome.
As the previous citation says, Turing computing generalizes both Gödel recursiveness and Church λ-definablity. That is the reason why it is better (more general and simpler) to formulate Gödel incompleteness theorem and Church's thesis in Turing computing terms. So I do it thus in the paper.
This linguistic generalization of Gödel's incompleteness theorem is still a mathematical theorem. That is, it is not open to interpretation. In a way, as every mathematical theorem, it is a tautology, and as such, in principle, of no practical importance.
Its importance depends on Church's thesis, but there is not any agreement on the epistemological status of this thesis. For Church himself, his thesis was a definition. Gödel preferred it to be an axiom in a formal system capturing the meaning of computation. But we side with Post, see next section.
Church's reaction to Post was bipolar.
We position ourselves with Post, see §8: Church's thesis is a law of nature. More precisely, Church's thesis is a consequence of the law of Post.
Post and Kant fit nicely into a Post-Kantian subjectivism.
The underlined text will be added, in §4¶5, to the next version of the paper, v6:
So the equation of Turing completeness, where the $|$ represents an end of program symbol or, in general, a composing operation, is:
$$\exists\,{\cal U},\forall{\cal P},\forall{\frak d}:\; \overleftarrow{{\cal U}\langle\,{\frak p}|\vec{\frak d}\,\rangle} = {\cal P}\langle{\frak d}\rangle \;.$$
The composing operation can be Merge, cons, or another one.
In §4¶6 it is written:
Note that, to satisfy the equation, the syntax of $\cal L$ has to be decidable.
This is because, while in the right hand side (rhs) of the equation of Turing completeness, $\frak d$ is any string of symbols of $\cal P$, in the left hand side (lhs), what is on the tape is not any string of symbols of $\cal U$, but a well-formed formula (wff), or sentence, of the language $\cal L$ implemented by the universal Turing machine $\cal U$. Therefore, the equation of Turing completeness requires that it is always possible to decide both whether a string of $\cal L$ is a program $\frak p$ or not, and whether a string of $\cal L$ is properly coded data $\vec{\frak d}$ or not.
Note that, in any sentence of any Turing complete language $\cal L$, there is a program $\frak p$, which works as a verb, and its argument, or coded data $\vec{\frak d}$, which works as anything else, i.e. either subject, or object, or whatever, and even more than one, or none.
In §6¶6 it is written:
Then, in the complete language $\cal L$ of the universal Turing machine $\cal U$, a program $\frak h$ that solves the halting problem is inexpressible.
Turing computing is more general than Gödel's formal system,
and therefore it is not limited to produce TRUE statements,
also known as theorems. However,
a program that always halts and that outputs only two possible values,
one for TRUE and the other one for FALSE,
implements a predicate.
Then program $\frak h$ is defined to be a predicate, since it would always decide whether a computation would halt or not. So program $\frak h$ is a definable predicate, which is not expressible in any Turing complete language. In other words, $\frak h$ defines the set of the halting computations of the Turing complete language $\cal L$; let us call it set $H$.
Since in every Turing complete language there is an inexpressible program $\frak h$, we can formulate Gödel's incompleteness theorem generalized to Turing computing this way:
Being Gödel incomplete means that there are concepts that can be defined but not expressed, for example ‘arithmetic truth’. In other words, the set of all true arithmetic propositions, which is Gödel set T, is undecidable because it is not possible to write a computable predicate that expresses what is in and what is out of it, implying that we cannot always decide whether an aritmetic proposition belongs to the set or not. Other undecidable sets are the set of all sets that are not members of themselves, which is Russell set S, and the set of the halting computations of a Turing complete language, which is Turing set H.
All undecidable sets, with their associated concepts, are paradoxical or illusory, because they can be defined, named, and referred to, but they cannot be expressed in a Turing complete language. And, because any arithmetic truth is a truth, if there are undecidable arithmetic truths, then there are undecidable truths. Therefore, as a consequence of Gödel's incompleteness theorem, truth is an undecidable concept. In addition, outside computing, a partial function is not a function, and only total functions are considered functions. Therefore, the halting theorem shows, in computing, that ‘total function’ is an undecidable concept, and, in general, that function is an undecidable concept. In summary, set, truth, and function are three undecidable concepts.
Therefore, the diagonal argument is used to show some limitations of human language, and of other finitary systems, which derive from it. In these systems, the means are finite, but we do not limit their use. This is, of course, an idealization, but nevertheless it would also be wrong to limit, for example, the number of words in a sentence, or the number of steps in a proof. Summarizing, the incompleteness and unsolvability theorems by Gödel, Church, and Turing find limitations in our finitary tool, which is our complete language.
And, in any complete language, there are definable concepts that cannot be expressed, see §10.2.
This generalizes Gödel’s incompleteness theorem, see §6¶8, which represents, under the
law of Post, an absolute human limitation, see §7 and §8, which Kant promotes to
transcendental, see §9. So, epistemologically, Gödel’s incompleteness theorem elevates
from Turing’s generalization,
Following Post program, we will propose a linguistic and empirical interpretation of Gödel's incompleteness theorem and related ones on unsolvability by Church and Turing. All these theorems use the diagonal argument by Cantor in order to find limitations in finitary systems, as human language, which can make “infinite use of finite means”. The linguistic version of the incompleteness theorem says that every Turing complete language is Gödel incomplete. We conclude that the incompleteness and unsolvability theorems find limitations in our finitary tool, which is our complete language.
Link to the page of my paper on “Gödel Incompleteness and Turing Completeness” in figshare, and direct link to the pdf file.
These are the external references used in this page:
Versions:
Última actualización: 2024-12-31.
© Ramón Casares 2024