From 39939a29fbaf4a511b85be60074e544df954c320 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Fri, 14 Aug 2026 09:58:48 +0000 Subject: [PATCH] more tweaks to font matter --- document/book/TM-2026.html | 42 ++++++++++++++++++++++++++++++++------ document/book/notes.txt | 23 +++++++++++++++++++++ 2 files changed, 59 insertions(+), 6 deletions(-) create mode 100644 document/book/notes.txt diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index 48e0688..56fb819 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -193,9 +193,13 @@ - + The search that led to the Turing Machine +

+ The survey material here is limited to that which is relevant to the Computation Naturalism thesis of this book. It would have been easy to keep pulling on these threads and end up with a history book instead. There is far more to the story of the foundation of mathematics than what is presented here. +

+

In 1893 Gottlob Frege published an axiomatic construction of mathematics from set theory. Frege's grand objective was the programme later called Logicism, the philosophical thesis that all of mathematics can be derived entirely from pure logic. To bridge set theory and logic, Frege defined sets using a method known as set comprehension. Under this approach, a mathematician states a logical rule or property, and any object satisfying that logical statement automatically becomes a member of the set. Because the membership of a set is determined entirely by logical rules, the resulting sets, and the mathematics built upon them, are derived directly from logic. To implement this, his specific machinery relied upon unrestricted set comprehension, formalized as Basic Law V Gottlob Frege, Grundgesetze der Arithmetik, Vol. 1 (Jena: Hermann Pohle, 1893), §20..

@@ -226,16 +230,30 @@

- The authority to remove Russell's Paradox set formulation comes from the set S. If we know its definition, then the authority comes through that definition. However, if we merely stipulate that S must be defined, then we are expressing our authority through S by declaring, "Undefined sets are not allowed." In the explanation above, it is only after discovering a set is undefined that we conclude it is not a member of Sibid. I sometimes wonder how mathematics might have evolved had Frege simply taken that approach. We take this question up again in chapter , Computational Naturalism, and discover there is a deeper issue. + The authority to remove Russell's Paradox set formulation comes from the set S. It is not that undefined sets are disallowed, as \dot{R} is perfectly well defined, the Axiom of Separation having defined it. It is that membership in S is granted by prior construction and never by satisfying a condition. A condition can only partition what S already holds, so it has no power to admit. This is why the very condition that is fatal under unrestricted comprehension is harmless under separation: in the first it was doing the admitting, and in the second it is not. Though this invites an objection. If S is stocked in advance, and a condition can only sort what is already inside, then have we not merely arranged for \dot{R} to be absent and called the arrangement a repair? I sometimes wonder how mathematics might have evolved had Frege simply taken that approach and declared such formulations dismissed. It is not the same thing, and showing why requires machinery we do not have yet. We take the question up again in section .

Stepping back from the mechanics of set definition, a person can observe two competing approaches to establishing mathematical foundations. The first approach is constructive, building complex systems by assembling them upward from fundamental primitives. The second approach relies on islands of meaning, carving out valid spaces from the abstract void using precise rules and axioms, exactly as Zermelo did. Because both methodologies rely entirely upon a rigorous framework of deduction, logic itself serves as the essential substrate. Consequently, a complete study of the foundation of mathematics requires the examination of three distinct subjects: the primitives used for construction, the rules that bound the theoretical islands, and the underlying logic that evaluates them both.

-

- In 1928 David Hilbert and Wilhelm Ackermann published a textbook on mathematical logic, Grundzüge der theoretischen Logik David Hilbert and Wilhelm Ackermann, Grundzüge der theoretischen Logik (Berlin: Springer, 1928). This first edition has not been translated into English.. A feature of this book is its attention to procedures to follow for mechanically determining truth of statements. They called the problem solved by such a procedure the Entscheidungsproblem. In the first chapter they review the procedure for solving the Entscheidungsproblem in the propositional logic. For the first-order predicate calculus they define the problem as, "Universal validity concerns the following question: How can one determine, for any given logical expression that contains no individual signs [constants], whether the expression represents a true assertion for arbitrary substitutions for the occurring variables, or not?" Hilbert and Ackermann, Grundzüge der theoretischen Logik, 72–73.. They review some special cases with solutions, including one published earlier by Ackermann, but then throw down the gauntlet by saying, - "A general solution to the Entscheidungsproblem, regardless of whether a person considers the first or the second formulation, is not yet available." Hilbert and Ackermann, Grundzüge der theoretischen Logik, 81. "Eine allgemeine Lösung des Entscheidungsproblems, mag man nun die erste oder die zweite Fassung nehmen, liegt bis jetzt noch nicht vor." The term Entscheidungsproblem literally translates to 'decision problem'. However, there are many types of decision problems, and later we will meet a class of Turing Machine programs called deciders, so it appears to be best to keep the original German. As we will see later Alan Turing also did this.. +

