From b95cf97716ddc1dea745f4bcb8e9280a755172e9 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Wed, 19 Aug 2026 17:04:49 +0000 Subject: [PATCH] adding first Nat thes chapt, still an outline --- document/book/TM-2026.html | 507 ++++++++++++++++++++----------------- 1 file changed, 281 insertions(+), 226 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index 37bb299..510e5d8 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -34,7 +34,7 @@ - + Exordium

My colleagues in computer arithmetic work tirelessly to confirm Schopenhauer's thesis, so I am left to chose among only unfunded inconsequential problems that no one else wants.

@@ -46,12 +46,12 @@ - - Common Ground + + Conventio -

All communication builds upon a foundation of common knowledge, so let us begin by searching for some common ground. This section discusses the terminology and conventions the rest of the book is based upon. It is a chapter for getting accustom to the language used. However, this chapter is not intended to present new material, nor to serve as a tutorial for the discussed subjects.

+

All communication starts from the knowledge held in common between the author and reader. This chapter is a first meeting and a search for that commonality. It is not the start of the thesis of the book, that being Computational Naturalism. That topic doesn't even come up. A reader who skipped these pages would be more likely to misread what follows, but would not miss any of the argument. What follows is the notation this book is written in and the words it takes from mathematics and logic. There are some terms introduced by this book and mentioned here, and those are so marked.

- + Notation

In math spans and blocks, each container, such as a sequence or a set, is represented with a single capital letter, even when in Greek. Each object that is not a container is represented with a single lower case letter. Character pairs or full symbol names can also be used to represent math objects, in which case the same convention is followed for the first letter of the symbol, while the remaining letters are lower case. The context will make it clear if a non-letter Unicode character represents a container or a non-container.

@@ -93,7 +93,7 @@

The Unicode middle dot, ·, is used as an ad hoc namespace operator in identifiers. Hence N·x would be the variable x from the N namespace. This is a typographic symbol with a long history of use as a separator. It appears in dictionaries where words are broken into syllables, e.g. 'op·er·a·tor'. It is a letter of the Catalan alphabet, the punt volat, which distinguishes the geminate l·l of 'col·legi' from the digraph ll. And Japanese uses it, as the nakaguro, to separate the components of a transliterated foreign name. It is accepted in identifiers by modern C compilers,C11 permits the character anywhere in an identifier, including as the first character: it falls in the 00B7−00BA range of Annex D.1, and appears in none of the ranges disallowed initially in D.2. C23 restates the rule in terms of Unicode UAX #31, where the character belongs to Other_ID_Continue and so remains permitted, though no longer in first position. ISO/IEC 9899:2011, Annex D; ISO/IEC 9899:2024, §6.4.2. and it is part of the RT·gcc compiler mods as an ad hoc namespace operator.

 - + Usage

In the RT coding culture, we say that argument values are given to a function. Functions do not take arguments, as it is the caller that has authority over making the call, and thus over sending the arguments. A function is only said to accept or reject a value in the context of guard code evaluating argument validity, something it has authority to do. Similarly, machines, factories, and software make objects by assembling components they are given; they do not create them, since bringing components into being is not within an engineer's authority. That leaves 'creation' to imply a more fundamental synthesis outside the scope of engineering, perhaps done by artists or supernatural beings.

@@ -105,27 +105,27 @@

Dates and times are given in the ISO 8601 format. The components run from the most-significant to the least-significant, year, then month, then day, in the same order the digits of a Hindu-Arabic numeral run. Two consequences follow from that ordering, and both are the reason for choosing it. A lexicographic comparison of two such dates agrees with their chronological comparison, so a list of them sorts correctly with no collation rules particular to dates. And the format is unambiguous, whereas a date such as 03/04/2026 is read as the third of April by some readers and the fourth of March by others. A time of day, when one is given, follows the date, and a trailing Z marks the time as UTC. Hence 2026-06-01 08:28:00Z. ISO 8601 itself separates the date from the time with a T, which is difficult to read. RFC 3339 anticipates the objection and permits a space in its place, and that is the option taken here.Graham Klyne and Chris Newman, Date and Time on the Internet: Timestamps, RFC 3339, July 2002, §5.6. Where a date appears without a time, the date alone is intended, e.g. 2026-06-01. As per the standard, if the day is not to be specified, it is simply dropped, e.g. 2026-06.

 - + Number types -

Several words in this book carry a formal definition that displaces their ordinary English sense, and those are capitalized: Peano Number, Integer, Rational, Real. The word real is the best example of why this is done. It was too much of an ask by mathematics to take a common English adjective and hold it to a technical meaning, and a reader is entitled to know which sense is in play. So a Real is the object mathematics defines, and a real problem or a real difficulty is the ordinary English word. Integer suffers no such ambiguity. It is capitalized for consistency with its siblings.

+

Several words in this book carry a formal definition that displaces their ordinary English sense, and those are capitalized: Peano Number, Integer, Rational, Real. The word real is the best example of why this is done. It was too much of an ask by mathematics to take a common English adjective and hold it to a technical meaning, and a reader is entitled to know which sense is in play. So a Real is the object mathematics defines, and a real problem or a real difficulty is the ordinary English word. Integer suffers no such ambiguity. It is capitalized for consistency with its siblings.

The leading capital letter on the mathematical number types does not distinguish the classical notion from the one constructed herein, because this book denies that the two are distinct in the first place. A Real is a Real whether a mathematician defines it or a machine produces the definition.

-

What mathematics calls the natural numbers are called Peano Numbers in this book. A Peano Number is what a Peano Machine outputs. This convention frees the word 'Natural' to refer to the philosophy only, so a reader never has to work out which of the two is meant. Note that herein Peano Numbers are taken to begin at zero, while Counting Numbers begin at one, and the two are not the same.Peano's own axioms began at one. Modern presentations of Peano arithmetic begin at zero, and that is the convention followed here. Giuseppe Peano, Arithmetices principia, nova methodo exposita (Turin: Bocca, 1889), §1. An Integer, a Rational, and a Real are likewise the outputs of machines, each constructed in its turn.

+

What mathematics calls the natural numbers are called Peano Numbers in this book. A Peano Number is what a Peano Machine outputs. This convention frees the word 'Natural' to refer to the philosophy only, so a reader never has to work out which of the two is meant. Note that herein Peano Numbers are taken to begin at zero, while Counting Numbers begin at one, and the two are not the same.Peano's own axioms began at one. Modern presentations of Peano arithmetic begin at zero, and that is the convention followed here. Giuseppe Peano, Arithmetices principia, nova methodo exposita (Turin: Bocca, 1889), §1. An Integer, a Rational, and a Real are likewise the outputs of machines, each constructed in its turn.

 - + Fields of study -

Number Theory consists of the analysis of Peano Number related structures. It gives properties to these structures, e.g. the familiar 'odd' and 'even'. It gives properties to the relationship between numbers and operations on those numbers, e.g. proving that an odd number squared is odd. It deals with the solution of mixed integer equations, and systems of such equations, and sets the rules for modulus arithmetic. For example, encryption algorithms belong to Number Theory.

+

Number Theory consists of the analysis of Peano Number related structures. It gives properties to these structures, e.g. the familiar 'odd' and 'even'. It gives properties to the relationship between numbers and operations on those numbers, e.g. proving that an odd number squared is odd. It deals with the solution of mixed integer equations, and systems of such equations, and sets the rules for modulus arithmetic. For example, encryption algorithms belong to Number Theory.

-

Numerical Analysis is built on two axioms. The first axiom limits computing to vectors of Peano Numbers, where a vector represents a number. A common representation is a number pair, where one number of the pair scales the other number, thus making it possible to represent fractional values. The second axiom states the actual intention of the programmer is to perform computation over a Real field. As Real Numbers fall on a continuum, it follows that some Real Numbers can not be represented with a vector of Peano Numbers. The objective of Numerical Analysis is then to establish the relationship between Peano Number results with the corresponding exact Real Number results. The difference between the two is called error. People who work in numerical algorithm design often spend a great deal of time trying to keep some metric of error low over a given domain.

+

Numerical Analysis is built on two axioms. The first axiom limits computing to vectors of Peano Numbers, where a vector represents a number. A common representation is a number pair, where one number of the pair scales the other number, thus making it possible to represent fractional values. The second axiom states the actual intention of the programmer is to perform computation over a Real field. As Real Numbers fall on a continuum, it follows that some Real Numbers can not be represented with a vector of Peano Numbers. The objective of Numerical Analysis is then to establish the relationship between Peano Number results with the corresponding exact Real Number results. The difference between the two is called error. People who work in numerical algorithm design often spend a great deal of time trying to keep some metric of error low over a given domain.

Computation Theory consists of proofs over what can, and cannot be computed, the time and space complexity of algorithms, and the fundamental structure of computation. Number Theory is a kind of Computation Theory applied to Peano Structures before Church, Turing, and their contemporaries gave computation theory its name.

 - + Symbol

A math object is anything mathematics is willing to name: a number, a set, a function, a formula, or a symbol. Nothing further is meant by it. A value, where the term is used without qualification, is synonymous with math object.

@@ -148,21 +148,21 @@

Because a function annotates what goes in and out of an inner scope, any evaluation context, or set of evaluation contexts, can be interpreted as being a function.

-

The term constant is a property ascribed to an object when a primary aspect of that object under discussion does not change across evaluation contexts. Different primary aspects are conventionally considered. Of a fixed symbol, the aspect is its binding as an object. Of a function, it is the return value, which for a constant function is the same for every evaluation. Of a primitive math object such as an individual Peano Number, it is the object itself. This latter usage would mean that the term constant is the same as a math object, and thus the same as value.

+

The term constant is a property ascribed to an object when a primary aspect of that object under discussion does not change across evaluation contexts. Different primary aspects are conventionally considered. Of a fixed symbol, the aspect is its binding as an object. Of a function, it is the return value, which for a constant function is the same for every evaluation. Of a primitive math object such as an individual Peano Number, it is the object itself. This latter usage would mean that the term constant is the same as a math object, and thus the same as value.

 Logic - + Propositional calculus

A proposition is a statement that is given no arguments and carries a truth value, that being one of exactly two things, written true and false. A proposition is not predicated upon anything, so settling it requires nothing to be looked up and no value to be supplied. "The moon is made of green cheese" is a proposition, and it is false. "Seven is prime" is a proposition, and it is true. In either case the statement stands complete as it is written. Nothing in the calculus that follows looks inside a proposition or has any means of altering one. A proposition enters the calculus carrying its truth value, and the calculus makes use of nothing else about it.

The connectives are symbols, and instances of their representations are these: ∧ (and), ∨ (or), ¬ (not), → (implies), and ↔ (if and only if). Alongside them stand the parentheses, ( and ), which group. Each connective is fixed, in that what it does is settled once for the whole calculus and nothing later on is at liberty to change it. What each one does is combine truth values to give a truth value, so ∧ gives true exactly when both of the truth values given to it are true, ¬ gives the truth value it was not given, and so on for the rest.

-

Beside the connectives stand the proposition symbols, whose representations are commonly p, q, and r. These are variables. A proposition symbol has no meaning of its own, and marks a place where a proposition is later bound to it. It is the only kind of symbol in this calculus that is not fixed.The letters follow the notation convention of section , applied to whatever the symbol marks a place for. A proposition is not a container, so the letter is lower case. A formula is a string and therefore a container, so the letters standing for formulas below are capitals.

+

Beside the connectives stand the proposition symbols, whose representations are commonly p, q, and r. These are variables. A proposition symbol has no meaning of its own, and marks a place where a proposition is later bound to it. It is the only kind of symbol in this calculus that is not fixed.The letters follow the notation convention of section , applied to whatever the symbol marks a place for. A proposition is not a container, so the letter is lower case. A formula is a string and therefore a container, so the letters standing for formulas below are capitals.

Symbol instances are strung together according to the formation rules, and what the rules build is called a formula. The rules are three, and the third is what closes the definition. The Greek letters Φ and Ψ stand for whole formulas below, and ∘ stands for any one of the binary connectives. All three belong to this discussion rather than to the calculus being discussed.

@@ -178,7 +178,11 @@

For example, (p ∧ ¬q) is a formula. Rule 1 supplies p, and supplies q. Rule 2 applied to q supplies the negation, ¬q. Rule 2 applied again, this time to the pair, supplies (p ∧ ¬q), and the parentheses arrive with that application rather than by any step of their own, because the rule writes them. Rule 3 then terminates the process by saying nothing more can be added. Every formula arrives through this same method.

