Gödel Incompleteness and Turing Completeness

www.ramoncasares.com 20241111 GPT 1 G¨odel Incompleteness and Turing Completeness Ram´on Casares orcid: 0000-0003-4973-3128 Following Post program, we will propose a linguistic and empirical interpretation of G¨odel’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¨odel incomplete. We conclude that the incompleteness and unsolvability theorems find limitations in our finitary tool, which is our complete language. Keywords: G¨odel incompleteness, Turing completeness, law of Post, Cantor’s diagonal argument, liar paradox §1 Introduction ¶1·Following Post (1936) program, we will argue in favor of a linguistic and empirical interpretation of G¨odel’s (1930) incompleteness theorem and related ones on unsolvability by Church (1935) and Turing (1936). All these theorems use the diagonal argument by Cantor (1891) in order to find limitations in finitary systems, as human language, which can make “infinite use of finite means”. ¶2·In section §2, we explain Cantor’s diagonal argument. Next, in §3, we sketch G¨odel’s incompleteness theorem, which uses the diagonal argument on an ad hoc language. Then, in §4and §5, we present Turing computing: Turing completeness and complete languages. In §6, we show that the halting problem generalizes G¨odel’s theorem and, using the diagonal argument on a Turing complete language, that it is unsolvable by computing. The linguistic version of the incompleteness theorem says that every Turing complete language is G¨odel incomplete. Then, following Post program, in §7and §8, we posit as a refutable law of nature that human language is just Turing complete, by which the incompleteness and unsolvability theorems become human limitations. Next, in §9, we defend, in Kant’s terminology, that language is a condition of all possible theory, and, in §10, that language can “make infinite use of finite means”, in Humboldt’s words. Finally, in §11, after noticing that the diagonal argument finds limitations in finitary systems, we conclude that the incompleteness and unsolvability theorems find limitations in our finitary tool, which is our Turing complete language. This is doi: 10.6084/m9.figshare.25434994.v5, version 20241111. c 2024 Ram´on Casares; licensed as cc-by. Any comments on it to [email protected] are welcome. www.ramoncasares.com 20241111 GPT 2 §2 Cantor: Diagonal ¶1·Let us start from the beginning. In a four pages paper, Cantor (1891) presented a new and simpler proof showing that the cardinality of the real numbers |R|is greater than the cardinality of the natural numbers |N|, that is, |R|>|N|. The theorem says that the powerset (the set of all the subsets) of the natural numbers cannot be enumerated. ¶2·proof ·First, we should see that every subset Ris defined by a predicate on the natural numbers R(n) that is true if the natural number nbelongs to the subset, and false if it does not. Fully expressed, ∀n∈N{R(n) = true if n∈R, R(n) = false if n /∈R. Or, in fewer words, n∈R≡R(n). ¶3·For the sake of the argument, let us assume that all the predicates defining the subsets of the natural numbers can be enumerated. In that case, Rpwould denote the predicate number p, and we could compose the following matrix of true and false values. R0(0) R0(1) R0(2) . . . R0(n). . . R1(0) R1(1) R1(2) . . . R1(n). . . . . .. . .. . ..... . .... Rp(0) Rp(1) Rp(2) . . . Rp(n). . . . . .. . .. . ..... . .... ¶4·Now, let us define a subset Kthis way, where the bar above denotes negation: n∈K≡Rn(n). It is easy to see that K=R0, because, if 0 ∈R0then R0(0) = true, so R0(0) = false, and then 0 /∈K, and conversely, if 0 /∈R0then 0 ∈K. Similarly for 1, and then K=R1, and for 2, so K=R2, and so on for every natural number. Therefore, ∀p∈N:K=Rp, showing that the assumption was wrong. qed ¶5·The proof shows that the powerset of the natural numbers cannot be enumerated, in Cantor’s notation ℵ0<2ℵ0. This is enough for us here, but Cantor was interested in showing that |N|<|R|, which follows immediately from |N|=ℵ0and |R|= 2ℵ0. The proof is named Cantor’s diagonal argument because the elements chosen to be negated are those in the matrix diagonal, Rn(n), which are the most easily denoted, though the proof works just by choosing systematically a different column for each row. Below, in §6¶1, we will learn from G¨odel that choosing to negate the diagonal instantiates the liar paradox; other selections will implement other epistemological antinomies. God made the counting numbers; all else is the work of man Leopold Kronecker www.ramoncasares.com 20241111 GPT 3 §3 G¨odel: Incompleteness ¶1·sketch of proof ·In order to explain the incompleteness theorem by G¨odel (1930), where it is Theorem VI but sometimes referred to as the first one, we will start with the following lemma: in every language that is expressive enough to mean ‘this sentence is false’ there is a paradox. It is easy to see that the lemma is true because the sentence ‘this sentence is false’ is a paradox; in fact it is the canonical liar paradox. Therefore, the hard part of the incompleteness theorem is to prove that the language required to express arithmetic has to be expressive enough to mean ‘this sentence is false’. Let us try it! ¶2·The language required to express arithmetic has to be able to express that ‘the successor of zero is one’, which happens to be considered true, that ‘one plus one is one’, considered false, that ‘thirteen is prime’ and also that ‘thirteen is not prime’, and an infinity of other propositions. I have written ‘an infinity of other propositions’, perhaps too lightly, but am I right? The answer is ‘yes’, because there is an infinite enumerable number of true propositions as ‘the successor of zero is one’, each one referring to a different natural number, as ‘the successor of one is two’, ‘the successor of two is three’, and so on and on. This means that the language required to express arithmetic has to be infinite enumerable, at least. ¶3·Although the infinite enumerable sets are the infinite sets with the lowest cardinal number, ℵ0, it is still true that all of them contain proper subsets that are equicardinal with the whole set. This property is required for full naming, also known as full referring, that is, to be able to assign a different name to every linguistic object. For example, G¨odel (1930) was able to assign a unique natural number, its G¨odel number which worked as its name, to every finite sequence of arithmetic symbols, including the natural numerals themselves! Of course, self referring, included in full referring, is used in paradoxes as ‘this sentence is false’. ¶4·Above, we were using English statements to express arithmetic propositions, but G¨odel, instead of using German, designed a more precise language. All the concepts used in the proof are implemented in the formal system. We follow G¨odel’s (1930) sketch of the proof in page 175, as translated by Davis (1965) in pages 7 and 8. G¨odel’s subset K of natural numbers is defined n∈K≡Bew[Rn(n)] ,(1) where Bew[x] means ‘xis a provable formula’, and where Rn(n) is Cantor’s diagonal formalized (this last word is decisive!). Since Kis a formalized subset of N, then its predicate has to be some definite enumerated predicate Rq, so Kcan also be defined n∈K≡Rq(n).(2) We now show that the proposition Rq(q) is undecidable in the formal system. If we assume that Rq(q) is provable, then it would be true, and then, following the second definition, q∈K, which, following the first definition, means that Bew[Rq(q)], contradicting the assumption. On the other hand, if the negation of Rq(q) were provable, then q /∈K would hold following the second definition, and then Bew[Rq(q)] would be true following the first one, but now both Rq(q) together with its negation would be provable, which is again impossible. Rq(q)≡q∈K≡Bew[Rq(q)] www.ramoncasares.com 20241111 GPT 4 ¶5·So G¨odel is setting out of sight the following Cantor’s matrix of provabilities for every formalized predicate, which is true if Rp(n) is provable, so Rp(n) is true, and false if Rp(n) is not provable. Bew[R0(0)] Bew[R0(1)] Bew[R0(2)] . . . Bew[R0(n)] . . . Bew[R1(0)] Bew[R1(1)] Bew[R1(2)] . . . Bew[R1(n)] . . . . . .. . .. . ..... . .... Bew[Rp(0)] Bew[Rp(1)] Bew[Rp(2)] . . . Bew[Rp(n)] . . . . . .. . .. . ..... . .... The negated diagonal of this matrix is Bew[Rn(n)], on which he defines subset Kwith its corresponding predicate Rqand undecidable proposition Rq(q), which G¨odel writes [R(q); q], which expresses the liar paradox in the formal system, see §6¶1.qed ¶6·As you can see, G¨odel (1930) is not as simple as Cantor (1891) and, given Cantor’s proof, some doubts regarding whether Rqis effectively in the enumeration or not could remain that the full proof conceals behind its many details. G¨odel’s proof is not as simple because it implements a comprehensive and logical language specifically designed to express arithmetic. However, we will not go further into its technicalities here, because Turing (1936) turned things much easier, and then much easier to understand, I hope. §4 Turing: Completeness ¶1·Instead of using symbols specifically designed to refer to arithmetic concepts, as done by G¨odel (1930),Turing (1936) uses a non-empty and finite set of arbitrary symbols. Thus, Turing’s way is more general than G¨odel’s one and, even more important, less prone to induce us to go from the symbol to its intended meaning. All Turing requires is one or more symbols that can be strung, that is, that can be composed into unidimensional and finite structures, or sequences, which are known as strings. ¶2·And again, where G¨odel implements the rules of inference specific of arithmetic and logic to transform arithmetic formulas, Turing uses generic finite-state machines, also known as finite automata, to transform the generic strings of symbols. Note that finitestate machines were not formally studied until much later than Turing’s 1936 paper, in the nineteen-fifties by Mealy (1955),Moore (1956), and others. ¶3·How Turing machines work is not hard to understand, and you can find many other places where it is explained, for example in Casares (T). For us here, it is enough to know that a Turing machine takes a finite string of symbols written on its tape as input and, commanded by the finite-state machine, it halts after a finite number of computing steps with another finite string written on its tape, which is its output, or it keeps computing without halting. We will use P⟨d⟩to denote the output string of Turing machine Pwhen string dwas used as input; if the machine does not halt, we will write P⟨d⟩=∞. ¶4·Now, the deepest and more difficult to understand concept is Turing completeness, that is, that some Turing machines can compute whatever any Turing machine can compute. Those Turing machines that can emulate any Turing machine are called universal Turing machines.Turing (1936) himself constructs a universal machine, but I would very much recommend an instructive text book, as Abelson & Sussman (1985), to get the full details of this counterintuitive concept. www.ramoncasares.com 20241111 GPT 5 ¶5·In order to imitate any possible Turing machine P, a universal Turing machine U needs a complete description of the Turing machine to imitate as input, that is, as part of what is written on the tape when it starts. We will call this complete description the program, and pwill denote the program for P. So the equation of Turing completeness, where the |represents an end of program symbol, is: ∃ U,∀P,∀d:←−−−− U⟨ p| d⟩=P⟨d⟩. We say that Uis a full-programmable computer because it can compute whatever any computer Pcan compute. Let us now examine the equation closely. ¶6·Today, the existence of universal computers, ∃ U, is a common experience, since all general-purpose computers, including our phones, are Turing complete, or universal, or full-programmable; these last three phrases are synonymous. For the equation to be true, the next task is to show that for any Turing machine, ∀P, we can find a string of symbols p(symbols of U) that describes the Turing machine Pcompletely. This is not too difficult; just linearize the table defining P’s finite-state machine, and code the states and symbols of Pby using strings composed of symbols of U;p= Pwill denote this. For example, Turing (1936) in his universal machine uses a semicolon (;) as end of row symbol to linearize the table, and codes Pstate number ias one symbol Dfollowed by isymbols A, and Psymbol number jas one symbol Dfollowed by jsymbols C. Other encodings are possible, where an encoding sets a reversible mapping from the states and symbols of P to some strings of symbols of U. This determines the syntax of the language Lused by each specific Uto code any possible Turing machine Pas its corresponding program, the string p= P, and also to code any string dof symbols of P, denoted  d; a left pointing arrow on top denotes the corresponding decoding, ←−  d=d. The remaining task is the difficult one: to implement the semantics of Turing machines in the hardware of U, that is, in its finite-state machine, in such a way that the equation of Turing completeness will be satisfied, ever (including ∞). Note that, to satisfy the equation, the syntax of Lhas to be decidable. Once achieved, the resulting language Lis a Turing complete language, or a complete language for short. Therefore, in a complete language, every Turing machine can be meaningfully expressed . §5 Turing: Translation ¶1·As the syntax can be defined in different ways, the program p′for Turing machine P in one universal Turing machine U′will differ from the program p′′ for the same Turing machine Pin another universal Turing machine U′′ that uses a different syntax, that is, p′=p′′ though ←−−−−− U′⟨p′| d′⟩ ′ =P⟨d⟩=←−−−−−− U′′⟨p′′| d′′⟩ ′′ . We will call this last double equation the translation equation because it explains how to translate complete languages, in this case from (or to) the complete language L′ implemented by U′to (or from) the complete language L′′ implemented by U′′, since though their syntaxes differ, p′=p′′, their meanings are the same, P. The equations of Turing completeness and translation imply that all universal Turing machines are equal in calculating capability, since they differ only on the encodings used. www.ramoncasares.com 20241111 GPT 6 ¶2·At this point, we can abstract encodings, that is, codings and decodings, away, since coding (or decoding) is a trivial transformation that uses a finite mapping, and it is easy to determine from context whether coding (or decoding) is needed or not. Then, we define the algorithmic equivalence relation thus: two programs p′and p′′ are algorithmically equivalent, denoted p′∼p′′, iff their meanings are the same; for instance when they are translations of the same Turing machine Pto two complete languages, L′and L′′: p′∼p′′ ≡(∃P,∀d:←−−−−− U′⟨p′| d′⟩ ′ =P⟨d⟩=←−−−−−− U′′⟨p′′| d′′⟩ ′′ ). ¶3·The corresponding equivalence classes are called algorithms, so algorithm πis the equivalence class of program p, that is, π= [p] : x∈[p]≡x∼p. We are using uppercase calligraphic letters to denote Turing machines, as Pand U, German lowercase letters for strings on the tapes of Turing machines, as pand d, or  dif coded, but typewriter characters for individual symbols, as Aand w, and we will use Greek lowercase letters for algorithms and information, as πand δ, where information is data after abstracting away its encoding. And, after abstracting encodings away, the equation of Turing completeness is cleaner; the capital upsilon Υ represents the abstract universal Turing machine: Υ⟨π|δ⟩∼ =P⟨d⟩. ¶4·While G¨odel (1930) mimics semantics into syntax from the beginning, making the distinction between both more difficult to grasp, in Turing’s (1936) approach meanings appear only when completeness appears. That is, everything is syntax, except when implementing a language to fully express computing, because by then implementing the semantics of computing is required. However, after abstracting encodings away, it is also possible to confuse concepts in computing. That is, given the coding-decoding bijection between Turing machines and programs in a complete language, P ↔ p, it is nearly natural to use pfor P, or Pfor p, and after abstracting encodings away, π= [p], it is only a minor inconvenience to use πfor p, or pfor π. And the same ambiguity can be applied to data d, coded data  d, and information δ. But it is much better not to confuse these three levels: ◦Semantics or hardware: machine Pand data d. ◦Syntax or software: program pand coded data  d. ◦Pragmatics or knowledge: algorithm πand information δ. ¶5·By abstracting encodings away we are ignoring syntax. We could do it, but it would be dangerous because, in computing, syntax is prior to both semantics and pragmatics. In the beginning everything is syntax, because a Turing machine is a finite-state machine applying its syntactic rules to generic strings of symbols. It is later, when implementing a universal Turing machine, that a complete language that gives meaning to the whole of computing is required; so semantics is required to implement complete languages. And finally, if we abstract encodings away, we get language independent knowledge; now we can resolve problems algorithmically, meaning that their solutions can be coded in different complete languages and implemented in different hardware devices. However, to pragmatically resolve a problem, the algorithm has to be instantiated, that is, coded on a specific universal Turing machine, or implemented directly on a specific piece of hardware. All things considered, language independent knowledge could be misleading, since it promises more than it provides; use it with caution! www.ramoncasares.com 20241111 GPT 7 §6 Turing: Proof ¶1·So we are seeing that G¨odel (1930) is generalized by Turing (1936). Then we need to ascertain what generalizes G¨odel’s incompleteness theorem in Turing computing. As G¨odel (1930) writes in page 175, translated by Davis (1965) in page 9, “there is also a close relationship14 with the Liar paradox, for the undecidable proposition [R(q); q] says that qbelongs to K, i.e. according to (1), that [R(q); q] is not provable.” Note 14 says: “Every epistemological antinomy can be used for a similar proof of undecidability.” In any case, he uses the liar paradox, ‘this sentence is false’, that has not a definite meaning because it can neither be decided true nor false; if it is true what it says, then it is false, but if it is false what it says, then it is true, thus closing an infinite loop. In Turing computing, the only computations that result undecided are those that do not halt. ¶2·Therefore, the generalization of G¨odel’s incompleteness theorem is the theorem showing that the halting problem is unsolvable by a Turing machine. Though, in fact, the halting problem was defined later by Davis (1958),Turing (1936) had already shown that it is unsolvable, by resolving the circularity problem, see Petzold (2008) page 179. ¶3·proof ·Without loss of generality, we will use the complete language Limplemented by the universal Turing machine Ufor the proof. Lhas a finite set of symbols, and therefore the set of its finite strings is enumerable, using for example a shortlex order. That the syntax of Lis decidable means that we can always determine whether a string of Lis a coded string  dor not, implying that the set of coded strings is enumerable. Then we will refer to coded string number das  dd. And that the syntax of Lis decidable also means that we can always determine whether a string of Lis a program por not. The conclusion, which was perhaps doubtful in G¨odel’s proof, see §3¶6, it is easy to see in computing: the set of programs is enumerable. Then we will refer to program number pas pp. ¶4·We will set a Cantor’s diagonal argument to show that there is not any Turing machine Hthat takes any arbitrary pair of program pand coded data  das input, and every time it outputs, in a finite number of computing steps, a string expressing whether U⟨ p| d⟩ will halt or run indefinitely, say the one symbol string Yif it will halt, and Notherwise. ∃H,∀p,∀ d{H⟨ p| d⟩=Yif U⟨ p| d⟩halts H⟨ p| d⟩=Nif U⟨ p| d⟩does not halt ¶5·Now, for the sake of the argument, let us assume that Hexists. Then the following matrix of Yand Nstring values could be computed (without got stuck in a non-halting computation). H⟨p0| d0⟩ H⟨p0| d1⟩ H⟨p0| d2⟩. . . H⟨p0| dd⟩. . . H⟨p1| d0⟩ H⟨p1| d1⟩ H⟨p1| d2⟩. . . H⟨p1| dd⟩. . . . . .. . .. . ..... . .... H⟨pp| d0⟩ H⟨pp| d1⟩ H⟨pp| d2⟩. . . H⟨pp| dd⟩. . . . . .. . .. . ..... . .... However, the row for program q, which negates the diagonal, would not be in the matrix. q:∀n∈N{U⟨q| dn⟩=Yif H⟨pn| dn⟩=N U⟨q| dn⟩=∞if H⟨pn| dn⟩=Y www.ramoncasares.com 20241111 GPT 8 Program qwould exist if the program for H, denoted h, existed, which would be the case if Hexisted as assumed. Therefore, the assumption was false. ¶6·Then, in the complete language Lof the universal Turing machine U, a program h that solves the halting problem is inexpressible. And, taking advantage of the translation equation, this theorem holds for every complete language, which then can be formulated this way: in every complete language, there is an inexpressible program.qed ¶7·In computing, to say that there are undecidable computations is too trivial to be of any interest, since it just means that some computations do not halt, as for example while true {relax }or liar() = return( not liar() ). However, it is not only that in any complete language there are computations that do not halt, but also that there is not any computable way of avoiding them definitively. This parallels G¨odel’s conclusion that undecidable propositions cannot be avoided by adding them as axioms; you just need to use Cantor’s diagonal on the new formal system to find a new undecidable proposition. ¶8·From Turing’s conclusion that there are problems that cannot be solved by computing, it follows that, in every complete language, there are expressible problems the solutions of which are not expressible, so we can say that in every complete language there are concepts that can be defined, and named, but not expressed, see §10.2. Then another way to state Turing’s conclusion, which is closer to popular formulations of G¨odel’s incompleteness theorem, is: every complete language is not complete . This statement uses two different meanings of the word ‘complete’: the complete language is Turing complete because every Turing machine can be meaningfully expressed in it, but it is not G¨odel complete because there are definable tasks that no Turing machine can perform and, consequently, they cannot be expressed in it. Therefore, every Turing complete language is G¨odel incomplete . §7 Church: Thesis ¶1·Some of my readers could suspect that I am pretending to pass as new that Turing generalizes G¨odel. It is not my intention. In fact, this is known from the very beginning, since Turing (1936) himself, in page 259, shows that G¨odel’s incompleteness theorem is a consequence of his unsolvability theorem. This is his argument, where −Ais the negation of proposition A, and Entscheidungsproblem is the German word for ‘decision problem’: If the negation of what G¨odel [(1930)] has shown had been proved, i.e. if, for each A, either Aor −Ais provable [in the functional calculus K], then we should have an immediate solution of the Entscheidungsproblem. For we can invent a [Turing] machine Kwhich will prove consecutively all provable formulae. Sooner or later Kwill reach either Aor −A. If it reaches A, then we know that Ais provable. If it reaches −A, then, since Kis consistent [. . . ], we know that Ais not provable. In other words, if G¨odel’s incompleteness theorem were not the case, G, then Turing’s unsolvability of the decision problem would not be the case, T, denoted G→T, which is equivalent by contraposition to T→G, which means that Turing’s implies G¨odel’s, or in reverse, that G¨odel’s is a logical consequence of Turing’s. www.ramoncasares.com 20241111 GPT 9 ¶2·As these results on decidability and on solvability are all negative, a question arises: Could it be that they can be decided and solved by devices that are more capable than universal Turing machines? The accepted answer is Church’s thesis, which asserts that there are not more capable calculating devices than universal Turing machines . Before going on, please note that, in linguistic terms, the question becomes a revealing one, since it is asking for a language more expressive than a complete language but in which the sentence ‘this sentence is false’ is not expressible, a sentence that is expressible in every complete language. Linguistically, the impossibility is apparent. ¶3·The interesting story, or history, around Church’s thesis is detailed by Davis (1982), who explains why G¨odel preferred Turing machines over his own recursive functions and over Church’s λ-calculus in order to fix Church’s thesis. As we have written above, the advantage of Turing computable functions, which are those from strings to strings implemented by Turing machines, is that they are much more generic and simpler than G¨odel’s recursive functions, and the same applies to Church’s λ-definable functions. For example, in the case of the recursive functions, in order to achieve a capability equivalent to Turing completeness, it was necessary to add a conditional incremental loop to the decremental loop of primitive recursion, see Kleene (1952) Chapter XI, an addition which we could describe as a hack, and even then G¨odel “was [. . . ] not at all convinced that [his] concept of recursion comprises all possible recursions”, as cited by Davis (1982) in page 8. This explains why we have used universal Turing machines when we presented Church’s thesis, while Church (1935) himself used recursive functions and λ-calculus instead, and it also explains why, though he resolved the Entscheidungsproblem as unsolvable before Turing (1936), we prefer the cleaner proof by Turing. ¶4·According to Kleene (1952), from page 319 on, the arguments supporting Church’s thesis as the accepted answer are of four types: heuristic evidence, equivalence of diverse formulations, Turing’s concept of a computing machine, and symbolic logics and symbolic algorithms. As an example of the second type, it is really convincing that, even being so different, computing, recursion, and λ-calculus are all capable of universality. The computing version of universality is Turing completeness, that is, that computing can express computing completely, as we saw above. In the case of recursion, it is Kleene’s (1935a) normal form, see Kleene (1952) Theorem IX in page 288, where a recursive function can express any recursive function. And, for Church’s λ-calculus, it is that an evaluator of λ-expressions can be defined as a λ-defined function, resulting that the evaluator is a λ-defined function able to express any λ-defined function; this is done (in Lisp) by Abelson & Sussman (1985). Universality, or full-self-expressibility, manifests itself in all three formulations because they are equivalent, as shown by Kleene (1935b) and Turing (1937). ¶5·To me, that all formulations of the concept of computing point to the same calculating maximum limit, which is universality, suggests that the limit has an empirical meaning. For suppose these two possibilities: ◦Tomorrow someone devises a procedure to perform calculations that are beyond the capability of a universal Turing machine. ◦Tomorrow some machine is found that performs calculations that are beyond the capability of a universal Turing machine. In either case, Church’s thesis would be wrong. Then, Church’s thesis is uncertain because it depends on what it might occur tomorrow, showing that it is empirically refutable. www.ramoncasares.com 20241111 GPT 16 Davis (1982): Martin Davis, “Why G¨odel Didn’t Have Church’s Thesis”; in Information and Control, vol. 54, pp. 3–24, 1982, doi: 10.1016/s0019-9958(82)91226-8. G¨odel (1930): Kurt G¨odel, ,,¨ Uber formal unentscheidbare S¨atze der Principia Mathematica und verwandter Systeme I“; in Monatshefte f¨ur Mathematik und Physik, vol. 38, pp. 173–198, 1931, doi: 10.1007/BF01700692. Received November 17, 1930. English translation in Davis (1965). Kleene (1935a): Stephen Kleene, “General Recursive Functions of Natural Numbers”; in Mathematische Annalen, vol. 112, no. 1, pp. 727–742, December 1936, doi: 10.1007/BF01565439. Presented to the American Mathematical Society, September 1935. Kleene (1935b): Stephen Kleene, “λ-Definability and Recursiveness”; in Duke Mathematical Journal, vol. 2, pp. 340–353, 1936, doi: 10.1215/s0012-7094-36-00227-2. Received July 1, 1935; presented to the American Mathematical Society, September 13, 1935. Kleene (1952): Stephen Kleene, Introduction to Meta-Mathematics; Ishi Press, New York, 2009, isbn: 978-0-923891-57-2. Reprint of the same title by North-Holland, Amsterdam, 1952. Mealy (1955): George H. Mealy, “A Method for Synthesizing Sequential Circuits”; in Bell System Technical Journal, vol. 34, no. 5, pp. 1045–1079, September 1955, doi: 10.1002/j.1538-7305.1955.tb03788.x. Manuscript received May 6, 1955. Moore (1956): Edward F. Moore, “Gedanken-Experiments on Sequential Machines”; doi: 10.1515/9781400882618-006. In Automata Studies (editors C. E. Shannon and J. McCarthy), Volume 34 in the series Annals of Mathematics Studies (AM34); Princeton University Press, Princeton, 1956, pp. 129–153; isbn: 0-691-07916-1. Petzold (2008): Charles Petzold, The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine; Wiley Publishing, Indianapolis, 2008, isbn: 978-0-470-22905-7. Post (1936): Emil L. Post, “Finite Combinatory Processes — Formulation 1”; in The Journal of Symbolic Logic, Volume 1, Number 3, pp. 103–105, September 1936, doi: 10.2307/2269031. Received October 7, 1936. Post (1944): Emil L. Post, “Recursively Enumerable Sets of Positive Integers and their Decision Problems”; in Bulletin of the American Mathematical Society, vol. 50, no. 5, pp. 284–316, 1944, doi: 10.1090/s0002-9904-1944-08111-1. Shagrir & Pitowsky (2003): Oron Shagrir and Itamar Pitowsky, “Physical Hypercomputation and the Church-Turing Thesis”; in Minds and Machines, vol. 13, pp. 87–101, 2003, doi: 10.1023/A:1021365222692. Turing (1936): A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”; in Proceedings of the London Mathematical Society, vol. s242, no. 1, pp. 230–265, 1937, doi: 10.1112/plms/s2-42.1.230. Received 28 May, 1936. Read 12 November, 1936. Turing (1937): A. M. Turing, “Computability and λ-Definability”; in The Journal of Symbolic Logic, vol. 2, no. 4, pp. 153–163, December 1937, doi: 10.2307/2268280. Turing (1938): A. M. Turing, “Systems of Logic Based on Ordinals”; in Proceedings of the London Mathematical Society, vol. s2-45, no. 1, pp. 161–228, 1939, doi: 10.1112/plms/s2-45.1.161. Received 31 May, 1938. Read 16 June, 1938.