Dmytro Taranovsky
July 17, 2005

Finitistic Properties of High Complexity

Abstract: We use fast growing finite and infinite sequences of natural numbers to define models of hypercomputation and plausibly finitistic non-arithmetic properties of integers. The strongest extension reaches full second order arithmetical truth.

List of Sections: Introduction, A Model of Hypercomputation, Strengthenings to Multiple Sequences, Finite Structures, Σ12 Truth, Second Order Arithmetic and Beyond.

Introduction

Finitism refers to definitions and arguments that do not use an actual infinity, though they may involve a potential infinity. The potential infinity refers to the fact that the natural numbers are unlimited, and that there are arbitrarily large natural numbers. Hyperfinitism by contrast deals only with "small" natural numbers, such as those whose binary representation is feasible.

The central question about finitism is what properties are definable and what claims are demonstrable finitistically. At one extreme is the view that finitistic properties are the recursive ones, and that finitistic demonstration does not go much further beyond PRA. At the other extreme is the view that every definable property (including the truth predicate of set theory) of natural numbers can be defined finitistically, and that every true mathematical claim is finitistically demonstrable. On that view, infinite structures are useful as conceptual aids and for argument simplification, but can ultimately be replaced by finitistically definable finite analogues. Finitistic strong consistency proofs can involve either new finitistic properties or just new insights on the recursive properties. Most logicians have a narrow view of finitistic definability because of absence of evidence to the contrary. Plausibly finitistic ways to define properties of high complexity or to prove strong consistency statements were simply not known before this paper.

Hypercomputation refers to idealized computers computing non-recursive functions. Models of hypercomputation may be divided into two types. One uses oracles, either directly or through some auxiliary mechanism. The other uses an infinite amount of computation in finite time. In the models we propose (which are technically oracle based), finite computations correspond to infinite computations by using fast-growing sequences to convert unbounded searches into bounded ones.

In a way, this paper complements my paper "Extending the Language of Set Theory," especially the last section. Both papers use largeness to extend the language — of number theory in this paper, and of set theory in the other paper.

The second section describes computation using a single sufficiently fast growing infinite sequence. The third section discusses computation using multiple sequences. The fourth section presents similar results for finite sequences. The fifth section describes a plausibly finitistic way to compute Σ12 truth. The final section extends the results to full second order arithmetic, and also discusses definitions using only the countable infinity.

A Model of Hypercomputation

A powerful hypercomputation model rests on a surprisingly mild physical assumption:

There is a type of event that occurs an unlimited number of times, but with frequency of occurrence decreasing sufficiently fast.

Formally, a language L is recognized by the (oracle) Turing machine iff there is a total function A such that for every B with B(n)≥A(n) (for every n), the machine using B as an oracle halts on input S iff S is in L.

It is not known whether such machines are physically constructible. Currently, the biggest problem is surviving for the extremely long time required, rather than the apparent lack of the required physical events. In any case, studying the machines improves our understanding of the recursion theory. Below, we prove that a language is recognized by such a hypercomputer iff it is Π11. Thus, a language is decidable in the model iff it is hyperarithmetic. Note that Π11 rather than Σ11 is the correct analogue of recursively enumerable. Also, a set is definable in first order arithmetic with a sufficiently fast growing function A (independent of A) iff it is recursive in a finite hyperjump of 0.

For a sufficiently fast growing sequence A, a recursive relation has an infinite descending path through n iff it has an infinite descending path through n and then through a natural number less than A(max(n, m)) where m is the length of the given recursive definition of the relation. By Konig's lemma, if the relation is well-founded, then the tree is finite, and thus the machine will eventually discover that the relation is well-founded.

For converse, we examine the tree of all (oracle) sequences. We build the computational history for every branch of the tree. A computation terminates if the computation history has no infinite path (technically, if it has no sufficiently fast growing infinite path, but that does not affect the expressive power). Thus, the halting problem is in Π11. Also, the rank of a terminating computation is defined as the ordinal depth of the part of the tree used by the computation.