-

A computer scientist would see the formation rules as forming a grammar, and a parser built from them would sort strings into two categories, the well formed formula and the malformed formula. Take the string p ¬ ∧ q, which would not parse. A logician would point out that this string is not a result of applying the formation rules, so it is simply not a formula at all, and there is no second category called malformed formula for it to fall into. Yet the traditional term used by logicians for a formula is well formed formula, shortened to wff, and along with formula all three are used interchangeably.Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed. (San Diego: Harcourt/Academic Press, 2001), §1.1, which introduces the three words as alternatives for one thing. Texts that keep the adjective and texts that drop it are describing the same objects. The adjective invites the reading that a determination carries its own negation along with it, so that well formed implies something for it to be distinguished from; the point is Hegel's, taken over from Spinoza's omnis determinatio est negatio. G. W. F. Hegel, Wissenschaft der Logik (Nuremberg: Schrag, 1812–1816), Book One, on determinate being; Baruch Spinoza to Jarig Jelles, June 2, 1674, Letter 50.A C++ committee borrowed the terminology for a well formed program, and then found it necessary to name the opposite, which became the ill formed program. ISO/IEC 14882, [defns.well.formed] and [defns.ill.formed], which pair the two definitions: a well formed program is one constructed according to the syntax rules, the diagnosable semantic rules, and the One Definition Rule, and an ill formed program is one that is not well formed. There the pair does work, because a compiler is required to say which side a given input falls on. This book uses formula.

+

A computer scientist would see the formation rules as forming a grammar, and a parser built from them would sort strings into two categories, the well formed formula and the malformed formula. Take the string p ¬ ∧ q, which would not parse. However, a logician would point out that this string is not a result of applying the formation rules, so it is simply not a formula at all, and there is no second category called malformed formula for it to fall into. Yet the traditional term used by logicians for a formula is well formed formula, shortened to wff, and along with formula all three are used interchangeably. + Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed. (San Diego: Harcourt/Academic Press, 2001), §1.1, which introduces the three words as alternatives for one thing. Texts that keep the adjective and texts that drop it are describing the same objects. + Meanwhile the philosophers have spent two centuries telling us that naming a thing this way implies the existence of its opposite. + That a determination carries its own negation is Hegel's point, taken from Spinoza's omnis determinatio est negatio. G. W. F. Hegel, Wissenschaft der Logik (Nuremberg: Schrag, 1812–1816), Book One, on determinate being; Baruch Spinoza to Jarig Jelles, June 2, 1674, Letter 50. A C++ committee borrowed the adjective for a well formed program and then found it necessary to name the opposite, which became the ill formed program. ISO/IEC 14882, [defns.well.formed] and [defns.ill.formed]. There the pair does work, because a compiler is required to say which side a given input falls on. + Who do we believe, the logicians or the philosophers? This book accepts the term malformed formula for something intended or presented as a formula, although when the formation rules are applied as a grammar, turns out to have one or more syntax errors.

An interpretation binds a proposition to each proposition symbol of a formula. Since each connective combines truth values and inspects nothing else, an interpretation carries no more information than the truth value each bound proposition holds, and the formula then holds or fails according to those truth values alone. Let p be bound to "the clock line is high" and q to "the enable line is high"; whether (p ∧ ¬q) holds follows from those two truth values and from nothing else. An interpretation does not alter the formula, which was settled before any interpretation was considered, and it does not reach inside a proposition, which was settled before it was bound.

@@ -211,17 +215,16 @@ - - + First-order predicate calculus -

Now suppose that a proposition could be predicated on something else. A predicate is a logic function. It is given values for its arguments, and it then evaluates to true or to false. Give a predicate its arguments and what results is a proposition, so the predicate is the general case and the proposition is the settled one. \text{prime}(x) is a predicate of one argument, and \text{prime}(7) is true while \text{prime}(8) is false. <(x, y) is a predicate of two arguments, which is how a relation is written. Thus <(3, 5) is true, while <(5, 3) is false. Predicate arguments are drawn from a domain, a set holding at least one member, and that set is whatever mathematics cares to name: the Peano Numbers, the points of a plane, the strings over an alphabet. Nothing requires the arguments to be truth values, and nothing forbids it. What is required is that the result be a truth value.

+

Now suppose that a proposition could be predicated on something else. A predicate is a logic function. It is given values for its arguments, and it then evaluates to true or to false. Give a predicate its arguments and what results is a proposition, so the predicate is the general case and the proposition is the settled one. \text{prime}(x) is a predicate of one argument, and \text{prime}(7) is true while \text{prime}(8) is false. <(x, y) is a predicate of two arguments, which is how a relation is written. Thus <(3, 5) is true, while <(5, 3) is false. Predicate arguments are drawn from a domain, a set holding at least one member, and that set is whatever mathematics cares to name: the Peano Numbers, the points of a plane, the strings over an alphabet. Nothing requires the arguments to be truth values, and nothing forbids it. What is required is that the result be a truth value.

-

A property is a predicate of one argument. It is not a new kind of object; it is the one-argument case of the predicate already defined. \text{even} is a property of the Peano Numbers, holding of 4 and failing of 5, and \text{prime} is another. To give a property over a domain is to mark off which members of that domain it holds of, so the properties of a domain stand in exact correspondence with the sub-collections of it, and a domain of n members carries 2^n properties.This correspondence counts two predicates holding of the same members as the same property, a convention called extensionality. It sets aside the sense in which 'is an equilateral triangle' and 'is an equiangular triangle' are different properties that happen to hold of the same figures. The properties of a domain form a collection of their own, distinct from the domain, so a quantifier ranging over the one is not ranging over the other.

+

A property is a predicate of one argument. It is not a new kind of object; it is the one-argument case of the predicate already defined. \text{even} is a property of the Peano Numbers, holding of 4 and failing of 5, and \text{prime} is another. To give a property over a domain is to mark off which members of that domain it holds of, so the properties of a domain stand in exact correspondence with the sub-collections of it, and a domain of n members carries 2^n properties.This correspondence counts two predicates holding of the same members as the same property, a convention called extensionality. It sets aside the sense in which 'is an equilateral triangle' and 'is an equiangular triangle' are different properties that happen to hold of the same figures. The properties of a domain form a collection of their own, distinct from the domain, so a quantifier ranging over the one is not ranging over the other.

The first-order predicate calculus also begins with symbols, and its base level holds three groups rather than two. The fixed group gains the quantifiers, ∀ (for all) and ∃ (there exists), alongside the connectives and parentheses already in it. The second group holds the variables an interpretation binds, and there are three kinds of them. A predicate symbol is a variable to be bound to a predicate, and it carries a fixed number of argument places, so that the predicate bound to it is one of that many arguments; its representations are commonly F, G, and R. A name is a variable to be bound to one member of the domain; its representations are commonly a, b, and c. A function symbol is a variable to be bound to a function carrying some fixed number of domain members to one domain member, and it carries that many argument places; its representations are commonly f, g, and s.The capitals are the traditional letters for predicate symbols, and are kept so that a reader can find the literature. The third group is new, and holds the variables a quantifier is able to claim. This calculus has one kind, the domain variable, whose representations are commonly x, y, and z. The proposition symbol is gone, having no work left to do: a predicate symbol given its arguments occupies the place where a proposition once stood.

-

A function applied to domain members yields another domain member, so the expressions that mark out a member of the domain have to be settled before the formulas can be. A term is a domain variable, or a name, or a function symbol of n places applied to n terms, and nothing else is a term. A term marks out a member of the domain and carries no truth value of its own. So x, a, and f(s(a), x) are terms.The word is used elsewhere in this book in its ordinary sense, for one of the parts of a compound expression, as when the two conjuncts of a set-defining condition are called its terms in chapter . Where the calculus is under discussion, the definition given here is the one intended.

+

A function applied to domain members yields another domain member, so the expressions that mark out a member of the domain have to be settled before the formulas can be. A term is a domain variable, or a name, or a function symbol of n places applied to n terms, and nothing else is a term. A term marks out a member of the domain and carries no truth value of its own. So x, a, and f(s(a), x) are terms.The word is used elsewhere in this book in its ordinary sense, for one of the parts of a compound expression, as when the two conjuncts of a set-defining condition are called its terms in chapter . Where the calculus is under discussion, the definition given here is the one intended.

@@ -242,7 +245,7 @@

A formula in which no variable appears free, also called a sentence, makes an outright claim once its predicate symbols, names, and function symbols are bound. A formula with a free appearance holds or fails according to what is bound to that appearance, so its truth value varies where the other's does not. So ∀x ∃y \, R(x, y) is one and ∃y \, R(x, y) is not. The distinction has no work to do in the propositional calculus, which holds no quantifier and so no free appearances.

-

An interpretation of a first-order formula supplies a domain, which holds at least one member.Standard first-order logic does not admit the empty domain, and the reason is visible in the formulas. Over an empty domain ∀x \, F(x) would hold and ∃x \, F(x) would fail, so (∀x \, F(x) → ∃x \, F(x)) would not be valid; it is counted a validity of this calculus, and admitting the empty domain would cost that. It then binds, to each variable of the formula, a value of the kind that variable marks a place for: a predicate over the domain to each predicate symbol, of the matching number of arguments; a member of the domain to each name; a function over the domain to each function symbol; and a member of the domain to each free appearance of a domain variable, passing over the bound appearances, which the quantifier has already claimed.The notation is not settled across the sources surveyed in this book. Hilbert and Ackermann write (x) for the universal quantifier and (Ex) for the existential, and they mark negation with an overbar rather than with ¬. A reader going to their book should be prepared for this. Take the Peano Numbers as the domain and bind < to R: the formula ∀x ∃y \, R(x, y) then states that every Peano Number has a larger one, and under that interpretation it holds. Every appearance in it is claimed by a quantifier, so the only things the interpretation had to give were the domain and the predicate.

+

An interpretation of a first-order formula supplies a domain, which holds at least one member.Standard first-order logic does not admit the empty domain, and the reason is visible in the formulas. Over an empty domain ∀x \, F(x) would hold and ∃x \, F(x) would fail, so (∀x \, F(x) → ∃x \, F(x)) would not be valid; it is counted a validity of this calculus, and admitting the empty domain would cost that. It then binds, to each variable of the formula, a value of the kind that variable marks a place for: a predicate over the domain to each predicate symbol, of the matching number of arguments; a member of the domain to each name; a function over the domain to each function symbol; and a member of the domain to each free appearance of a domain variable, passing over the bound appearances, which the quantifier has already claimed.The notation is not settled across the sources surveyed in this book. Hilbert and Ackermann write (x) for the universal quantifier and (Ex) for the existential, and they mark negation with an overbar rather than with ¬. A reader going to their book should be prepared for this. Take the Peano Numbers as the domain and bind < to R: the formula ∀x ∃y \, R(x, y) then states that every Peano Number has a larger one, and under that interpretation it holds. Every appearance in it is claimed by a quantifier, so the only things the interpretation had to give were the domain and the predicate.

The same three levels carry the first-order calculus. What a quantifier claims is a fact about the formula, so it is stated at level 1.

@@ -271,7 +274,7 @@ List . The first order predicate logic stack - + Second-order predicate calculus

In the first-order calculus a quantifier claims a domain variable and nothing else. Each predicate symbol is bound by an interpretation, so a person supplies a particular predicate for F and asks what follows, and no formula of that calculus ranges over the predicates themselves. The second-order predicate calculus lifts that restriction by admitting a second kind of claimable variable, the predicate variable, which carries a fixed number of argument places. The two fates are as before, and now apply to this second kind of symbol as well. In ∀F \, Φ the quantifier has claimed F, so no interpretation binds a predicate to it, and the quantifier runs it over the properties of the domain in the same way that ∀x runs a domain variable over the domain itself.

@@ -280,7 +283,7 @@

∀F \, \big( (F(0) ∧ ∀x \, (F(x) → F(s(x)))) → ∀x \, F(x) \big)

-

where 0 is a name marking the place of zero and s is a function symbol of one place marking the place of the successor function, both of which the formation rules admit within terms. The outermost quantifier has claimed the predicate variable, so the axiom states that any property holding of zero and carried from each Peano Number to its successor holds of every Peano Number.

+

where 0 is a name marking the place of zero and s is a function symbol of one place marking the place of the successor function, both of which the formation rules admit within terms. The outermost quantifier has claimed the predicate variable, so the axiom states that any property holding of zero and carried from each Peano Number to its successor holds of every Peano Number.

One cell of the abstraction stack changes, and it is the cell at level 0.