In 1922 Hilbert lectured on the foundations of arithmetic, and he appears to be the first to use the word metamathematics in its modern sense, for the study of formal systems as objects, in which axioms, formulas, and proofs are treated as finite arrangements of symbols and are reasoned about from outside, by means that the system under examination need not itself contain + David Hilbert, "Neubegründung der Mathematik. Erste Mitteilung," Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 1 (1922): 157–177. The word reached print as Metamathematik in David Hilbert, "Die logischen Grundlagen der Mathematik," Mathematische Annalen 88 (1923): 151–165. Hilbert did not coin the word. It appears in English in the 1870s as a term of derision for speculation about non-Euclidean geometry, formed on the model of 'metaphysics' and carrying the same charge of idle abstraction. Charles Porterfield Krauth, A Vocabulary of the Philosophical Sciences (New York: Sheldon, 1879), defines it as the philosophy of mathematics, and the 1890 Funk & Wagnalls dictionary gives 'the philosophy or metaphysics of mathematics'. What Hilbert repurposed was a slur that had been aimed at the very geometry which made the subject necessary. On the earlier usage see Jeff Miller, "Earliest Known Uses of Some of the Words of Mathematics," entry for METAMATHEMATICS, which credits the observation to John Aldrich.. + The distinction the word draws is between working within a system and working upon one. The practice predates the branding. In one of the better known examples, when Beltrami built a surface upon which Euclid's parallel postulate fails, he proved nothing about triangles. He proved that one axiom could not be derived from the others, which is a fact about a collection of axioms and not about space + Eugenio Beltrami, "Saggio di interpretazione della geometria non-euclidea," Giornale di Matematiche 6 (1868): 284–312.. + Russell supplies another example from earlier in this chapter. When he exhibited his set, he proved nothing about sets. He proved that Frege's system was inconsistent. In each case the object under examination was a mathematical system, and the examination was itself done using mathematics. +

+ +

In 1928 David Hilbert and Wilhelm Ackermann published a textbook on mathematical logic, Grundzüge der theoretischen Logik + David Hilbert and Wilhelm Ackermann, Grundzüge der theoretischen Logik (Berlin: Springer, 1928). This first edition has not been translated into English.. + A feature of this book is its attention to procedures to follow for mechanically determining truth of statements. They called the problem solved by such a procedure the Entscheidungsproblem + The term Entscheidungsproblem literally translates to 'decision problem'. However, there are many types of decision problems, and later we will meet a class of Turing Machine programs called deciders, so it appears to be best to keep the original German. As we will see later Alan Turing also did this.. + In the first chapter they review the procedure that solves it for the propositional logic. Raising the same question for the first-order predicate calculus, they ask the question of metamathematics: how one can determine, for an arbitrary logical expression, whether it represents a true assertion under every substitution for the variables occurring in it + Hilbert and Ackermann, Grundzüge der theoretischen Logik, 72–73. The authors' formulation restricts the question to expressions containing no individual signs, that is, no constants. This is a normalisation of the input rather than a limitation on what can be asked. A constant can be replaced by a fresh variable without affecting the answer, and the authors do this on page 73 for propositional variables, noting that these too can always be eliminated. Where a system of axioms fixes the meaning of its predicates, as with the geometry worked through on pages 74 to 76, those predicates are likewise replaced by variables and the content of the axioms is gathered into the antecedent of a single implication, so that a question about a particular subject matter becomes a question about the validity of a formula containing nothing determinate at all. I have left the restriction out of the sentence above because it answers a question the reader has not yet had occasion to ask.. + They then show what such a procedure would be worth, working through the axioms of geometry: it would mechanically settle whether a given theorem follows from a given system of axioms, and whether that system is consistent at all. Having reviewed the special cases that have been solved, including one by Ackermann himself, then still awaiting publication, they concede that "A general solution to the Entscheidungsproblem, whether one takes the first or the second formulation, is not yet available." + Hilbert and Ackermann, Grundzüge der theoretischen Logik, 81. "Eine allgemeine Lösung des Entscheidungsproblems, mag man nun die erste oder die zweite Fassung nehmen, liegt bis jetzt noch nicht vor." The two formulations are distinguished on page 80: the first asks, of a given expression, for which domains of individuals it is valid and for which it is not; the second asks only whether it is valid for all domains. The second suffices for deciding whether a theorem follows from a system of axioms. + And so they throw down the gauntlet: "The fundamental significance of the Entscheidungsproblem should by now be sufficiently clear; the Entscheidungsproblem must be regarded as the main problem of mathematical logic." + Hilbert and Ackermann, Grundzüge der theoretischen Logik, 77. "Die fundamentale Bedeutung, die das Entscheidungsproblem besitzt, dürfte damit genügend illustriert sein; das Entscheidungsproblem muß als das Hauptproblem der mathematischen Logik bezeichnet werden." The italics are the authors' own. Note that this sentence precedes the concession quoted above: it closes § 11, on page 77, whereas the admission that no general solution exists opens the survey of solved special cases in § 12, on page 81. I have reversed the order because the declaration reads to a modern eye as a response to the open problem, which is how the following decade received it, while in the book it serves to introduce the survey that establishes the problem is open. The sentence is conventionally rendered "the decision problem must be called the main problem of mathematical logic"; my translation differs in three small ways. I keep the German Entscheidungsproblem throughout, for the reason given above. I render bezeichnet werden as "regarded as" rather than the literal "designated as", because modern English "designate" reads as an act of naming, whereas the German here is passing judgement on the problem's standing. And dürfte damit genügend illustriert sein is a courteous subjunctive with no close modern equivalent — literally "may thereby be presumed to be sufficiently illustrated" — which I have flattened to "should by now be sufficiently clear".