The model admits a complexity theory that essentially agrees with the classical one. An oracle is given as a one-dimensional tape with sequential access, with '1' at a position n indicating that n is in the range. To avoid a possible unreasonable speed up for some NP problems, we require the oracle to be informationally sparse in that it can be (uniformly) generated up to n cells in polynomial time from O(log n) space. A problem can be solved in time T(n) iff there is a Turing machine and an informationally sparse set A such that the machine using A solves the problem in time T(n) and that whenever nth element of B ≥ nth element of A, the machine using B correctly solves the problem. Thus, a language has recursive complexity iff it is recursive, and arithmetic complexity iff it is arithmetic. A key strength of the theory is that there is no unreasonable speed-up even for non-recursive problems: The sequences allow the computers to make the fullest use of the time spent without coding in the answers.

Strengthenings to Multiple Sequences

Still higher complexity is reachable by computers that use a sufficiently fast growing function A and a function B that grows sufficiently fast relative to A. Formally, a language L is recognized by the machine iff there is an (infinite) sequence A such that for every B with B(n)≥A(n), there is a sequence C such that for every D with D(n)≥C(n), the machine using B and D as oracles halts on input S iff S is in L.

The set of winning positions in a Σ02 game is recognizable in this model. To see this, if a player has a winning strategy, then he has a winning strategy using moves less than B(position), where position includes the position in the game and a canonical description of the rules. Given this constraint on the moves, the second player has a winning strategy iff he has a strategy that enters then nth open set before time D(n+position). Given these constraints, the game becomes an open one with finite number of moves per turn, and hence recognizable.

We can extend the model to allow more sequences, each of which growing sufficiently fast relative to the previous ones. We can even allow transfinitely many sequences through the use of diagonalization. To handle such cases, an infinite alternation of quantifiers is defined to mean existence of a winning strategy in the corresponding game. The n-tuple of sequences will be called a sequence of level n.

At least for finite levels, the extension also has a complexity theory agreeing with the classical one. The definition is analogous to the definition in the previous section. The program has to remain correct if the growth rate of a sequence is increased, and the sequences dependent on that sequence are made to grow sufficiently fast. This way computational complexity theory is extended beyond hyperarithmetic sets.

We conjecture the following to have equal complexity:

  1. Recognizability using sequences of level n+1.
  2. For n>0, existence of winning strategies in level n of the difference hierarchy of (lightface) Δ03 sets (level 1 is Σ02).
  3. Monotone inductive definitions for co-recognizable sets (relative to the current real number) for sequences of level n (for Π01 if n=0).
  4. For n>0, Σ1 truth below the least recursively n-inaccessible ordinal.

Moreover, (we conjecture that) allowing number quantification in the model corresponds to the boldface or iterated version of the last three properties. For example, (4) would read, "Real numbers constructible below the least limit of recursively n-inaccessible ordinals."

Also, (we conjecture that) allowing the complex of sequences to have an arbitrarily high well-founded order corresponds to, "for every ordinal α, there is a recursively α-inaccessible ordinal," which is equivalent (under V=L) to boldface Δ03 determinacy.

The equivalences show us both the power and limitations of the concept of sufficiently fast growing sequences. The concept suffices for most mathematical analysis, yet, as given, it is not sufficient for even recursively Mahlo ordinals.

Finite Structures

The infinite structures have finite analogues. The key concept is that of a sufficiently fast-growing sufficiently long finite sequence. Sufficiently long is with respect to the rate of growth. In computation, along with input, we will be given such a sequence, with the first element larger than the input size.

Vagueness is avoided because there is no error in interpreting "sufficiently" too strictly. What we are defining are not the sequences themselves, but the results of the computations, and the computations agree for all appropriate (as explained above) sequences. The appropriate sequences can then be formally defined as the ones giving the correct results. Also, by using infinite sets, we can quantify over all possible definitions and thus formally define the results without using "sufficiently".

For a single sequence, decidability corresponds to being Δ11 in the hyperjump of 0. To see that, note that the algorithm above for testing well-foundness (with reaching the end of the sequence indicating an infinite path), will work correctly (and compute the hyperjump of 0) up to a very large unspecified point in the sequence. In deciding a problem in the class, check (using the partially computed hyperjump of 0) which of the two opposing sequences (for the sentence and its negation) terminates first: For inputs in the size limit, that will happen before that unspecified point.