@@ -313,18 +316,19 @@ - - + More logic terminology

A formula that holds under every interpretation is valid, and in the propositional calculus such a formula is also called a tautology. A formula that holds under at least one interpretation is satisfiable. So ((p ∧ p) ↔ p) is valid, (p ∧ q) is satisfiable and not valid, and (p ∧ ¬p) is neither. The two are duals: a formula is valid exactly when its negation is unsatisfiable.

Say a formula of the propositional calculus holds n distinct proposition symbols. An interpretation binds a proposition to each of them, and there is no counting the propositions, but the calculus reads nothing from a proposition except its truth value. What the formula answers to is therefore the induced binding of a truth value to each proposition symbol, and of those there are exactly 2^n. A truth table is an enumeration of them, one per row.

+

The Entscheidungsproblem asks for a mechanical procedure that decides, in finitely many steps, whether a given formula is valid. Enumerating the 2^n rows of a truth table is such a procedure for the propositional calculus. For the first-order calculus an interpretation selects a domain of any size whatever, so there is no finite set of rows to enumerate. Chapter gives the history of the problem and where the search for a solution in the first order predicate calculus lead.Hilbert and Ackermann review the tabulation procedure for the propositional calculus in the first chapter of the 1928 book, before raising the same question for the first-order calculus. Their two formulations of the problem are distinguished by domains: the first asks for which domains of individuals a given expression is valid, and the second asks only whether it is valid for all of them.

+

A derivation is a finite arrangement of formulas built from a stated collection of axioms by stated rules, ending at the formula being derived. Where validity asks what holds under every interpretation, derivation asks what can be reached by rearranging marks, and it consults no interpretation at all. Each is written with a symbol of its own, the double turnstile and the turnstile.

- + Double turnstile. Φ holds under every interpretation. Turnstile. A derivation of Φ exists from the stated axioms and rules. @@ -334,36 +338,8 @@

A collection of axioms and rules is sound when everything it derives is valid, so ⊢ never outruns ⊨, and complete when everything valid is derivable, so ⊨ never outruns ⊢.The turnstile is reused later in this book, subscripted with a machine, for the relation between one instantaneous description of a Turing Machine and the next. The subscript keeps the two apart on the page. A calculus together with a collection of axioms is a theory. Completeness is a property of the axioms and rules relative to the validities of a calculus, and is not the same question as whether a theory settles every statement it can express.

-

The Entscheidungsproblem asks for a mechanical procedure that decides, in finitely many steps, whether a given formula is valid. Enumerating the 2^n rows of a truth table is such a procedure for the propositional calculus. For the first-order calculus an interpretation selects a domain of any size whatever, so there is no finite set of rows to enumerate. Chapter gives the history of the problem and its answer.Hilbert and Ackermann review the tabulation procedure for the propositional calculus in the first chapter of the 1928 book, before raising the same question for the first-order calculus. Their two formulations of the problem are distinguished by domains: the first asks for which domains of individuals a given expression is valid, and the second asks only whether it is valid for all of them.

- -

Finally, the word order counts something different in each of the two places this book uses it, and the two scales are independent of each other. In the predicate calculus, the order counts what a quantifier runs over: a domain member at the first order, and a property of domain members at the second. In the orders of analysis set out in section , the order counts the depth of machines examining machines: running a machine is the first order, examining a machine's definition is the second, and examining an examiner is the third. A second-order analysis of a machine that computes over the first-order predicate calculus is an ordinary thing, and nothing about it is second-order logic. Where a later chapter of this book speaks of second-order arithmetic, it is the orders of analysis that are meant. The same warning applies to metamathematics: a statement about a first-order system is made in the metalanguage, and that alone does not make it a second-order statement.

- - - - - - More logic terminology - -

A formula that holds under every interpretation is valid, and in the propositional calculus such a formula is also called a tautology. A formula that holds under at least one interpretation is satisfiable. So ((p ∧ p) ↔ p) is valid, (p ∧ q) is satisfiable and not valid, and (p ∧ ¬p) is neither. The two are duals: a formula is valid exactly when its negation is unsatisfiable.

- -

Say a formula of the propositional calculus holds n distinct proposition symbols. An interpretation binds a proposition to each of them, and there is no counting the propositions, but the calculus reads nothing from a proposition except its truth value. What the formula answers to is therefore the induced binding of a truth value to each proposition symbol, and of those there are exactly 2^n. A truth table is an enumeration of them, one per row.

- -

A derivation is a finite arrangement of formulas built from a stated collection of axioms by stated rules, ending at the formula being derived. Where validity asks what holds under every interpretation, derivation asks what can be reached by rearranging marks, and it consults no interpretation at all. The two are written as follows.

- - - - - Φ holds under every interpretation. - A derivation of Φ exists from the stated axioms and rules. - - List . The two assessments of a formula - - -

A collection of axioms and rules is sound when everything it derives is valid, so ⊢ never outruns ⊨, and complete when everything valid is derivable, so ⊨ never outruns ⊢.The turnstile ⊢ is reused later in this book, subscripted with a machine, for the relation between one instantaneous description of a Turing Machine and the next. The subscript keeps the two apart on the page. A calculus together with a collection of axioms is a theory. Completeness is a property of the axioms and rules relative to the validities of a calculus, and is not the same question as whether a theory settles every statement it can express.

-

The Entscheidungsproblem asks for a mechanical procedure that decides, in finitely many steps, whether a given formula is valid. Enumerating the 2^n rows of a truth table is such a procedure for the propositional calculus. For the first-order calculus an interpretation selects a domain of any size whatever, so there is no finite set of rows to enumerate. Chapter gives the history of the problem and its answer.Hilbert and Ackermann review the tabulation procedure for the propositional calculus in the first chapter of the 1928 book, before raising the same question for the first-order calculus. Their two formulations of the problem are distinguished by domains: the first asks for which domains of individuals a given expression is valid, and the second asks only whether it is valid for all of them.

- -

Finally, the word order counts something different in each of the two places this book uses it, and the two scales are independent of each other. In the predicate calculus, the order counts what a quantifier runs over: a domain member at the first order, and a property of domain members at the second. In the orders of analysis set out in section , the order counts the depth of machines examining machines: running a machine is the first order, examining a machine's definition is the second, and examining an examiner is the third. A second-order analysis of a machine that computes over the first-order predicate calculus is an ordinary thing, and nothing about it is second-order logic. Where a later chapter of this book speaks of second-order arithmetic, it is the orders of analysis that are meant. The same warning applies to metamathematics: a statement about a first-order system is made in the metalanguage, and that alone does not make it a second-order statement.

+

Finally, the word order counts something different in each of the two places this book uses it, and the two scales are independent of each other. In the predicate calculus, the order counts what a quantifier runs over: a domain member at the first order, and a property of domain members at the second. In the orders of analysis set out in section , the order counts the depth of machines examining machines: running a machine is the first order, examining a machine's definition is the second, and examining an examiner is the third. A second-order analysis of a machine that computes over the first-order predicate calculus is an ordinary thing, and nothing about it is second-order logic. Where a later chapter of this book speaks of second-order arithmetic, it is the orders of analysis that are meant. The same warning applies to metamathematics: a statement about a first-order system is made in the metalanguage, and that alone does not make it a second-order statement.

 @@ -372,7 +348,7 @@ - + Preface

The IEEE Std 754 floating-point standard equips the numerical analyst with the tools to design platform independent algorithms with predictable numerical behavior. Though the principal founder of the standard did commit one sin. He allowed for the expanded precision of the intermediate calculations on the Intel 8087 as a matter of backwards compatibility. He apparently succumbed to that final temptation because he had been part of that project. Consequently, the standard does not provide universal platform independence.

@@ -415,7 +391,7 @@ - + Introduction

Kleene's Introduction to Metamathematics opens with, "A flock of four sheep and a grove of four trees are related to each other in a way in which neither is related to a pile of three stones or a grove of seven trees. ... Without counting the sheep or the trees, one can pair them with each other, for example by tethering the sheep to the trees, so that each sheep and each tree belongs to exactly one of the pairs."Stephen Cole Kleene, Introduction to Metamathematics (Amsterdam: North-Holland, 1952), 3.

@@ -443,7 +419,7 @@ - + The search that led to the Turing Machine

@@ -480,7 +456,7 @@

- 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 . + 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 .

@@ -549,7 +525,7 @@ - + On Turing and Babbage

@@ -595,15 +571,15 @@ - + The conditions on a Natural machine

- The Computational Naturalism thesis holds that mathematics is a taxonomy of machine observations. This sets some conditions. For a machine to be observed, it must be possible to realize it. For observations of the machine to be relevant, its program must be able to encompass any statement in mathematics, being a second condition, and execution must be faithful to the program, being a third condition. The third condition will be met if said observable machine is a computation theoretic inconsequential variation of the Turing Machine. This property is formally defined in chapter ; informally it means that the observed machine gives the same computation theoretic results as a Turing Machine. This argument builds on the work already done with Turing Machines, and it establishes that said programs are executed faithfully to their meaning. + The Computational Naturalism thesis holds that mathematics is a taxonomy of machine observations. This sets some conditions. For a machine to be observed, it must be possible to realize it. For observations of the machine to be relevant, its program must be able to encompass any statement in mathematics, being a second condition, and execution must be faithful to the program, being a third condition. The third condition will be met if said observable machine is a computation theoretic inconsequential variation of the Turing Machine. This property is formally defined in chapter ; informally it means that the observed machine gives the same computation theoretic results as a Turing Machine. This argument builds on the work already done with Turing Machines, and it establishes that said programs are executed faithfully to their meaning.

- The Turing Machine itself fails the first condition. It cannot be built, so the machine that started the Naturalism thesis cannot carry the thesis. Some other machine has to, and satisfying the third condition is what makes the substitution of the new machine valid. A realizable machine that is not a computation theoretic inconsequential variation of the Turing Machine is merely some other machine, and a catalog of observations of it is a catalog of nothing in particular. The obvious candidate is the computer already sitting on the desk, which descends from the concrete machine Babbage drew rather than from the paper one Turing described. It is realizable by construction, it is the machine people actually own and run, and were it to satisfy the third condition the thesis would be finished here, with no proposal to make and no book to write. It does not satisfy it. Establishing that, and locating precisely where it fails, is in part the business of this book. A machine that does satisfy all three conditions is the RT Machine of chapter . + The Turing Machine itself fails the first condition. It cannot be built, so the machine that started the Naturalism thesis cannot carry the thesis. Some other machine has to, and satisfying the third condition is what makes the substitution of the new machine valid. A realizable machine that is not a computation theoretic inconsequential variation of the Turing Machine is merely some other machine, and a catalog of observations of it is a catalog of nothing in particular. The obvious candidate is the computer already sitting on the desk, which descends from the concrete machine Babbage drew rather than from the paper one Turing described. It is realizable by construction, it is the machine people actually own and run, and were it to satisfy the third condition the thesis would be finished here, with no proposal to make and no book to write. It does not satisfy it. Establishing that, and locating precisely where it fails, is in part the business of this book. A machine that does satisfy all three conditions is the RT Machine of chapter .

@@ -623,7 +599,7 @@

- The problem with the controller is more nuanced. The head of a Turing Machine must read and react at every step, and the only place a controller has to hold what it has seen is a branch in its own control path. So the Turing Machine uses its controller as memory. This is treated in detail in section , where a machine that reverses a string is analyzed and the consequence is proven: the number of states and arcs required grows exponentially with the width of a machine word, and for a word of any practical size the controller cannot be built at all. A machine room operator can mount another reel of tape. Nobody can mount a larger controller, because the controller is fixed at the start. The tape's limit can be handed outside the machine and dealt with there, as we have just seen. The controller's limit is sealed inside the model, where nothing can reach it. + The problem with the controller is more nuanced. The head of a Turing Machine must read and react at every step, and the only place a controller has to hold what it has seen is a branch in its own control path. So the Turing Machine uses its controller as memory. This is treated in detail in section , where a machine that reverses a string is analyzed and the consequence is proven: the number of states and arcs required grows exponentially with the width of a machine word, and for a word of any practical size the controller cannot be built at all. A machine room operator can mount another reel of tape. Nobody can mount a larger controller, because the controller is fixed at the start. The tape's limit can be handed outside the machine and dealt with there, as we have just seen. The controller's limit is sealed inside the model, where nothing can reach it.

@@ -643,7 +619,7 @@