@@ -545,6 +563,18 @@ Famously, we know that no analyzer can universally determine whether a machine is computational, i.e. that it halts in a finite number of steps. This was proven by reasoning about, i.e. analyzing, the properties of a hypothetically existing halting analyzer machine. A count of the layers shows that this was a third-order analysis activity.

+

+ Russell's set formulation of section is worth taking up here. It is perfectly legal to write a Turing Machine that accepts or rejects a proposed element by evaluating a logical predicate on it, and R = \{x \mid x ∉ x\} is such a machine. Asked whether R is a member of R, it will not halt. First-order analysis therefore returns nothing about it at all, which is the condition described above under which the only remaining option is a higher-order analysis. So the machine, its input, and the whole system around it are written to a tape and reasoned about instead, which is what was done in that section and what we are doing here. R is not dismissed. It is promoted. +

+ +

+ The dotted formulation is a different machine. Asked whether \dot{R} is a member of \dot{R}, it evaluates the first term, finds that \dot{R} is not in S, rejects, and stops. It halts because the first term hands it a question that prior construction has already settled, so the second term is never given a candidate it can loop on. This is the authority of S seen from the machine side: the predicate was not forbidden, it was placed downstream of something decidable. +

+ +

+ That leaves the question of whether excluding \dot{R} from S is a repair or merely an arrangement. Note that we never ran a test for it. The definition of S was never given, so there was nothing to run. The exclusion was obtained by reasoning about the formulation, which is to say at the second order, and a result obtained is not a stipulation made. Had Frege merely declared such formulations dismissed, there would be no formalization left to reason with, and nothing standing to be promoted. A question is left open by this. If there are machines that first-order analysis can not reach, and that is what forced the second order, then are there machines that second-order analysis can not reach either? If Gödel has a say, a person would wager that there are. +

+

All orders of analysis come down to running a machine. There is no difference in architecture between a machine doing first-order analysis and one doing second-order analysis, etc. The order of analysis is only assigned by analyzing the system as a whole, and it exists outside the system, and thus does not affect the computation, so it is merely useful information when discussing the system. However, this would change if this system meta-information were fed back into the system for decisions to be made upon it.

@@ -4883,7 +4913,7 @@ --> diff --git a/document/book/notes.txt b/document/book/notes.txt new file mode 100644 index 0000000..b217d1e --- /dev/null +++ b/document/book/notes.txt @@ -0,0 +1,23 @@ + +Alfred Tarski, Logic, semantics, matamathematics_Papers from 1923 to 1938 + +ON SOME FUNDAMENTAL CONCEPTS +OF METAMATHEMATICS + +following Hilbert, it is customary to call +metamathematics.[1] + +S is the set of all sentences + +X,Y ⊆ S: X -> rules of inference making and extending all possible branches -> Y ; the consequences + +Cn(X) is the set of all consequences + +I would not have htought this, because I don't see why X must be a subset of Consequences of X: +Axiom 2: If X ⊆ S, then X ⊆ Cn(X) c S. + +Axiom 3 +X ⊆ S, then Cn(Cn(X)) = Cn(X) + +Axiom 2 +X ⊆ S, then X ⊆ Cn(X) ⊆ S -- 2.20.1