A finite sequence appears more expressive than the corresponding infinite sequence because it gives us a stopping point. Also, if we allow the computers to produce sufficiently fast growing sequences of level n unlimited number of times, that corresponds to an infinite sequence of level n+1. However, to make the definition of sufficiently fast as concrete as possible, we limit ourselves to a single application (of the producer of the sequences), and to correctness with respect to an ordinary Turing machine using that application.

Every sufficiently fast growing sufficiently long sequence, has (relative to the sequence) a sufficiently fast growing sufficiently long subsequence. Such nesting can be done an arbitrary number of times, yielding finite objects that can be used to solve problems of high complexity with appropriate input size. By using diagonalization, it can even be done "transfinitely" many times, but such "transfinite" constructions are not (immediately) finitistic.

The description of such sequences (and sets of sequences) is done without invoking an actual infinity, and therefore is apparently finitistic. By using finite sequences of level 3, we can finitistically define the truth predicate for the minimal transitive model of KP plus (boldface) Σ11 Monotonic Induction, which (more than) suffices for mathematical analysis, except for exceptional cases.

Notice that the finitistic descriptions seem less concrete than the precise formal definitions that use infinite sets. Infinity (if accepted) eliminates any appearance of vagueness in these descriptions. It can be argued that the descriptions make a subtle use of infinity, but in any case, they enrich our mathematical understanding. Obviously, doubts about being finitistic increase as the level of expressiveness is increased.

Σ12 Truth

We now give an apparently finitistic definition of Σ12 truth. Essentially, this section describes in detail level 2 estimators of the next section.

Along with input, we are given a finite set of finite sequences. Each sequence is sufficiently long relative to itself, or relative to its rate of growth. If A is sufficiently long and |A|≤|B| and ∀n<|A| B(n)≤A(n), then B may be considered sufficiently long. Arbitrary conditions may be imposed on the sequences as long as they do not impose an upper bound on the rate of growth. (An upper bound would be a function f such that for every permitted sequence A, ∃n<|A|-1 A(n+1)<f(A(n)) or A(0)<f(0).) Given these conditions, the set is sufficiently complete for the input size. Completeness is preserved under addition of new sequences or decrements to input size. We are not given the conditions on the sequences, but so long as they include a basic "sufficient length" condition, the algorithm below is guaranteed to be correct.

The algorithm aims to check whether the sentence encoded in the input has a transitive model. It enumerates potential initial segments (of the length of the longest sequence in the set of sequences) of the truth predicate for the language with a distinguished symbol for a well-ordering of the elements. Each segment is checked for a quick (relative to its length) inconsistency with the sentence. If not found inconsistent, it is converted into a finite quasi-model, with elements coded by sentences of the right syntactic form: ∃x P(x) codes the least such x if true, and 0 if false. Then, for every sequence A with A(0) larger than the input size, it tries to form a descending path (a, b, c, …) of elements with a<A(1), b<A(2), c<A(3), … . If the path reaches length |A|-1, the truth predicate is rejected; otherwise it is accepted by the sequence. The algorithm returns 'yes' iff a truth predicate segment is accepted by all sequences.

To see that the computation is correct, note that if a sentence has a transitive model, then it has a transitive model of bounded complexity, and hence without sufficiently long descending sequences of the required type. If it does not have a transitive model, then in the complete binary tree of candidate truth predicate initial segments, every path will have an infinite descending sequence (or inconsistency). Thus, regardless of how strictly "sufficiently long" is defined, every path will have sufficiently long infinite descending sequences. By Konig's lemma, a finite set of such sequences can cover all paths.