- The remainder is delivered by construction rather than by thesis, and it occupies much of this book. A tape cell is defined as a location in physical memory in section , and a symbol in computational terms in section . Logic follows from relay switch logic, as Shannon and others have already established. On top of logic sits the Peano Machine, a counter, which then serves as the definition of Peano Numbers. Where Gödel reduced logic to Peano Numbers, we run the other way and expand logic out of them. An axiomatic proof becomes a decider assembled from subroutine calls to the axioms. Frege's set theory becomes the analysis of a logic program against an enumeration of inputs. Russell's paradox becomes a machine that can be analyzed in the second order though it will never halt in the first, which requires the orders of analysis set out in section . The whole is drawn together in chapter , where the claim is that every statement a mathematician has ever made can be restated in this language. + The remainder is delivered by construction rather than by thesis, and it occupies much of this book. A tape cell is defined as a location in physical memory in section , and a symbol in computational terms in section . Logic follows from relay switch logic, as Shannon and others have already established. On top of logic sits the Peano Machine, a counter, which then serves as the definition of Peano Numbers. Where Gödel reduced logic to Peano Numbers, we run the other way and expand logic out of them. An axiomatic proof becomes a decider assembled from subroutine calls to the axioms. Frege's set theory becomes the analysis of a logic program against an enumeration of inputs. Russell's paradox becomes a machine that can be analyzed in the second order though it will never halt in the first, which requires the orders of analysis set out in section . The whole is drawn together in chapter , where the claim is that every statement a mathematician has ever made can be restated in this language.

@@ -651,15 +627,15 @@

- There is a remedy, and it occupies the chapters that follow. We will transform the Turing Machine into a modern architecture in a stepwise fashion, while ensuring that at each step the modifications are inconsequential to computation theoretic existence proofs and complexity class results. The transformation does not run in one direction only. On the Turing Machine side, the controller has to stop being used as memory. On the modern side, the fixed widths an architecture stipulates, those of an address and of an Integer, are what have to give way. The two meet in the middle, and the machine we arrive at is less strange than that might suggest. It separates the control path from the data path; it holds an instruction table; and it has a small register file. It looks modern. The differences from what we currently build are real but few, and the point of the exercise is that we could build it. That machine, the RT Machine of chapter , satisfies the first condition by being buildable and the third by the manner of its construction, and it inherits the second from the Turing Machine it was transformed out of. Neither the Turing Machine nor the computer on the desk is a Natural manifestation of mathematics. The RT Machine, standing between them, is. + There is a remedy, and it occupies the chapters that follow. We will transform the Turing Machine into a modern architecture in a stepwise fashion, while ensuring that at each step the modifications are inconsequential to computation theoretic existence proofs and complexity class results. The transformation does not run in one direction only. On the Turing Machine side, the controller has to stop being used as memory. On the modern side, the fixed widths an architecture stipulates, those of an address and of an Integer, are what have to give way. The two meet in the middle, and the machine we arrive at is less strange than that might suggest. It separates the control path from the data path; it holds an instruction table; and it has a small register file. It looks modern. The differences from what we currently build are real but few, and the point of the exercise is that we could build it. That machine, the RT Machine of chapter , satisfies the first condition by being buildable and the third by the manner of its construction, and it inherits the second from the Turing Machine it was transformed out of. Neither the Turing Machine nor the computer on the desk is a Natural manifestation of mathematics. The RT Machine, standing between them, is.

- + The computer design abstraction stack - + The six levels

@@ -693,7 +669,7 @@

- It is not a requirement of a computer organization, nor of an architecture, that it be capable of physical realization. The abstract Turing Machine organization developed in chapter serves as an example. Instead, an abstract organization can serve other purposes, in this case as a stepping stone to another organization that can be realized. + It is not a requirement of a computer organization, nor of an architecture, that it be capable of physical realization. The abstract Turing Machine organization developed in chapter serves as an example. Instead, an abstract organization can serve other purposes, in this case as a stepping stone to another organization that can be realized.

@@ -710,7 +686,7 @@ - + The levels are not independent

@@ -735,7 +711,7 @@ - + Where the Turing Machine fits in

@@ -762,7 +738,7 @@ - + Computation theoretic consequentiality

@@ -773,7 +749,7 @@ Suppose a transform applied to machine m_i produces machine m_{i.1}. Suppose further that this latter machine gets the same results for the same computational inputs, and that any computation theory analysis applied to m_{i.1} yields the same existence and big O results as it would when applied to m_i. Then we say that the transform is computation theoretic inconsequential. Otherwise, the transformation is said to be computation theoretic consequential. The remainder of this chapter defines these terms more precisely.

- + Orders of analysis

@@ -814,7 +790,7 @@

- 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. + 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.

@@ -835,7 +811,7 @@ - + Definition of the same results transform property

@@ -916,7 +892,7 @@ - + Definition of the computation theoretic consequential and inconsequential transform property

@@ -987,7 +963,7 @@ - + The conventional Turing Machine

This definition comes from Hopcroft and Ullman's book with minor terminology changes to make it flow into the text here John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (Reading: Addison-Wesley, 1979).. @@ -1047,7 +1023,7 @@

So first the tape is X_1 X_2 ⋯ X_{i-1} X_i X_{i+1} ⋯ X_n, with the head over X_i, and in state q. Then after a step of the machine, the tape is X_1 X_2 ⋯ X_{i-1} Y X_{i+1} ⋯ X_n, with the head over X_{i-1}, and in state p. Thus X_i was overwritten with Y, and the head stepped left.

- + The reverse machine example

Here is the programmed controller for a Turing Machine that reverses a binary string. Although by definition each state transition matches exactly one value under the head, as a practical matter, disjunctive selection is allowed via a comma list. A conjunctive phrasing for a state transition proposition would require stringing intermediate states in series.

@@ -1188,7 +1164,7 @@ - + Analysis of the reverse machine

The total number of steps for reversing an n symbol string:

@@ -1280,7 +1256,7 @@ - + The memory of emptiness

Turing described a clerk writing symbols into squares, with the option to erase them. He states, "In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol."Alan M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936): 231. So initially Turing's original article uses blank to mean no symbol. However, later Turing says, "We also give numbers to the symbols ... in particular, blank = S₀ ." ibid: 239..

@@ -1367,12 +1343,12 @@ - + The computation theoretic RT Machine

This chapter presents a modified computation theoretic Turing Machine with three structural additions. First, it separates control flow from data flow, ensuring that payload symbols do not needlessly expand the control state machine. Second, it unifies the control and data symbol sets into a single alphabet to natively support explicit communications protocols even in the presence of recursion and self-recursion. Finally, it implements a cascading next-state evaluation hierarchy, permitting the programmer to formally define and handle meta-symbols while also making it more convenient to program communication protocols.

- + The unspecified meta-symbol

In the first edition of this book, I introduced a "read-only after write" rule while working towards an architectural Turing Machine because conventional computer architectures do not maintain a concept of empty memory. The approach described in this section integrates the "read-only after write" into a computation theoretic machine by designing in the concept of being unspecified, which then displaces the concept of a cell being empty.

@@ -1404,7 +1380,7 @@ - + The modifications

The specific architectural modifications are as follows:

@@ -1457,7 +1433,7 @@ - + The RT Machine fixed part @@ -1521,7 +1497,7 @@ - + Machine variables @@ -1541,7 +1517,7 @@ - + Programmable part @@ -1647,7 +1623,7 @@ - + The RT Machine definition in total @@ -1724,7 +1700,7 @@ - + Computation theoretic RT Machine executor

Computer was at one time a job title. Turing described a clerk following directions to cause his machine to go, thus implying that mathematicians are mere automata chained to following the procedures they derive. So then an executor can be a person, perhaps a student who is studying the computation theoretic machine, and has a homework assignment of showing what it does.

@@ -1733,7 +1709,7 @@

This description assumes support is programmed in for the first-order unspecified symbol.

- + Initialization stage

Before the first cycle begins, a tape is selected and mounted. The read/write head is positioned over the leftmost tape cell. The machine variables are initialized as follows:

@@ -1748,10 +1724,10 @@ - + Programmed control stage - + Phase 1: Instruction issue and execution @@ -1765,14 +1741,14 @@ - + Phase 2: The state transition

Following the completion of the instruction, the programmed controller evaluates the next-state by cascading through the ordered sequence of transition rules Δ = [Δ_0 \mid Δ_1 \mid Δ_2 \mid Δ_3]. The evaluation follows this hierarchy, stopping and branching at the first valid match. Upon not finding a next-state transition, the machine hangs.

 - + Halting stage

If, after the state transition phase completes, the current state is a member of H, the machine halts. Otherwise, the execution continues from the programmed control stage.

@@ -1780,7 +1756,7 @@ - + The RT Machine string reverse

Because the RT Machine separates the data path from the control path, it is possible to reverse a string without inspecting the payload. The programmed controller only needs to recognize the structural boundaries of the data protocol. When a payload symbol is encountered, the controller executes a read(d) instruction, placing the value into the data register, which is not examined for decision-making purposes. When a value is used to base a decision upon, the controller executes a read(s), placing the value into the status register. Because instructions are bound to states rather than transitions, reading and stepping are distinct states. This combination of features results in a controller that has threads of serialized execution.

@@ -1941,7 +1917,7 @@ - + Analysis of the RT reverse machine

The number of states is constant at 24 independent of how much data is to be reversed. No arc refers to a payload value.

@@ -2023,7 +1999,7 @@ - + Two-headed reverse string example

The reverse string machine spends a lot of time shuttling the head between two context areas: one for the original string, and one for the resulting reversed string. This suggests that a two-head version would be faster. The following is the two-head state machine definition:

@@ -2144,7 +2120,7 @@ - + Analysis of the two-headed reverse string machine

The number of states has dropped from 24 to 18, while the speed increase is dramatic, with the former quadratic performance becoming linear performance. The total number of steps for reversing an n symbol string using a two-head RT architecture:

@@ -2220,7 +2196,7 @@ - + The RT Machine design @@ -2232,9 +2208,9 @@ Figure . A Turing Machine -

The prior chapter on the computation theoretic RT Machine, chapter , serves as the architectural template, with only a few modifications. The architecture requires explicit data rather than accepting meta-symbols like 'unspecified' as presumed initial values 'by definition'. Actual values are transacted. Now that data and control have been separated, the controller is practical to implement, and even more so because it was defined in terms of tables that can be built in hardware. As the read status instruction returns the cell type, it will in its current form be able to return 'rightmost', so the right end of the tape can be detected. In order to extend the tape, the machine will stop and ask the operator to mount a new reel. This could be signaled when the user attempts to step right of rightmost, either by a panel light that illuminates upon the machine finding a rightmost status, or by the program printing a message on the console teletype. As this is a constant-time operation, it is computation theoretic inconsequential.

+

The prior chapter on the computation theoretic RT Machine, chapter , serves as the architectural template, with only a few modifications. The architecture requires explicit data rather than accepting meta-symbols like 'unspecified' as presumed initial values 'by definition'. Actual values are transacted. Now that data and control have been separated, the controller is practical to implement, and even more so because it was defined in terms of tables that can be built in hardware. As the read status instruction returns the cell type, it will in its current form be able to return 'rightmost', so the right end of the tape can be detected. In order to extend the tape, the machine will stop and ask the operator to mount a new reel. This could be signaled when the user attempts to step right of rightmost, either by a panel light that illuminates upon the machine finding a rightmost status, or by the program printing a message on the console teletype. As this is a constant-time operation, it is computation theoretic inconsequential.

-

Because a Turing Machine can only reach another cell further out on the tape by stepping to it, space complexity and time complexity are related. A program that runs for ten steps can consume at most ten cells of tape. However, if that program merely bounces between two cells, it will require less space, precisely two cells. As another example, a program that counts the number of characters on its input tape using Hindu-Arabic notation will execute in asymptotically linear time, as demonstrated in section , which analyses the increment operation. Its working footprint, however, will be logarithmic in space complexity, because that is how fast an Hindu-Arabic representation grows with a count.

+

Because a Turing Machine can only reach another cell further out on the tape by stepping to it, space complexity and time complexity are related. A program that runs for ten steps can consume at most ten cells of tape. However, if that program merely bounces between two cells, it will require less space, precisely two cells. As another example, a program that counts the number of characters on its input tape using Hindu-Arabic notation will execute in asymptotically linear time, as demonstrated in section , which analyses the increment operation. Its working footprint, however, will be logarithmic in space complexity, because that is how fast an Hindu-Arabic representation grows with a count.

