Click here to return to the main page
DOI: 10.6084/m9.figshare.25434994
I wanted to investigate the precise scope of Gödel's incompleteness theorem, and its interpretation from my Post-Kantian 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 defines 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 Rp(n) to his [R(p);n], where Rp is the p-th formalized predicate, and then Rp(n) denotes the formula which arises from Rp 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. These two resolve 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 complete language 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.
Church's reaction to Post was bipolar.
We position ourselves with Post: 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.
Universal computing requires a complete language, which is one in which every computation can be meaningfully expressed. However, as shown by Gödel incompleteness theorem generalized to Turing computing, every complete language is Gödel incomplete. As a consequence, there are some sets that seem to be right but are illusions, as for example the set of all sets that are not members of themselves, which is Russell set, or the set of all true arithmetic propositions, which is Gödel set, or the set of all halting computations of a complete language, which is Turing set, and so on. These illusory sets are non-recursive (= non-computable), because it is not possible to recursively (= computably) enumerate both the set and its complement, so it is not possible to decide what is in and what is out of the set.
Therefore, the diagonal argument is used to show some limitations of human language, see §10.2, 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.
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 his page:
Versions:
Última actualización: 2024-04-27.
© Ramón Casares 2024