The construction has an infinite version, namely a predicate or a tree on finite sequences of natural numbers. Consider a well-founded tree of such sequences (ordered by extension) such that every non-leaf node can be extended by any natural number, and if a sequence is a leaf node, then it is sufficiently long relative to itself (or relative to its rate of growth; the difference does not affect the expressive power). Using such a tree, recognizability is Π12 complete (however, Σ12 may be a better analogue of being recursively enumerable). The theory admits computational complexity theory, which is analogous to the one in the second section: The algorithm is required to be correct for any well-founded extension of the tree used. (However, this allows some unreasonable speed-ups (including arbitrarily high recursive speed-ups); requiring that sequence lengths in the initial tree are not decreased when the rate of growth is increased may solve the problem.)

We can extend definability be using an infinite sequence growing sufficiently fast relative to the tree. Recognizability then corresponds to having a Π12 monotonic inductive definition. A stronger extension is to use an n-tuple of trees, with sequences in each tree sufficiently long relative to themselves, and to every previous tree. The extensions also admit a complexity theory analogous to the one in the third section.

Second Order Arithmetic and Beyond

Every sentence in second order arithmetic can be converted in polynomial time (and if necessary, provably in RCA0) to the following form: Q X1Q X2 … Q Xn ∀x ∃y>x P(X1∩y, X2∩y, …, Xn∩y), where P is polynomial time computable, Xi∩y refers to the first y digits of Ai, and Qs are quantifiers with the last Q being ∃. Each Xi represents an infinite binary sequence.

We compute the truth-values of these statements by using estimators. Estimations can be done at various levels of correctness.

In "sufficiently complete", ambiguity is avoided because there is no error if "sufficiently" is interpreted too strictly. However, we have to specify which interpretations are impossible. The following set of criteria appears correct. If c≤a and d≥b and (a, b) is acceptable, then so is (c, d). For every a, there is b such that (a, b) is acceptable. Completeness of an estimator of level n+1 stays the same or is increased by including another level n estimator (or--but this is not necessary for the definition--by changing an included level n estimator into one of the same or lesser completeness; note that some degrees of completeness may be incomparable). For every n, there are (finite) sufficiently complete estimators of level n regardless of how strictly (consistent with the requirements, including this one for lower levels) "sufficiently complete" is interpreted for levels below n.

To see that the description is correct, if a Σ1n statement is true, then it has a witness (for the outermost existential quantifier) of bounded complexity. Level n-1 estimators will work correctly with that witness and hence the sentence. On the other hand, if a Σ1n statement is false, then every potential witness will be intercepted by some level n-1 estimator, and hence the falsehood will be witnessed by a sufficiently complete set of such estimators. By induction on n, the method is correct.

The estimators have an infinite version, that of predicates for every n of being sufficiently complete. To make it work for every input size, we require that the completeness is achievable for every lower bound on a in level 0 estimators (a, b).

This completes our description. What remains is finitistically studying which axioms to include in the system. If, for example, projective determinacy for the results of the estimations will be deemed a finitistically acceptable axiom schema, we will have a finitistic consistency proof of ZFC.

Using Countable Infinity

We can also consider what can be expressed using real numbers but without using an uncountable infinity. One way to increase expressiveness is to allow an infinite alternation of real quantifiers. Formally, ∃X1 ∀X2 … can be defined as true when the first player has a winning strategy in the game where the players takes turns to play Xi and the goal of the first player is to satisfy the formula after the quantifiers. This leads to expressiveness beyond L(R). Technically, for every countable ordinal α, real numbers definable from a countable ordinal using 1+α+1 real quantifiers are precisely those that are in the minimal iterable inner model with α Woodin cardinals. Just ω+2 real quantifiers go beyond first order definability in L(R).

This definition uses strategies, which are formally uncountable. However, we can avoid the uncountable by introducing a notion of Y having a sufficiently large complexity (under Turing reducibility) relative to X. As before, vagueness is avoided because every sufficiently strict notion works. We obtain the necessary complexity by using a sequence of α real numbers, each sufficiently complex relative to a join of the previous real numbers. Statements with infinite alternations of quantifiers can be decided by restricting the complexity of the strategies: For γ levels of play, the strategies must be recursive in the γ's member of the sequence. By determinacy, and by sufficiency of the sequence, this does not affect who wins. We can go even further by using sequences with ordinal length sufficiently long relative to themselves. Reaching higher complexity is an endless endeavor.