If a program executed at the speed of a human operator, the operator would likely abandon the process before it finished. This highlights a necessary attribute of good software: utility. It also exposes a limitation of pure computation theory, which abstracts away physical time. Nevertheless, formal analysis remains a necessity. Consider an exponential-time program processing worst-case operands: its execution time explodes relative to input length, rapidly exceeding the age of the universe. In such extremes, empirical wall-clock measurement becomes superfluous. Computation theory classifies a program's behavior, which establishes structural implications for wall-clock time, rather than calculating absolute durations.

@@ -2248,7 +2224,7 @@

Suppose a controller is not analyzed to determine its computation theoretic complexity, or even tested against worst-case inputs, but is instead run with random or everyday input to gather performance measurements. This process is called profiling. After many runs, a programmer might surmise the behavioral limits of the program. However, many programs are neither linear systems nor smooth functions. With a different set of inputs than those used for profiling, perhaps even values adjacent to prior inputs, the program behavior can shift drastically. Consider the Pentium divider. It did not matter how many millions of times the result was accurate; the fact remains that customers later found inputs that yielded wildly inaccurate results. Only by elevating the analysis to the structural logic of the code can such an eventuality from an erroneous program be categorically ruled out. This is why the K5 transcendental function development project included a proof writing phase; see Thomas Walker Lynch, A. Ahmed, M. Schulte, T. Callaway, and R. Tisdale, "The K5 Transcendental Functions," Proceedings of the 12th IEEE Symposium on Computer Arithmetic, 1995. DOI: 10.1109/ARITH.1995.465368.

- + Head Unit, HU

An HU contains a head and a local controller. The local controller supports these instructions:

@@ -2263,7 +2239,7 @@ List . The instructions supported by the head unit controller -

On this model of machine, the HU status is identical to the indicated cell's type. The cell type is not read from the tape; rather, it is derived from the head's physical relationship to the ends of the tape. With a physical tape drive, an unused leader and trailer are required to prevent the tape from departing from the reels, a condition difficult to reverse. Therefore, the format, or physical, markers will be on the ends of the usable portion of the tape, rather than on the physical end of the tape. Consequently, the HU works in conjunction with the TTU to derive the status. (The tape transport unit, the TTU, is discussed in the next section, section .) As established in section , cell types are:

+

On this model of machine, the HU status is identical to the indicated cell's type. The cell type is not read from the tape; rather, it is derived from the head's physical relationship to the ends of the tape. With a physical tape drive, an unused leader and trailer are required to prevent the tape from departing from the reels, a condition difficult to reverse. Therefore, the format, or physical, markers will be on the ends of the usable portion of the tape, rather than on the physical end of the tape. Consequently, the HU works in conjunction with the TTU to derive the status. (The tape transport unit, the TTU, is discussed in the next section, section .) As established in section , cell types are:

@@ -2284,7 +2260,7 @@ - + Tape transport unit, TTU

The TTU is the component where tapes are mounted and unmounted, and where read/write head units are installed. When multiple HUs are plugged in, the controller passes control among them so it appears that heads never collide. The TTU controller has these components: @@ -2319,7 +2295,7 @@ - + The customer programmed control unit, CPCU

The controller is programmed via patch panels. The panels would look something like what is shown in the following ASCII art blocks. Note that ● indicates an illuminated indicator light, whereas ○ is not illuminated. [/] represents an open toggle switch, while [—] is a closed one. {*} is a pushed button, while { } is a button that is not pushed. ( ) represents a hole for a banana plug. Each patch cord has a banana plug on each end. Plugging a patch cord between separate panels will void the warranty ;-).

@@ -2416,7 +2392,7 @@ - + The machine block diagram @@ -2474,7 +2450,7 @@ List . The units and panels the machine is assembled from -

As described in chapter , which is being used as the architectural template, the executor guides the machine through the initialization, programmed control, and halting stages of execution. The Executor contains the power, reset, and clock logic. It has two modes of execution: the run mode in which the clock runs free, and the single-step mode, in which clock pulses are sent with the push of a button. It also holds the halt state switch bank, and is ready to stop the clock when a halt state is reached. When in the programmed control stage, most of the active control comes from the CPCU.

+

As described in chapter , which is being used as the architectural template, the executor guides the machine through the initialization, programmed control, and halting stages of execution. The Executor contains the power, reset, and clock logic. It has two modes of execution: the run mode in which the clock runs free, and the single-step mode, in which clock pulses are sent with the push of a button. It also holds the halt state switch bank, and is ready to stop the clock when a halt state is reached. When in the programmed control stage, most of the active control comes from the CPCU.

The CPCU contains the current state register q, the Next-State Table, and the Instruction Table.

@@ -2492,7 +2468,7 @@ The tape transport unit, TTU, handles mounting, unmounting, reading, writing, and moving the tape. In this volume, we treat head motion in a relative sense, recognizing that a physical TTU moves the magnetic tape beneath a stationary head rather than displacing the head across the tape. Our architecture allows a system to incorporate multiple TTU modules, each containing its own read buffer, status buffer, and head assembly. Tapes can be dynamically mounted, unmounted, shelved, and transferred between any TTU on the same machine or across distinct systems.

- + Description of a read('s') instruction

The current state register, q, samples and holds on the rising edge of the clock. This then provides a stable state signal to the control panel next-state matrix columns for an entire cycle. The status register, s, is the phase inverse; when enabled it samples on the falling edge of the clock and holds for an entire cycle.

@@ -2516,7 +2492,86 @@ - + + Mathematics as a machine notation + +

In March of 1826 Babbage read a paper to the Royal Society describing a language he had invented for machines.Charles Babbage, "On a Method of Expressing by Signs the Action of Machinery", Philosophical Transactions of the Royal Society of London 116 (1826): 250−265, read 16 March 1826. He called it the mechanical notation. It gave each part of a machine a sign, classified that part as fixed or as moveable, recorded what drove it and what it drove in turn, and set down when each motion occurred relative to the others. Given the notation for a machine, a person could say what that machine would do, and could find any part at any moment and state whether it was moving or at rest.

+ +

The engine Babbage wrote about was never built. He said plainly that without the notation he could not have invented the Analytical Engine, and he counted the notation among his best inventions.Charles Babbage, Passages from the Life of a Philosopher (London: Longman, Green, 1864), 104, where he adds that he doubts machinery of comparable complexity could be contrived without that language or an equivalent one. On its mature form, comprising labeled drawings, timing diagrams, and logic diagrams, see Anthony Hyman, Charles Babbage: Pioneer of the Computer (Oxford: Oxford University Press, 1982), 58. The signs came first and the metal was to follow. That is what makes the notation worth beginning with. Its sentences say what a machine will do, they were written before any machine did it, and they are answerable to the machine for whether they said right.

+ +

Computational Naturalism holds that mathematics is a language of precisely this kind: a language about what a constructed machine will do. Babbage's notation was about one engine. Mathematics is about machinery in general. That is the whole of the difference between them, a difference of scope and not of kind. The word constructed carries weight, since a language about what an unrealizable machine would do is a language about nothing, which is why the first of the conditions of chapter is that the machine can be built.

+ +

This chapter is where that claim is made good, and it starts where the machine starts, with symbols and the lamps that report them. Chapter gave the words a reader is likely to arrive with, and gave them as they are conventionally used. Nothing here is derived from that chapter. It is a table of translations, offered so that reader and author use words the same way, and it is consulted below only to say which familiar word names the thing the machine has just been seen to do.

+ + + The lamps + +

The machine of chapter carries a row of status lamps on its control panel, and they were drawn there without remark. Recall how they are driven. The alphabet is enumerated so that each of its symbols corresponds to one row of the panel. A head reads a cell, the value arrives in the s register, the status decoder converts that value into a one-hot encoding, and the single asserted line illuminates one row.

+ +

One-hot means one line asserted and no others. It is not a policy the machine follows but a fact about how the decoder is cut: the lines are driven from a complete decode of the register, so exactly one of them is high for any value the register can hold. There is a lamp for each symbol, no lamp for anything else, and never two lamps at once.

+ +

Nor is any judgment exercised anywhere along that path. The objection presents itself early, so it is worth closing early. If a lamp reports a voltage, and voltage is continuous, then somewhere a threshold was chosen and a decision made, and a symbol resting on a decision was imposed by whoever made it. But the machine holds no thresholding device. Take the CMOS inverter. A high input turns the N device hard on and the P device off, and the output is pulled to ground; a low input does the reverse. Through the middle region its gain is far above unity, so an input that wanders toward the middle is driven away from it rather than adjudicated. Noise margins are not decision points. They are the width of the region the gate's own gain repairs. The lamp is not deciding whether to illuminate; it is commanded to, or it is held dark, and no third behavior is available to it.There are devices that do decide, and they are worth naming so as not to be mistaken for the general case. A communications receiver samples a line and hands the sample to a decider. A memory array develops a small differential on its bit lines and hands it to a sense amplifier. Both restore a signal degraded past what gain alone recovers, and both sit at the periphery, on the boundary between the machine and what is not yet digital. That boundary is where symbols enter and leave. It is not what the machine is made of.

+ +

So the lamp is lit if and only if the symbol is present, and the same decoder line does both jobs. A person watching the panel is not reading an instrument that formed an opinion about the machine. He is watching the machine.

+ + + + One report, carried across + +

The machine is in single-step mode, and there are five symbols in its alphabet and so five status lamps. The operator pushes the step button and reports what he saw. What follows is that report, rewritten six times.

+ + + +
    +

  1. I pushed the step button, and the third lamp from the left came on while the others stayed dark.

    +

    The report as spoken. It carries a person, an act, a moment, and a direction of gaze.

    2. + +

  2. Push of the step button: lamp ℓ_2 lit, lamps ℓ_0, ℓ_1, ℓ_3, ℓ_4 dark.

    +

    The lamps have been given names according to the row each occupies. Naming is not yet a claim, and no lamp has moved.

    3. + +

  3. \text{lit}(ℓ_2) holds, and \text{lit}(ℓ_0), \text{lit}(ℓ_1), \text{lit}(ℓ_3), \text{lit}(ℓ_4) fail.

    +

    The word lit has been written in front of what it is said of, and the five lamps have been taken together as what it is said of. A reader who wants the conventional names for these two moves will find them in chapter under predicate and domain. The lamps are unaffected by being named that.

    4. + +

  4. \text{bind}(s, σ_2)

    +

    Lamp ℓ_i is driven by the decoder line for σ_i, and that line is asserted exactly when the s register holds σ_i. So \text{lit}(ℓ_i) and the status symbol being σ_i are one report and not two, and the shorter phrasing has been kept. The substitution was licensed by the wiring, not by the operator.

    5. + +

  5. The operator pushes again. Each push is a separate occasion, and to speak of more than one at a time the occasion is written as an argument: \text{lit}(ℓ_2, c).

    +

    This is where the act and the moment went. The operator, the button, and the afternoon are not discarded; they are what distinguishes one occasion from another. The conventional word for such an occasion is evaluation context.

    6. + +

  6. ∀c \, ∃i \, \big( \text{lit}(ℓ_i, c) ∧ ∀j \, ( \text{lit}(ℓ_j, c) → j = i ) \big)

    +

    Exactly one lamp is lit, whichever push is taken. What licenses the ∀ is the decoder, which asserts one line and no more for any value the register can hold. The operator does not arrive at it by exhausting the pushes.

    7. +
+ List . An operator's report carried into the predicate calculus + + +

The last line is a sentence of the first-order predicate calculus, built by the formation rules and by nothing else. It is also a statement about lamps, true of a machine that was wired before anyone wrote it down, and it would have been true of the machine while it was still a drawing. There is one thing here being described in two notations, the longer of which was abandoned at line 2.

+ + + + Where the generality comes from + +

Read the ladder again looking for the step at which the account left the machine. There is not one. Line 2 names, line 3 puts a word in front of what it is said of, line 4 substitutes one phrase for another on the authority of a wire, line 5 admits there is more than one push, and line 6 says every. A reader who wants to locate the moment at which mathematics took over from engineering will not find it, and that absence is the argument of this chapter.

+ +

Line 6 repays a second look, because a universal claim from a man who has pushed a button a few times looks like an overreach. It would be, if the tally were what licensed it. It is not. The decoder asserts one line and no more, for every value the register is capable of holding, and that is a fact about how the part was cut. The operator could read it off the wiring diagram without pushing the button at all, which is what Babbage did for an engine that had no buttons to push. The generality is in the construction. The notation records it.

+ +

This also answers where the operator went. The final sentence mentions no person and no afternoon, and it does not follow that these were discarded as unreal. They were absorbed into c. Every occasion is a particular push, the quantifier ranges over those pushes and over nothing else, and the generality of the sentence is not achieved by rising above the machine but by declining to write its occasions out one at a time.

+ + + + Reading the ladder downward + +

A ladder can be climbed in either direction. Hand the final sentence to a person who has never seen the machine and ask what would have to be the case for it to hold. He arrives back at a panel on which exactly one lamp lights per step, or at a wiring diagram from which that follows. The sentence carries its own conditions of redemption, and they are conditions on an apparatus.

+ +

That is the thesis, and the chapters ahead are spent making the descent for one mathematical structure after another: the areas and partitions of a tape, the metrics over them, the Peano Numbers, the addresses, and the symbol itself considered more closely than it has been here. In each case the question asked is the one Babbage's signs were built to answer. What machine, and what will it do?

+ +

One detail of his notation is worth carrying forward. The first thing his signs recorded of any part was whether it was fixed or moveable. A reader who has been through chapter will recognize the pair, since the same two words are the conventional ones for sorting symbols by whether what they are bound to holds across every occasion or varies between them. The classification did not travel from mathematics to the machine. It was recorded of gears and levers first.

+ + + + + + + Area and partitioning

@@ -2529,7 +2584,7 @@

A tape partition is a set of areas that completely span a tape. For any partition of a single-ended Turing Machine tape, at least one of the areas will necessarily be infinite.

- + Head partition @@ -2546,7 +2601,7 @@ - + Leftmost/remaining partition @@ -2560,7 +2615,7 @@ - + Active area partition

@@ -2580,12 +2635,12 @@

- A noncomputational tape is one that cannot be initialized by a Turing Machine, but can still be surmised to exist, perhaps in analysis due to its properties. The empty tape is an example. The tape holding the Peano Numbers is another example. For noncomputational tapes that have the property that the active area is open on the right, there is no right empty tail. + A noncomputational tape is one that cannot be initialized by a Turing Machine, but can still be surmised to exist, perhaps in analysis due to its properties. The empty tape is an example. The tape holding the Peano Numbers is another example. For noncomputational tapes that have the property that the active area is open on the right, there is no right empty tail.

- + Area implied partition

@@ -2594,7 +2649,7 @@ - + The impossibility of recognizing an empty tape

@@ -2611,7 +2666,7 @@ - + The impossibility of recognizing the rightmost cell of the active area

@@ -2636,7 +2691,7 @@ - + In-band and out-of-band control

@@ -2653,7 +2708,7 @@ - + Virtual cells

A given finite area that is not sitting on the end of the tape will have a left neighbor area and right neighbor area that are not in the area. If the given area is sitting on the end of the tape there will be no left neighbor area. If the area is open on the right, there will be no right neighbor area.

@@ -2665,7 +2720,7 @@ - + Virtual tape

As established, the Turing Machine head transport returns a distinct left-of-leftmost symbol when stepping left off the end of the tape. The programmed controller, the statement machine, then uses an arc defined specifically for this symbol. It is a distinct symbol that cannot be written to the tape. @@ -2693,7 +2748,7 @@ - + Partitions on a finite virtual tape

@@ -2714,10 +2769,10 @@ - + Metrics - + Address defined area

We defined a tape as having a single feature, that of a leftmost cell, along with a linear neighbor topology. When a tape is mounted it gains a second feature, that of the cell the head is on. The leftmost cell was fixed in place, while any other single cell on the tape can be featured as the cell the head is on. When we introduced areas, we picked up two new features, that of the leftmost cell of the area, and the rightmost cell of the area. Again, those features could coincide with the former features. We noted that the features partitioned a tape thus defining more areas, and more features. @@ -2728,22 +2783,22 @@

- When discussing symbols we noted they could be Peano Numbers, and even went so far as to point out that addresses were symbols, though we had not yet defined them. They are familiar to anyone involved in computing, so again, it did not present a serious problem. Here we have now formalized them. + When discussing symbols we noted they could be Peano Numbers, and even went so far as to point out that addresses were symbols, though we had not yet defined them. They are familiar to anyone involved in computing, so again, it did not present a serious problem. Here we have now formalized them.

So we now have two means for identifying a feature. One means is to state its address, and the other is to put a tape machine head on it.

-

As we noted in section , an area has two distinguishing features, being that it has a leftmost cell, and a rightmost cell. That definition is topological. If we start with the leftmost cell of a tape, we are either already on the leftmost cell of a defined area, or we can step right to find it. At the point of finding it we know this leftmost cell is part of the area, then we are either already on the rightmost cell, or we can continue to step right on cells in the area until we find the rightmost cell in the area. The right neighbor of the rightmost cell in the area, and all cells to that right of that, are excluded from the area. +

As we noted in section , an area has two distinguishing features, being that it has a leftmost cell, and a rightmost cell. That definition is topological. If we start with the leftmost cell of a tape, we are either already on the leftmost cell of a defined area, or we can step right to find it. At the point of finding it we know this leftmost cell is part of the area, then we are either already on the rightmost cell, or we can continue to step right on cells in the area until we find the rightmost cell in the area. The right neighbor of the rightmost cell in the area, and all cells to that right of that, are excluded from the area.

-

With addresses we can now define an area with two addresses, two Peano Numbers, the address of the leftmost cell, and that of the rightmost cell. All Peano Numbers greater than or equal to the address of the leftmost cell, or less than or equal to the address of the rightmost cell, are addresses of cells that are in the area. This feels more satisfactory for most of us, as now we are talking about arithmetic rather than graph topology. Though should the topology of the tape be generalized, this could become limiting. It reminds me of Frege's admonition that perhaps math should be built on top of geometry. +

With addresses we can now define an area with two addresses, two Peano Numbers, the address of the leftmost cell, and that of the rightmost cell. All Peano Numbers greater than or equal to the address of the leftmost cell, or less than or equal to the address of the rightmost cell, are addresses of cells that are in the area. This feels more satisfactory for most of us, as now we are talking about arithmetic rather than graph topology. Though should the topology of the tape be generalized, this could become limiting. It reminds me of Frege's admonition that perhaps math should be built on top of geometry.

- + Distance and extent

The distance between two cells is the absolute difference in their addresses. When we talk about the distance between the leftmost cell of an area and the rightmost cell of an area, we call this number the area's extent.

@@ -2756,7 +2811,7 @@ - + Length

If cells in an area are transacted, the cost of the area is the cost of a cell multiplied by the count of cells. Vincent Atanasoff probably found himself needing to know such a count when ordering capacitors. The count of cells in an area is also known as the area's length. We will use the Greek symbol Ï¡, pronounced as sampi, to refer to the length. The length of an area, the count of its cells, will always be one greater than its extent, Ï¡ = \omega + 1. This symbol makes sense here, as the Greek number system fell short of letters, so the symbol Ï¡ was tacked on to the end of the alphabet, but did not belong to the alphabet. @@ -2767,12 +2822,12 @@ - - Is the cardinality of an open on the right area a Peano Number? + + Is the cardinality of an open on the right area a Peano Number?

So we find an interesting situation with the cardinality of an address space for an area that is open on the right. It goes like this.

- + How cardinality is computed @@ -2787,59 +2842,59 @@ - - Lemma 1, the A machine produces Peano Numbers + + Lemma 1, the A machine produces Peano Numbers -

This follows from its definition; it is literally the increment from the Peano Numbers Machine.

+

This follows from its definition; it is literally the increment from the Peano Numbers Machine.

 - - Lemma 2, cardinality is a Peano Number + + Lemma 2, cardinality is a Peano Number -

Cardinality is produced by repeatedly calling the A machine, and the A machine produces Peano Numbers.

+

Cardinality is produced by repeatedly calling the A machine, and the A machine produces Peano Numbers.

 - + Lemma 3, cardinality is not in the address space

At the end of the second step in the procedure for producing the cardinality, the tape of the A machine held the extent of the address space. Then in step 3, A was called again, thus leaving a number one larger than the extent on its tape. The extent is the largest number in the address space, hence cardinality is larger than all numbers in the address space. Thus cardinality is not in the address space.

 - - Lemma 4, the address space of an open on the right area is identical to the Peano Numbers. + + Lemma 4, the address space of an open on the right area is identical to the Peano Numbers. -

Composing the A machine with an unterminated loop call, where each result is written to a tape with a terminator between entries, results in the same machine as the Peano Numbers Machine.

+

Composing the A machine with an unterminated loop call, where each result is written to a tape with a terminator between entries, results in the same machine as the Peano Numbers Machine.

 - + The apparent contradiction. -

By Lemma 2, cardinality is a Peano Number. By Lemma 3 cardinality is not in the address space. By Lemma 4 the address space is identical to the Peano Numbers.

+

By Lemma 2, cardinality is a Peano Number. By Lemma 3 cardinality is not in the address space. By Lemma 4 the address space is identical to the Peano Numbers.

 - + Resolution -

The resolution lies in the computational reality of Step 2. For an area that is open on the right, the stepping of machine P never halts. Because Step 2 never terminates, Step 3 is never executed. The A machine never runs that final, additional time. Therefore, the cardinality of an open area is never actually produced by the machine. In the language of Computational Naturalism, Lemma 2 is false for an infinite area; the cardinality of an open on the right area is excluded from being a Peano Number because a Peano Number Machine cannot reach it in the first-order.

+

The resolution lies in the computational reality of Step 2. For an area that is open on the right, the stepping of machine P never halts. Because Step 2 never terminates, Step 3 is never executed. The A machine never runs that final, additional time. Therefore, the cardinality of an open area is never actually produced by the machine. In the language of Computational Naturalism, Lemma 2 is false for an infinite area; the cardinality of an open on the right area is excluded from being a Peano Number because a Peano Number Machine cannot reach it in the first-order.

So then can we add a property to cardinality, such that a second-order analysis could use this property to continue downstream analysis? In short we could say that cardinality has no first-order value, but it has a second-order one. This is analogous to inventing a new type of number, analogous to a complex number with a second component. I.e., there is no 'real' solution, but there is an 'imaginary' one. Or analogous to error algebra, where a number value is replaced with a rule on how to handle downstream operations when it is given as an input.

-

Such a value would be a new Turing Machine, one that composes a call to the never halting Peano Number machine followed by an increment operation. It cannot be run, but it perfectly explains the situation to an analyst. Perhaps we name this machine \aleph_0. +

Such a value would be a new Turing Machine, one that composes a call to the never halting Peano Number machine followed by an increment operation. It cannot be run, but it perfectly explains the situation to an analyst. Perhaps we name this machine \aleph_0.

- + What if extent was used instead of cardinality?

- Had extent been used instead of cardinality, we would lack the final increment step in the three step computing procedure. However, step 2 still cannot complete. Rather than a value, the result of the second-order analysis would be a machine that produces ever larger Peano Numbers. We can call this machine \aleph_{-1}. + Had extent been used instead of cardinality, we would lack the final increment step in the three step computing procedure. However, step 2 still cannot complete. Rather than a value, the result of the second-order analysis would be a machine that produces ever larger Peano Numbers. We can call this machine \aleph_{-1}.

@@ -2855,14 +2910,14 @@

- Neither machine can be run. However we can compose the two machines, then simplify the composition. When we do so, the ever larger Peano Number machines annihilate each other, and the increment machine remains. The increment machine can be run, so we end up with an output value. + Neither machine can be run. However we can compose the two machines, then simplify the composition. When we do so, the ever larger Peano Number machines annihilate each other, and the increment machine remains. The increment machine can be run, so we end up with an output value.

- + Size

Consider the case of a partitioned tape. Then consider that we write a gasket, such that we have a higher level Turing Machine that considers each of the areas of the partition as a cell. So then, initially the Turing Machine starts with its head on the leftmost area, stepping right steps to the right neighbor area etc. In this manner we abstract the concept of a cell to areas. A length then becomes a count of areas; however the size remains a count of the cells. Something similar is done in the C language, where the length of an array is a count of the elements in the array, but the size of the array is a count of bytes. A byte being an addressable unit in physical memory, and thus the underlying cell that everything is built up from.

@@ -2870,31 +2925,31 @@ - - Peano Number + + Peano Number - + Unary representation

- A person can define a Turing Machine that is identical to the recursive definition of Peano Numbers as given by Peano. Giuseppe Peano, Arithmetices principia, nova methodo exposita (Turin: Fratres Bocca, 1889). If a person were to run the Peano Number Machine and observe as it writes to the tape, that person would watch as the Peano Numbers are printed one after another: '·s·ss·sss·ssss· ...'. Here '·' represents zero, and 's·' represents one, etc. Because the Peano Number Machine never halts, the machine cannot be used to initialize a tape, but an analyzer can evaluate the machine to make conclusions about what it would write if it were run. + A person can define a Turing Machine that is identical to the recursive definition of Peano Numbers as given by Peano. Giuseppe Peano, Arithmetices principia, nova methodo exposita (Turin: Fratres Bocca, 1889). If a person were to run the Peano Number Machine and observe as it writes to the tape, that person would watch as the Peano Numbers are printed one after another: '·s·ss·sss·ssss· ...'. Here '·' represents zero, and 's·' represents one, etc. Because the Peano Number Machine never halts, the machine cannot be used to initialize a tape, but an analyzer can evaluate the machine to make conclusions about what it would write if it were run.

- In contrast, a function extension version of the Peano Number sequence generator can be run. The function extension machine would be given as input a prior function extension result, or an initial empty tape. It would then modify the tape to contain the next Peano Number, as per the sequence that the Peano Number machine would write, if it could be run. This is accomplished through two subroutine calls: find_empty and increment. The find_empty machine checks the symbol under the head. Upon finding it is not the empty symbol, the machine steps right and checks the next cell, repeating until it finds the empty symbol, whereupon it halts. The increment machine then writes an 's' onto the tape and halts. Recurrent calls to the Peano Number extender then produce a sequence of result tapes: [], [s], [ss], …. Similarly, a programmer can write a machine called decrement, though the programmer must note that decrementing can return the left-of-leftmost symbol. + In contrast, a function extension version of the Peano Number sequence generator can be run. The function extension machine would be given as input a prior function extension result, or an initial empty tape. It would then modify the tape to contain the next Peano Number, as per the sequence that the Peano Number machine would write, if it could be run. This is accomplished through two subroutine calls: find_empty and increment. The find_empty machine checks the symbol under the head. Upon finding it is not the empty symbol, the machine steps right and checks the next cell, repeating until it finds the empty symbol, whereupon it halts. The increment machine then writes an 's' onto the tape and halts. Recurrent calls to the Peano Number extender then produce a sequence of result tapes: [], [s], [ss], …. Similarly, a programmer can write a machine called decrement, though the programmer must note that decrementing can return the left-of-leftmost symbol.

- To say that Peano Number A is smaller than Peano Number B is to say that A would occur on the Peano Number Machine tape to the left of B, if the machine were run. Conversely, if B were said to be greater than A, that would mean B occurs further to the right. It is a simple matter for a programmer to write a decider machine for this. The decider is given two input tapes for the two numbers to compare, and it keeps a head on each. It then steps forward until neither head has an 's' under it. If empty symbols are found simultaneously on both tapes, then the two numbers are equal; otherwise, the number with an empty symbol under the head is the lesser number. + To say that Peano Number A is smaller than Peano Number B is to say that A would occur on the Peano Number Machine tape to the left of B, if the machine were run. Conversely, if B were said to be greater than A, that would mean B occurs further to the right. It is a simple matter for a programmer to write a decider machine for this. The decider is given two input tapes for the two numbers to compare, and it keeps a head on each. It then steps forward until neither head has an 's' under it. If empty symbols are found simultaneously on both tapes, then the two numbers are equal; otherwise, the number with an empty symbol under the head is the lesser number.

- As such, a person can assign a Peano Number to each cell of a given tape by using a mechanical procedure. Given a machine, say P, and an address machine, say A_P, each time P is stepped right, a call is made to run increment on A_P. Similarly, each time P is stepped left, a call is made to run decrement on A_P. In this manner the tape on A_P will always hold the address that machine P's head is on. + As such, a person can assign a Peano Number to each cell of a given tape by using a mechanical procedure. Given a machine, say P, and an address machine, say A_P, each time P is stepped right, a call is made to run increment on A_P. Similarly, each time P is stepped left, a call is made to run decrement on A_P. In this manner the tape on A_P will always hold the address that machine P's head is on.

- The Peano Number found on A_P is then called the address for the cell that machine P's head is on. As each increment and decrement of the address is a constant-time operation, keeping the address of the cell the head is on is computationally inconsequential. + The Peano Number found on A_P is then called the address for the cell that machine P's head is on. As each increment and decrement of the address is a constant-time operation, keeping the address of the cell the head is on is computationally inconsequential.

@@ -2903,13 +2958,13 @@ - + Hindu-Arabic representation

Charles Burnett published a very interesting book about the translation of Hindu-Arabic mathematics in Europe during the Middle Ages Charles Burnett, Numerals and Arithmetic in the Middle Ages (Farnham: Ashgate Variorum, 2010). DOI: 10.33137/aestimatio.v9i0.25990.. He describes a 9th-century treatise on Hindu-Arabic arithmetic authored by Muḥammad ibn Mūsā al-Khwārizmī, where "al-Khwārizmī" indicated he was from Khwarazm in Central Asia. When this manuscript was translated into Latin in the 12th century, European translators approximated his name as Algoritmi or Algorismi, thus giving us the word algorithm. He notes that the Arabs called such numbers "Indian Numbers". Another chapter, "Why we read Arabic numerals backwards," shows that the little-endian and big-endian debate that has plagued programmers for decades has its origin in the Middle Ages Danny Cohen, "On Holy Wars and a Plea for Peace," IEEE Computer 14, no. 10 (October 1981): 48-54. DOI: 10.1109/C-M.1981.220208.

-

The topological structure of a Hindue-Arabic representation is found embodied in a simple gear based machine called an odometer. Multiple geared wheels occur in a reticulated structure. Pushing a toggle advances the least-significant digit wheel by 36 degrees of rotation. The wheel has a peg in it, such that if it rolls past 9 back to 0, it pushes the toggle on the next wheel in the reticulation sequence. The peg of the last wheel rotates through a toggle that raises the overflow error flag. By its very construction, this process establishes a one-to-one correspondence between each Peano Number and a sequence of symbols in Arabic Representation.

+

The topological structure of a Hindue-Arabic representation is found embodied in a simple gear based machine called an odometer. Multiple geared wheels occur in a reticulated structure. Pushing a toggle advances the least-significant digit wheel by 36 degrees of rotation. The wheel has a peg in it, such that if it rolls past 9 back to 0, it pushes the toggle on the next wheel in the reticulation sequence. The peg of the last wheel rotates through a toggle that raises the overflow error flag. By its very construction, this process establishes a one-to-one correspondence between each Peano Number and a sequence of symbols in Arabic Representation.

@@ -2935,7 +2990,7 @@ Code . A controller that increments a binary counter -

Here TTU is the tape transport unit. It has the number to be incremented mounted on it. This number is either zero, which would mean the leftmost cell is empty, or it is of the same form as a result from a Peano Number extension machine. A TTU.read places a copy of the symbol instance found in the cell under the head into the read buffer automatically when the machine enters a new state on the programmed controller, so it is not counted as a step. In contrast, the other actions are associated with the state of the programmed controller, so when the machine arrives at a write, step, or halt node, it means that the programmed state controller has taken a step. Sequential instructions mean unconditional next-state choices, whereas an if signals a conditional next-state choice. The if condition is a logical proposition based on the read symbol.

+

Here TTU is the tape transport unit. It has the number to be incremented mounted on it. This number is either zero, which would mean the leftmost cell is empty, or it is of the same form as a result from a Peano Number extension machine. A TTU.read places a copy of the symbol instance found in the cell under the head into the read buffer automatically when the machine enters a new state on the programmed controller, so it is not counted as a step. In contrast, the other actions are associated with the state of the programmed controller, so when the machine arrives at a write, step, or halt node, it means that the programmed state controller has taken a step. Sequential instructions mean unconditional next-state choices, whereas an if signals a conditional next-state choice. The if condition is a logical proposition based on the read symbol.

The loop form here is worth taking note of, as it will come up again. The controller executes a first action, that of a read, followed by a middle break test, and then the recursive form actions.

@@ -3028,19 +3083,19 @@ - + The Computability of Length and Unbounded Zeros -

Consider the proposition of representing Peano Numbers with an unbounded sequence of leftward-trailing zero symbols, extending from the leftmost nonzero digit. If a Turing Machine attempts to evaluate the length of this number, or append a digit to the left of its most-significant digit, the machine encounters a structural failure. Any algorithm that starts at the right of the sequence (the least-significant digit) and scans leftward in search of the last non-zero digit can never be sure at any step that there isn't another non-zero digit further to the left, as those members of the sequence have not yet been examined.

+

Consider the proposition of representing Peano Numbers with an unbounded sequence of leftward-trailing zero symbols, extending from the leftmost nonzero digit. If a Turing Machine attempts to evaluate the length of this number, or append a digit to the left of its most-significant digit, the machine encounters a structural failure. Any algorithm that starts at the right of the sequence (the least-significant digit) and scans leftward in search of the last non-zero digit can never be sure at any step that there isn't another non-zero digit further to the left, as those members of the sequence have not yet been examined.

Thus, an append function can never know where to write the appended digit, and a length function can never know when to end the count. Because these functions cannot be computed locally on a tape initialized with unbounded zeros, the viable Arabic Representation must strictly be a finite, growing sequence rather than an unbounded string of zeros. If an algorithm attempts to access an index greater than the extent of this finite sequence, the access function fails. This failure is itself a form of meta-information—information about the structure of the representation rather than the number it encodes.

 - + The Representation of Zero and Structural Emptiness

In the growing Arabic representation, counting acts as a mechanical mechanism. In the case of zero, before the first increment, the mechanism has not yet encountered a carry-in. At this stage, no digits have materialized in the representation. Any attempt to retrieve a digit in this state results in an access violation.

-

This reveals a fundamental property of Arabic Representation: it encodes both the sequence of digit symbols (which map to a Peano Number) and the sequence's length (which exists at a meta level, governing computational operations). The representation of zero exposes a limitation. At zero, the representation retains length information necessary for computation but lacks an explicit numerical mapping to zero itself.

+

This reveals a fundamental property of Arabic Representation: it encodes both the sequence of digit symbols (which map to a Peano Number) and the sequence's length (which exists at a meta level, governing computational operations). The representation of zero exposes a limitation. At zero, the representation retains length information necessary for computation but lacks an explicit numerical mapping to zero itself.

Structurally, this forces a design choice between two options:

@@ -3056,7 +3111,7 @@ - + Numeric value

An Hindu-Arabic number consists of a sequence of digits, d_0 d_1 d_2 \ldots where, in base 10, each digit has a value ranging from 0 to 9. In this section, these sequences are represented using sequence notation. For example, X = [7, 8, 9] is a sequence with three components. Its zero index component, x_0, is 7, etc. Note that X is written as a capital letter to denote that it is a container, while its individual members use small letters.

@@ -3073,7 +3128,7 @@ - + Meaning of the word digital

The information about ENIAC in this chapter is found in a 1947 IRE article, "Electronic Computing Circuits of the ENIAC" by Arthur W. Burks Arthur W. Burks, "Electronic Computing Circuits of the ENIAC," Proceedings of the IRE 35, no. 8 (August 1947): 756-767. DOI: 10.1109/JRPROC.1947.234265. I found it interesting that some of the design issues for flip-flops made of vacuum tubes resemble those of designing static RAM cells in CMOS. Although ENIAC's implementation is electronic, its architecture is fundamentally that of a mechanical machine.

@@ -3100,7 +3155,7 @@ - + Scanning-Order and Digit-Order

Had this book been written in Hindu-Arabic, the text would be written right to left. Let us explore what that looks like by using an example where we start with an English sentence and then reverse it. Notice that in this right to left string, the sequence [9, 8, 7] without notation is 987. Both strings match.

@@ -3135,7 +3190,7 @@ - + Binary, Octal, Hexadecimal, BCD

A person interprets a sequence of n bits as a number by using this function:

@@ -3213,7 +3268,7 @@ - + Allocation

In most text documents, a number is written down once and remains unchanged. In contrast, a computing program frequently returns to the exact memory location and changes its value. This is equivalent to erasing an old value on a paper document and writing a new value in the same space.

@@ -3266,7 +3321,7 @@ - + Bit Order Within Bytes

Data transports between hardware nodes over bundles of wires called buses. Bus specifications explicitly define the order of bits in bytes, and for contemporary machines, bytes are strictly octets. All compute processors, channel processors, and attached devices must conform to the bus’s specifications.

@@ -3281,7 +3336,7 @@ - + Byte Order Within Words

A specific processor architecture features native support for byte data alongside varied word lengths, most commonly 16, 32, and 64 bits (or 4, 8, and 16 bytes).

@@ -3324,7 +3379,7 @@ - + RT

The native Integer data type for RT utilizes a high radix online number system. This number system functions as an extension of online arithmetic. Similar to online arithmetic, it employs serial most-significant-digit-first signed-digit arithmetic. In contrast to standard signed arithmetic, the radix scales significantly higher, causing a digit to span at least a byte in length. The numbers are highly scalable, and the architecture mandates an analysis step at compile time to establish rigorous precision requirements and exact range bounds. This process is detailed in the next chapter. The architecture provides explicit conversion instructions to generate alternate number formats.

@@ -3333,7 +3388,7 @@ - + Address @@ -3439,7 +3494,7 @@ - + The Universal Turing Machine

The Computer Theoretic model chapter provided symbolic definitions for the Turing Machine and the RT variation. Those definitions were written as strings of characters, which the reader scanned, and presumably understood, thus demonstrating the ability of those text strings to convey meaning. Furthermore the text explained in detail how an executor could make use of those definitions so as to perform the input string transformations. As Turing originally noted, the executor could be a person. Alternatively, as the book continued on to describe in detail, the executor could be a machine that applied the input transformations automatically.

@@ -3574,21 +3629,21 @@ - + Symbol - + Natural Symbol -

The design for the RT Machine was given in chapter . On that machine there was a column of patch panel holes said to be symbols for gating next state transitions. The presence of a symbol could be ascertained by its effect on the machine by observing the indicator lights, or more directly if the observer is allowed and facilitated to probe the machine with a voltage meter. Alternatively, the symbols could be enumerated in the abstract, as the maker of the control panel did, when he wrote symbol names next to each of the symbol holes. These are all natural actions. When there are merely two such symbols the machine is said to be a "binary" machine. +

The design for the RT Machine was given in chapter . On that machine there was a column of patch panel holes said to be symbols for gating next state transitions. The presence of a symbol could be ascertained by its effect on the machine by observing the indicator lights, or more directly if the observer is allowed and facilitated to probe the machine with a voltage meter. Alternatively, the symbols could be enumerated in the abstract, as the maker of the control panel did, when he wrote symbol names next to each of the symbol holes. These are all natural actions. When there are merely two such symbols the machine is said to be a "binary" machine.

- + Conventionally defined symbol

- A symbol is a distinct mathematical object capable of being instantiated. Within a given context, any instance of a specific symbol evaluates as equal to any other instance of that identical symbol, and evaluates as not equal to any instance of a different symbol. (Here we speak at the metamathematical level, where the objects being compared are the symbol instances themselves, rather than anything that might be bound to the symbol. binding is discussed in section .) + A symbol is a distinct mathematical object capable of being instantiated. Within a given context, any instance of a specific symbol evaluates as equal to any other instance of that identical symbol, and evaluates as not equal to any instance of a different symbol. (Here we speak at the metamathematical level, where the objects being compared are the symbol instances themselves, rather than anything that might be bound to the symbol. binding is discussed in section .)

@@ -3600,7 +3655,7 @@

- + Naturally derived Math Symbol

@@ -3611,7 +3666,7 @@ A symbol instance newly minted by the factory is said to come direct from the factory. A symbol instance direct from the factory is also called an original.

- + Required properties of symbol factories

@@ -3632,7 +3687,7 @@ - + Instance implementation

@@ -3656,12 +3711,12 @@

- At the time of this writing many machines use 64 bit words. This is equivalent to 8 ASCII characters, while the average size of an identifier is about 5 characters. Hence the approach of using a string as a symbol might not be as inefficient as it seems to be at first. Using strings has advantages. Symbol instances can carry semantic clues for the programmer. There is no hazard of conflating the string instance with the name, as they are the same. Also, a string instance will have integrity across contexts, such as between invocations or when passed between processes (note section , on crossing context boundaries). A drawback is in cases there is no language support, the strings are typically ad hoc so the guarantee of distinctness becomes merely a contract with the programmer. + At the time of this writing many machines use 64 bit words. This is equivalent to 8 ASCII characters, while the average size of an identifier is about 5 characters. Hence the approach of using a string as a symbol might not be as inefficient as it seems to be at first. Using strings has advantages. Symbol instances can carry semantic clues for the programmer. There is no hazard of conflating the string instance with the name, as they are the same. Also, a string instance will have integrity across contexts, such as between invocations or when passed between processes (note section , on crossing context boundaries). A drawback is in cases there is no language support, the strings are typically ad hoc so the guarantee of distinctness becomes merely a contract with the programmer.

- + Distinctness across contexts

@@ -3679,7 +3734,7 @@ - + Symbol copy consequentiality

@@ -3700,7 +3755,7 @@ - + Alphabet

@@ -3711,7 +3766,7 @@ - + Symbol implementation examples

@@ -3820,10 +3875,10 @@ - + Binding - + Property

@@ -3832,18 +3887,18 @@ - + Dictionary and reference

A dictionary is a property context object. It is a set of properties, where a property may be selected from the set given its name, which is a symbol instance. The corresponding property value is then the referenced object.

-

A reference is a dictionary key which uniquely identifies a property in the dictionary. A dictionary is also known as a symbol table. In hardware design, the symbols are often unsigned Integers, AKA Peano Numbers, and a symbol table is implemented using an array that is indexed into using the key.

+

A reference is a dictionary key which uniquely identifies a property in the dictionary. A dictionary is also known as a symbol table. In hardware design, the symbols are often unsigned Integers, AKA Peano Numbers, and a symbol table is implemented using an array that is indexed into using the key.

Any programming object that holds other objects is a container, whereas a dictionary is a specific type of key access container.

 - + A Turing Machine tape cell

@@ -3863,7 +3918,7 @@ - + Mathematical Tape

The RT Machine is a natural object. We observe its mechanisms, name its parts, and then find symbol representation for them so as to facilitate introspection. In short, we build a model.

@@ -3896,10 +3951,10 @@ - + Computational Analysis - + Definition

@@ -3912,7 +3967,7 @@

The orders of analysis were named in section - . This + . This chapter takes the second-order as its working material.

@@ -3931,7 +3986,7 @@ - + second-order Arithmetic

@@ -3962,7 +4017,7 @@ (write s) (step) )) - Code . The abstract syntax tree for the Peano Number five + Code . The abstract syntax tree for the Peano Number five

Similarly, the AST for the number 3:

@@ -3977,7 +4032,7 @@ (write s) (step) )) - Code . The abstract syntax tree for the Peano Number three + Code . The abstract syntax tree for the Peano Number three

@@ -4024,7 +4079,7 @@ Code . A composer that subtracts by inverting the direction of one machine -

We pass our two Peano Number ASTs to this composer, and we get as a result a newly synthesized AST.

+

We pass our two Peano Number ASTs to this composer, and we get as a result a newly synthesized AST.

@@ -4058,7 +4113,7 @@

- For a program containing branched control logic, the simplifier would require a deep recursive walk of the AST to ensure operations aren't annihilated across conditional boundaries. For our explicit Peano Number generators, a linear scan of the progn body suffices. It calls itself recursively until the scan fails to find any further reductions, returning its optimized AST. + For a program containing branched control logic, the simplifier would require a deep recursive walk of the AST to ensure operations aren't annihilated across conditional boundaries. For our explicit Peano Number generators, a linear scan of the progn body suffices. It calls itself recursively until the scan fails to find any further reductions, returning its optimized AST.

@@ -4124,11 +4179,11 @@ - + The multiplicative inverse of the additive identity

- Generally it is more efficient to perform arithmetic in the first-order. Also, it is easier to write Turing Machine control programs if we take Peano Number arithmetic as already available, say, from a subroutine library. On processors fixed word length arithmetic is built into the hardware. Where second-order computation becomes useful is in places where a result cannot be computed in the first-order. + Generally it is more efficient to perform arithmetic in the first-order. Also, it is easier to write Turing Machine control programs if we take Peano Number arithmetic as already available, say, from a subroutine library. On processors fixed word length arithmetic is built into the hardware. Where second-order computation becomes useful is in places where a result cannot be computed in the first-order.

@@ -4177,7 +4232,7 @@ - + Evaluating and Extending

@@ -4288,7 +4343,7 @@ For Call 2, the input tape is the result tape from Call 1. Execution then proceeds identically to Call 1. This pattern repeats for all successive calls. A person can see the values of t^2 as the first number on each result tape. Any polynomial can be computed in this manner, and the only ALU required is an adder that is also capable of subtraction.

- + Lemma: Only row 0 is needed

@@ -4301,7 +4356,7 @@ - + Lemma: Evaluating call \omega requires an initial tape populated with components 0 through \omega of row 0

@@ -4360,7 +4415,7 @@ - + Lemma: A polynomial function of degree \omega will have a D_0 vector of extent \omega

@@ -4373,7 +4428,7 @@ - + Lemma: A D_0 vector of finite extent \omega generates a polynomial function of degree \omega

@@ -4473,7 +4528,7 @@

- The main diagonal contains strictly non-zero factorials, ensuring the matrix is invertible. By inverting this matrix, a person replaces the cascading back substitution with a direct, closed form equation to recover any constant a_i. The inversion utilizes the signed Stirling numbers of the first kind, denoted s(n,i) (see the Appendix on Stirling numbers, section ). + The main diagonal contains strictly non-zero factorials, ensuring the matrix is invertible. By inverting this matrix, a person replaces the cascading back substitution with a direct, closed form equation to recover any constant a_i. The inversion utilizes the signed Stirling numbers of the first kind, denoted s(n,i) (see the Appendix on Stirling numbers, section ).

@@ -4507,7 +4562,7 @@ - + Difference table for an exponential function

@@ -4569,7 +4624,7 @@

- The first difference of 2^t is also 2^t, so row 0 of the table will have an infinite number of values. Fortunately, due to the lemma of section , stating that evaluating call \omega requires an initial tape populated with components 0 through \omega of row 0, exactly those components are needed for the recurrence to proceed. Furthermore, when new values are needed, they are easily computed. A programmer need not store the entire infinite first row of the difference table on a static tape. + The first difference of 2^t is also 2^t, so row 0 of the table will have an infinite number of values. Fortunately, due to the lemma of section , stating that evaluating call \omega requires an initial tape populated with components 0 through \omega of row 0, exactly those components are needed for the recurrence to proceed. Furthermore, when new values are needed, they are easily computed. A programmer need not store the entire infinite first row of the difference table on a static tape.

@@ -4578,7 +4633,7 @@ - + Composition of recurrence functions

If we desire to compose recurrence functions, in the first-order or the second-order, the call counts must first be synchronized.

@@ -4591,7 +4646,7 @@ - + A pole and zero cancellation

@@ -4870,7 +4925,7 @@ - + Chapter discussion

The fundamental claim of computational analysis is that all functions can be viewed as discrete entities. Take this simple function:

@@ -4920,10 +4975,10 @@ - + Appendix: The Tension Between Formal Methods and Practical Architecture - + Does computation theory matter to computing?

@@ -4986,7 +5041,7 @@ - + Do formal methods belong in computer design? @@ -5015,7 +5070,7 @@ - + Computational Naturalism: the transforms are reversible

@@ -5027,7 +5082,7 @@

- We then define the symbol in computational terms, as done in section . This begins with memory addresses, represented as charge arrays, acting as primitive symbols, and extends to the symbol factory, copy operations, and instance comparison. + We then define the symbol in computational terms, as done in section . This begins with memory addresses, represented as charge arrays, acting as primitive symbols, and extends to the symbol factory, copy operations, and instance comparison.

@@ -5035,11 +5090,11 @@

- On top of this we can define the Peano Machine, a counter, and then use that machine as the definition of Peano Numbers. + On top of this we can define the Peano Machine, a counter, and then use that machine as the definition of Peano Numbers.

- Where Gödel reduced logic to Peano Numbers, we go the other direction to expand upon logic from Peano Numbers. + Where Gödel reduced logic to Peano Numbers, we go the other direction to expand upon logic from Peano Numbers.

@@ -5074,7 +5129,7 @@ - + Appendix: Stirling Numbers

@@ -5089,7 +5144,7 @@ To understand their mechanical role, a person must look at the mathematical basis used in each domain.

- + The Continuous vs. Discrete Basis

@@ -5114,7 +5169,7 @@ - + Stirling Numbers of the Second Kind, S(n, k)

@@ -5135,7 +5190,7 @@ - + Stirling Numbers of the First Kind, s(n, k)

-- 2.20.1