{'fraction_non_alphanumeric': 0.04042888374485597, 'fraction_numerical': 0.015303497942386831, 'mean_word_length': 4.014832728738412, 'pattern_counts': {'":': 0, '<': 78, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Universal Hypercomputer

This paper describes a type of infinitary computer (a hypercomputer) capable of computing truth in initial levels of the set theoretic universe, V. The proper class of such hypercomputers is called a universal hypercomputer. There are two basic variants of hypercomputer: a serial hypercomputer and a parallel hypercomputer. The set of computable functions of the two variants is identical but the parallel hypercomputer is in general faster than a serial hypercomputer (as measured by an ordinal complexity measure). Insights into set theory using information theory and a universal hypercomputer are possible, and it is argued that the Generalised Continuum Hypothesis can be regarded as a information-theoretic principle, which follows from an information minimisation principle.


Introduction
This paper introduces the notion of a universal hypercomputer and shows that all sets in the Von Neumann hierarchy of pure sets can be computed by a universal hypercomputer, and computation theory with sufficient resources can be regarded as a recasting of set theory. The significance of this equivalence is that there are likely to be natural computational analogues in set theory. An example is given of the Generalized Continuum Hypothesis, which is shown to be an informationtheoretic principle. and which follows from an information minimization principle (see section 5).
According to B. J. Copeland [4] " [a] hypercomputer is any information-processing machine, notional or real, that is able to achieve more than the traditional human clerk working by rote." Hypercomputers are a controversial topic (see [5], [6]) because by definition they exceed what a human (or a computer) could compute by rote with finite resources in a finite time. And certainly it is not at all clear that you could physically build any kind of hypercomputer (see [22]). For example, an important class of hypercomputer allows a computer to run forever and converge to an output, and to start again with outputs taken to be inputs. This type of hypercomputer ("a infinite run time hypercomputer") requires a countably infinite sequence of computation steps, which humans cannot complete. Likewise a human could not load the input registers of a hypercomputer which allows arbitrary real numbers as input, because a human cannot load the uncountably infinitely many bits in an arbitrary real number and, even if a real number could be replaced by a finite label, there are uncountably many real numbers (see [1] and for a more recent survey see [24]).
Having noted the impracticability of hypercomputers, by way of contrast it is worth highlighting the long standing and rich literature of (meta-)mathematical results describing the computational power of different types of hypercomputer, starting with A. M. Turing's oracle machines (see [4,3,19]). Fundamentally infinitary models of hypercomputers can provide strong intuitions and sometimes result in simplifications of proofs and shortening of the length of those proofs. An example, taken from the subject of proof theory (see [20] for this and other examples), is that K Schütte's proof of the consistency of first-order Peano arithmetic is much shorter than G. Gentzen's original (broadly finitary) 1 proof because Schütte introduced two natural inference rules with an infinite number of premisses (usually countably infinitely many), collectively known as the ω-rule, which is generally the inference from S ⊢ P (c) for all constant symbols c to S ⊢ (∀x)P (x), and the dual inference from S ⊢ (∃x)P (x) to S ⊢ P (c) for some constant symbol c). It is also worth mentioning that computational power is related to the proof power of a deductive axiom system because a (total) function f is computable if (∀x)(∃y)(f (x) = y) is provable in some deductive axiom system. It would seem to follow that a hypercomputer can prove more than a Turing machine could; and indeed, this is true. A hypercomputer which allowed countably infinitely many registers of a computer to be non-empty and allowed a state to require countably infinitely many register values to match a condition would be able to implement the ω-rule and to decide the truth or falsehood of every proposition in first-order Peano arithmetic. The difficulty is that the ω-rule and the computer states that correspond to it are in principle not human computable when any model of a deductive system has an infinite domain (such as the set of the natural numbers). But of course that does nothing to undermine the truth of the result that first-order Peano arithmetic plus the ω-rule is complete for the language of first-order arithmetic.
In a similar vein a number of important results are known about hypercomputers. We will cite two such results. The first result (from [9]) is that an infinite run time hypercomputer is complete for first-order arithmetical truth and can decide the truth of all Π 1 1 propositions (i.e. propositions of the form (∀X)P (X), where formula P may contain bounded variables over the natural numbers but the variable X over sets of natural numbers remains free) and decide the membership of sets of natural numbers that are defined by a Π 1 1 formula with a free natural number variable. 2 The significance of this result is that Π 1 1 propositions and sets are impredicative 3 , and by a classic result due to S.C. Kleene and C. Spector (see [7], [21]) the sets of natural numbers (or equivalently real numbers) defined by a ∆ 1 1 1 The principle of transfinite induction up to the countable ordinal ǫ 0 is less finitary than primitive recursive functions but still corresponds to a definite progression in the complexity of the (concrete) proof figures. 2 It is possible for a Π 1 1 formula to have free variables over sets of natural numbers (indeed that is an essential part of the language of second order arithmetic), but in terms of a predicative concept of set, one starts with sets of natural numbers definable by arithmetical formulas and then defines sets of natural numbers inductively by relativizing quantifiers over sets of natural numbers of arbitrary formulas of second order arithmetic to the sets already defined and iterates this construction to the first non-recursive ordinal (see [7]). The resulting set of sets of natural numbers are the hyperarithmetical sets of natural numbers. 3 A set of natural numbers defined by an impredicative formula is a set of natural numbers defined by a formula that quantifies over all sets of natural numbers.
formula with a free natural number variable 4 can be identified with sets of natural numbers computable by a transfinite sequence of oracle machines up to the first non-recursive ordinal, starting from a universal Turing machine and adding a function which computes the halting problem of the previous oracle machines in the sequence (see [9] and compare the infinite time register machine defined in [13]). 5 The fact that ∆ 1 1 ⊂ Π 1 1 shows just how powerful a hypercomputer must be to decide the truth of all Π 1 1 propositions or membership of Π 1 1 sets. It is also worth mentioning that hyperarithmetical sets have been generalised by R. Shore, G. Sacks et al to set theory by means of α-recursion theory 6 . P. Koepke and B. Seyfferth [16] have shown that hypercomputers with α registers and up to α steps in a computation with a finite program can compute α-recursive and α-recursively enumerable sets, and can be used to prove results in α-recursion theory computationally. A second, even stronger result (from P. Koepke, see [12,15,14]) is that a hypercomputer that has a finite program, but has an infinite number of registers and an infinite run time that can have any infinite ordinal value, can compute all constructible sets (in the sense of K. Gõdel's constructible universe of sets, see [17] for a clear introduction) of ordinals from finitely many ordinal parameters. This result shows that ordinal constructibility (or better definability in terms of previously defined sets) is the same as a general notion of ordinal computability with a finite program. Now although the literature has considered Turing machines/register machines with infinite run time (which always terminate after countably many steps) and Turing machines/register machines with infinite run time and infinite memory indexed by the class of all ordinals (known as ordinal computers), there has been no exploration to date of Turing machines with infinite run time, infinite memory and programs with an infinite number of instructions. This paper proves the result that the set of hypercomputable sets with finitely many ordinal parameters (specifying the hypercomputer configuration) is the Von Neumann hierarchy of pure sets.
In many ways this result is fairly obvious: unconstrained computation resources lead to every set being computable. But it also leads to the thought that computational notions are likely to have natural set theory analogues. If we define the number of bits of information in a set x (expressed as a binary sequence that represents all the members of x as well as x) as the least length of the sequence which can be losslessly compressed from x, then we can see that the number of bits of information in a binary sequence of length α is ≤ α. In fact the amount of information in a set is a cardinal number, ℵ, because any sequence of length ℵ ≤ α < ℵ + 1 can be losslessly compressed by being mapped one-to-one and onto a sequence of length ℵ by definition of cardinal number. It is shown in Theorem 9 that the Generalized Continuum Hypothesis (GCH) states that the amount of information needed to decide the relation x ∈ X by enumeration 7 of X ⊆ 2 ℵ and 4 A ∆ 1 1 formula can be expressed in the form Π 1 1 and (∃X)Q(X), where formula Q may contain bounded variables over the natural numbers but the variable X over sets of natural numbers remains free. 5 In fact an infinite run time hypercomputer can decide propositions which extend up the analytical hierarchy and can be defined by a ∆ 1 2 formula, see [9] Theorem 2.5. 6 α is an ordinal such that cumulative Lα of Gödel's constructive universe of sets is a model of Kripke-Platek set theory. 7 The enumeration is an interleaved enumeration of X and 2 ℵ − X.
2 ℵ − X is < ℵ + 1, where x is expressed as a binary sequence of length at most cardinal ℵ ≥ ℵ 0 and 2 ℵ is the set of all such binary sequences. Of the standard principles of Zermelo Fraenkel set theory, GCH is the only principle that can be cast in an explicitly information-theoretic way, but the Axiom of Separation and the Axiom Schema of Replacement limit the information in a set by limiting its size, and the Axiom of Foundation ensures that a set has a bounded amount of information (because every membership chain must terminate after finitely many steps).
There is a view that second-order Zermelo Fraenkel set theory and the universal hypercomputer that computes its unique class model 8 , V , are too powerful to be useful in mathematics. It is shown in Corollary 11 below that a universal hypercomputer computes GCH as true in V if an information minimization principle is true, by exploiting the link between V and the universal hypercomputer, i.e. that V is "the class of" the universal hypercomputer and the universal hypercomputer is "the computer of" V . The information minimization principle states that, for losslessly incompressible sets, to any hypercomputation that decides x ∈ X by enumeration of X and its complement there corresponds a hypercomputation that decides x ∈ X by enumeration of X and its complement that has the length of the minimum number of bits of information in x ∈ X and x / ∈ X. This information minimization principle is an expression of the fact that all sets and all membership relations can be hypercomputed and that a set and a relation contain a certain number of bits of information, and it does not matter how those bits are enumerated, as some enumeration of this number of bits will define the set and decide the truth of the relation for particular sets. A key claim of this paper is that the number of bits of information in the relation x ∈ X ⊆ 2 ℵ is ℵ. The argument for this claim (see Theorem 13) is that every set X can be replaced by a corresponding associated set of X, 2 ℵ (X), which is defined by hypercomputing the truth value of x ∈ X and appending the result (0 for False or 1 for True say) to x. It is clear that y ∈ 2 ℵ (X) can be always be decided in ℵ = o(ℵ) + 1 steps by enumeration, where o(ℵ) is the least ordinal of cardinality ℵ. One strong assumption in this argument is that all hypercomputations can be performed in the universe of associated sets (which can be mapped one-to-one and onto V , see Theorem 10). We can also say that it is assumed that 2 ℵ exists and that a corresponding 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer exists. These assumptions are equivalent to the existence and uniqueness of V . It is of course possible to identify a set X ⊆ 2 ℵ by means of a particular formula or predicate in > ℵ bits if a quantified variable in the formula ranges over say ⊆ 2 2 ℵ , but the set itself in V does not change and is still ⊆ 2 ℵ .
We could in fact define a set X of cardinality ≤ 2 ℵ as a set of sets x that can be defined in ≤ ℵ bits by enumeration such that the membership relation between x and X (see Theorem 10) can also be decided in ≤ ℵ bits by enumeration. The basic argument for GCH is that GCH is equivalent to the statement that x ∈ X ⊆ 2 ℵ can be decided by enumeration almost always in < ℵ+1 steps for infinite cardinal ℵ (see Theorem 9) and yet this statement is equivalent to the claim that the number of bits of information in the relation x ∈ X is ℵ. 8 There is of course a hierarchy of set models of second-order Zermelo Fraenkel set theory defined by taking the set theoretic universe, V , up to the level of each uncountable strongly inaccessible cardinal, see [10] for an interesting discussion of a modal-structural view of set theory.

What is a Universal Hypercomputer?
So far we have not defined a universal hypercomputer. We start with a hypercomputer that can compute truth in the initial levels ≤ α of von Neumann cumulative hierarchy of pure, well founded-sets, V. The proper class of all such hypercomputers can compute the truth of all propositions in V and forms a universal hypercomputer. This type of hypercomputer permits programs of infinite ordinal length, infinitely many registers and computations of infinite length, which is possible if the registers are left in a consistent state at limit ordinals during computations. In the following definitions we split out the number of registers, the length of computations and and the length of the program as separate parameters. Definition 1. A ℵ, , -hypercomputer, for cardinals ℵ and and ordinal , where ≤ ≤ ℵ, comprises the following elements: • ℵ-many Registers for storage of inputs, outputs and workings of a computation. For ease of exposition 9 there will be disjoint sets of registers for inputs, outputs and workings. Input registers are read-only and contain inputs in the hypercomputer's initial state. Working registers are read-write and receive a copy of the inputs when the program starts. Output registers receive a copy of the content of the working registers, are write-only by the program and contain the outputs of the program in the hypercomputer's halting state (see below). A register consists of an ordinal identifier and a data field, written R α for α < ℵ, which can contain 0 or 1. By default all registers are initialized with the value 0 (representing "empty"). Input registers will be written I α , working registers W α , and output registers O α . It is convenient to allow multiple disjoint sets of working registers, W β,α , to facilitate operations on data set, 10 and it will be assumed in this paper that working registers are partitioned into disjoint sets. 11 To avoid complexities associated with the 9 Separate input, working and output registers are not essential, as registers can always be moved around and working space created, but I hope their use makes the exposition easier to follow.
10 Disjoint sets of registers can be reproduced by coding the set of disjoint sequences { a 1,α , a 2,α · · · , a i<ℵ,α , · · · : α < ℵ} by the concatenation a 1,1 , a 2,1 , · · · , a i<ℵ,1 , · · · 0, 1 a 1,2 , a 2,2 , · · · , a i<ℵ,2 , · · · 0, 1 · · · 0, 1 a 1,α , a 2,α , · · · , a i<ℵ,α , · · · · · · with the marker 0, 1 placed after each successor and limit member of the sequence and having rules to skip over markers. 11 For example, take a program which has two states (other than the standard special states), 1 and 2, the standard introduction and conclusion for input and output being ignored for simplicity. In state 1 if the program reads a register W 1,α containing a 1, it writes a 1 in register W 2,1 and stays in state 1. In state 1 if the program reads a register W 1,α containing a 1, it moves right to W 1,α+1 and stays in state 1, while if W 1,α contains a 0 it writes a 0 in register W 2,1 and terminates by moving to the halting state, 2. When reading registers W 1,λ with limit ordinal λ, the program will be in the highest state achieved (i.e. 1 in practice) when reading registers W 1,α<λ and the value of any register W β,α≤λ after limit ordinal λ steps of the program will be the value of an eventually constant sequence W β,α for < λ steps or 1 otherwise. It can be seen that W 2,1 contains 1 if and only if every W 1,α for ordinal α < ℵ contains 1. The program implements infinite logical conjunction (i.e. infinite logical "and") of propositions with truth values stored in W 1,α . This program can be written formally as follows in the notation of this paper: 1, W 1 , 1, 2, 2 , 1 , 1, W 1 , 1, 8, 1 , 1 , 1, W 1 , 0, 1, 2 , 2 , 1, W 0 , 0, 12, 0 , 1 , 1, W 0 , 1, 12, 0 , 1 , 1, W 0 , 1, 0, 2 . The last three instructions implement the flag set to 1 in W 0,0 when the program completes, and moves the program to the halt state. Infinite "or" can be done similarly with the two state machine: in state 1, if the program reads a register W 1,α containing a 0 it writes a 0 to W 2,1 , moves to W 1,α+1 computability of functions that jump between registers, registers perform like infinite linear tapes of length ℵ terminated on the left, with R 1 being the register with lowest ordinal and only registers R α+1 and R α−1 , where they exist, being accessible from R α . W 0,0 is treated as a special register as it is set to 0 by default and set to 1 if a program (or subprogram) runs to completion, after o(ℵ) steps, where o(ℵ) is the least ordinal of cardinality ℵ. This register can be used as a "flag" to capture the output of the program.
• -many States which determine which action the hypercomputer takes and any output it produces. A state can be identified by an ordinal. There are at least two special states, an initial state, identified by the ordinal 0, where a program (see below) starts and a halting state where a program stops. The hypercomputer enters the halting state, i.e. stops, when none of the instructions (see below) applies, or when the computation length is reached (when the contents of W 0,0 are set to 1). Ordinary states are like line numbers in a hypercomputer program (see [12]), so from the initial state the program will enter the first ordinary state, 1 say, and as the number of instructions executed (i.e. the length of the computation) increases towards limit ordinal α, the program jumps to state α unless there is a state with a smaller least upper bound. 12 It makes sense not to be able to jump past a limit ordinal, so for successor ordinal state α only states with ordinal prevlim(α) ≤ β < nextlim(α) are accessible from α, where prevlim(α) is the preceding limit ordinal ≤ α and nextlim(α) is the next limit ordinal > α. • An initial configuration, comprising data loaded into the input registers, an initial state and an initial current register (I 1 by default and likewise W β,1 and O 1 when these sets of registers are accessed). • A program of length 13 which is a (in general transfinite) sequence of 5tuples Current State, Register Set, Symbol, Action, Next State , called program instructions, read as "if the hypercomputer is in Current State and the current register in the Register Set contains Symbol then do Action and move into Next State", where an Action may be to do nothing, write a 0 or 1 to a current register, R α , in any set of registers, to move left or right where possible, i.e. from R α to R α−1 or R α+1 if α is a successor ordinal and from R α to R α+1 otherwise, or set the current register to the 0-th register, i.e. R 0 . As these operations apply to each disjoint set of registers, I, W β , O, there are 11 instruction types (as "do nothing" applies to all registers and I cannot be written to). For definiteness, "do nothing" can be represented by 0, "write a 0" to the current register of W β by 1, β , "write a 0" to the current register of O by 5, "write a 1" to the current register of W β by 2, β , "write a 1" to the current register of O by 6, "move left" by 3 (for I ), 7, β and stays in state 1; if it reads a register W 1,α containing a 1 it writes a 1 to W 2,1 and moves to halting state 2. 12 It is of course possible to become stuck in a particular state and for the program not to output given a particular set of register values, but equally it is possible to loop back to the same state if the register value is 0 say, and then at the next limit ordinal for the program to read a 1, when the program may move to a different state. 13 The instructions can be grouped by state into a table of instructions. For ease of exposition, the program length will refer to the number of state entries in the table.
(for W β ) and 9 (for O ), "move right" by 4 (for I ), 8, β (for W β ) and 10 (for O ), and "reset register" by 11 (for I ), 12, β (for W β ) and 13 (for O ). Each program comprises a standard introduction which copies the input registers to working registers (i.e. a set of 5-tuples with source set of registers I and destination set of registers W 1 ), 14 a program that manipulates the working registers, and a standard conclusion which copies working registers to output registers (i.e. a set of 5-tuples with source registers W β and destination registers O). 15 It is not possible for humans to write down infinitely long programs, but it is possible to write program schemas. An example is a program schema for the logical conjunction of a set a registers of cardinality ℵ given by a finite program in footnote 11 could be written 1, is an ordinal parameter for the state and o(ℵ) is the halt state. 16 • many steps in the computation (see Definition 2).
• Output is the contents of the output registers when the program is in a halting state.
A hypercomputer will read a program, which will start in the initial state, run through its computation and terminate when it reaches a halting state. The output of the program is the contents of the hypercomputer's output registers.

Definition 2.
A computation is a sequence of steps of length that results in output given specific input.
To make this characterisation precise, a computation can be considered to take place in discrete time intervals indexed by ordinals. Following [12] a "step" can be taken to have three components: the current state at time α, written S α (R), a pointer to the ordinal index of the current register, H α (R), and the contents of all the registers (a "snapshot" of the computation), C α (R) : → {0, 1}, where R is a set of registers I, W β , O. Limit ordinal "steps" are special, as the principle (see [9]) will be adopted that if S α (R), H α (R) or C α (R) are eventually constant for α < λ, where λ is a limit ordinal, then by default S λ (R), H λ (R) or C λ (R)(ζ) for ζ < ℵ will take those constant values or else will take the limit of the least upper bounds, which will be C λ (R)(ζ) = 1 if C α<λ (R)(ζ) is not eventually constant and S λ (R) = λ and H λ (R) = R λ if S λ (R) and H λ (R) are otherwise unbounded. This is the "lim sup" construction (i.e. the limit of the least upper bounds). Recursive 14 A program to copy the registers from I and destination W 1 has one ordinary state, 1, and comprises the instructions 0, I, 0, 0, 1 , 0, I, 1, 0, 1 , 1, I, 0, 1, 1 , 1 , The sequence 1, W 0 , 0, 12, 0 , 1 , 1, W 0 , 1, 12, 0 , 1 , 1, W 0 , 1, 0, 2 will move the program to the halting state, 2, when it completes copying. 15 A program to copy the registers from W β and destination registers O has one ordinary state, 1, and comprises the instructions 0, The sequence 1, W 0 , 0, 12, 0 , 1 , 1, W 0 , 1, 12, 0 , 1 , 1, W 0 , 1, 0, 2 will move the program to the halting state, 2, when it completes copying. 16 Program schemas are concise, but finite programs suffice in the theorems below except for writing data input and output, where most data will need to be hard coded because there are only countably many program schemas if each αhas no be defined by a finite formula.
definitions for S α (R), H α (R) and C α (R) are given as follows (again based on [12]) 17 . Definition 4. A Turing machine (see [23]) is a < ℵ 0 , < ℵ 0 , < ℵ 0 -hypercomputer as it has ℵ 0 many registers but with only finitely many registers addressed in the program, and each program having finitely many states and instructions. Although a finite program may not halt, a function is usually considered computable if there are < ℵ 0 steps.

Definition 5.
A parallel ℵ, , -hypercomputer, for cardinals ℵ, and where ≤ ≤ ℵ, is a hypercomputer that can store data in the registers and process data from the registers in parallel. For the purposes of this paper, such a parallel hypercomputer will comprise ℵ−many serial ℵ, , -hypercomputers running independently in step but with the ability to use common read-only input registers and the capability of writing outputs to a set of registers through a second management program. 18 To be precise, there are ℵ sets of registers { I α,γ , W β,α,γ , O α,γ }, where γ < ℵ is an index of the set of registers and in fact an index of the 17 Koepke uses "lim inf" rather than "lim sup" because the programs he considers are finite, and it makes no sense to jump to an infinite limit ordinal state. 18 The general case is where the ℵ, , -hypercomputers are not independent of one another, but even in the general case the dependency can be made explicit by taking the output of a overall parallel program, and the working and output registers are disjoint, i.e.
For each I α,γ , W β<ℵ,α,γ , O α,γ there is a program, P γ , of length which runs disjoint computations based on input registers I α,γ for ≤ steps and produces any output in O α,γ for α < ℵ. 19 There may be a separate management program M(Q) that copies the contents of all registers O α,γ to the registers in the initial state of a separate parallel ℵ, , -hypercomputer and then runs a given program Q (= P γ ), that in the halting state contains the output of Q (if any). For ease of computation, it is assumed that parallel hypercomputers can be chained, the output from one parallel hypercomputer being the input to other parallel hypercomputers, and such a chain of hypercomputers is also a parallel hypercomputer. 20 Remark 6. For infinite ℵ a parallel ℵ, , -hypercomputer computes the same functions as a serial ℵ, × ℵ, × ℵ -hypercomputer, i.e. as a serial ℵ, ℵ, ℵhypercomputer, as can be seen by noting that ℵ computations can be interleaved rather than being performed in parallel. For the same reason, a parallel ℵ, ,hypercomputer is ≤ ℵ faster than a serial ℵ, , -hypercomputer.

Losslessly Compressed Sets
It was mentioned in section 1 that it is possible to identify the number of bits of information in a set x (expressed as a binary sequence that represents members of x as well as x) as the least length of the sequence which can be losslessly compressed from x. The question arises how we express sets as binary sequences. While it is possible to concatenate binary sequences representing members of a set X to represent X as a binary sequence, here we will fix an enumeration of X ⊆ 2 ℵ , x α : α < 2 ℵ (which exists by the Axiom of Choice), and for any subset Y ⊆ X form the binary ℵ-sequence b α : (y α ∈ Y → b α = 1) ∨ (y α / ∈ Y → b α = 0) , where the ordinal index of any member y ∈ Y is taken from the enumeration of X (which includes all members of Y ). This approach has the advantages that all binary 2 ℵsequences are represented, and some sets where membership is easily decided are clearly compressible. For example, 2 ℵ is represented as a 2 ℵ -sequence of 1s, while the empty set is represented as a 2 ℵ -sequence of 0s. Moreover, the representation of 2 ℵ − Y is formed from the representation of Y by swapping 0s for 1s. and vice versa A binary ℵ-sequence is losslessly compressible if it has an initial binary < ℵ-sequence followed by a terminal binary ℵ-sequence which comprises ℵ many repetitions of binary < ℵ-sequences, and is losslessly incompressible otherwise. To see that this is a reasonable definition, note that it is possible to create an ℵ-sequence by concatenating together with repetitions a set of < ℵ-sequences of cardinality ≤ ℵ. If the ℵ-sequence that results has period < ℵ, then the ℵ-sequence can be treated as parallel ℵ, , -hypercomputer as an input to a serial ℵ, , -hypercomputer or to another parallel ℵ, , -hypercomputer. 19 Instructions in a parallel hypercomputer have the form Index of Serial hypercomputer, Current State, Current Set of Registers, Symbol, Action, N extState , so that a program to copy input registers Iα,γ to working register W 1,α,γ (without the sequence to move the program into the halting state) is γ, 1, I, 0, 1, 1 , 1 , γ, 1, I, 1, 2, 1 , 1 ,  γ, 1, I, 0, 4, 1 , γ, 1, I, 1, 4, 1 , γ, 1, I, 0, 8, 1 , 1 , where α is the current register in the input registers and in the set W 1,γ in γ−th hypercomputer in the parallel set. 20 Allowing chains of parallel programs does not change the set of computable functions, but can be useful in practice. ℵ many repetitions of binary < ℵ-sequences, while if it has period ℵ then it cannot be represented by a < ℵ-sequence and thus is losslessly incompressible because, if a set does not change its cardinality on being losslessly compressed, it is treated as losslessly incompressible. The idea of a losslessly compressible ℵ-sequence is that the sequence can be replaced by a binary code for an initial < ℵ-sequence, a binary code for the repeated pattern and a separate binary code for the number of repetitions. The code for ℵ repetitions can be set to 0 and for any other number of repetitions r < ℵ the code can be set to the cardinal of the ordinal o(r) + 1.
There is a clear link between the notion of information defined above and Kolmogorov complexity (see [18] for example). Recall that Kolmogorov complexity of a set X is the least length of a computer program in a defined formal programming language which outputs X. But while Kolmogorov complexity is a powerful and well-researched approach to algorithmic complexity and to the study of randomness, in this paper the focus will be on binary ℵ-sequences that do not comprise ℵ many repetitions of binary < ℵ-sequences rather than sets which can be generated by a computable formula. The primary reason for this choice is that the compressibility of a sequence should only depend on patterns in the sequence and the sequence length and not on a representation in a formal programming language 21 . Another difference with the approach of Kolmogorov complexity is that Kolmogorov complexity minimizes program length, while here the emphasis is on minimizing the number of steps in the computation of a (serial hyper-)computer from a blank tape (or empty registers), compressing the input data, running the program and decompressing the output as necessary. 22 It will also turn out that the program length is equal to the number of steps in the information minimization principle below. In addition, just like in Kolmogorov complexity, we make use of losslessly incompressible binary sequences as a useful tool in proofs. To that end, we show that there are sufficient losslessly incompressible sets of every infinite cardinality. Proof. Firstly we recall that the number of bits in a set is always a cardinal number. Proceed by an argument by cases on the cardinality of the set: the infinite countable cardinal, ℵ 0 ; the infinite successor cardinal case; and the infinite limit cardinal case.
We first prove that almost all sets of cardinality ℵ 0 are losslessly incompressible. We can note that there are 2 ℵ0 possible binary ω-sequences, while there are only ≤ ℵ 0 ω-sequences with a finite initial binary sequence and an independently chosen terminal binary ω-sequence comprising a repeated finite binary sequence (since ( Y ⊆X,|Y |<ℵ0 |Y |) × ( Z⊆X,|Z|<ℵ0 |Z|) = ℵ 0 × ℵ 0 = ℵ 0 ). Hence almost all (2 ℵ0 − ℵ 0 = 2 ℵ0 ) sets of cardinality ℵ 0 (i.e. sets expressible as a ω-sequence) are losslessly incompressible. When = ℵ+1 is an infinite successor cardinal, then by a counting argument there 21 Using a universal Turing machine it can be shown that choice of programming language imposes a constant overhead in terms of program length when the program language is changed, see [8]. 22 For decision problems no decompression is needed.
When is an infinite limit cardinal, by a counting argument there are 2 possible binary -sequences, while there are α< 2 α losslessly compressible binary -sequences, where is the cardinal sum operator, because by induction there are 2 ℵ losslessly compressible sets for each infinite successor cardinal ℵ + 1 (see the successor cardinal case) and we can assume by hypothesis that there are α<‫ג‬ 2 α losslessly compressible binary ‫-ג‬sequences for limit cardinal ‫ג‬ < . We can show that α< 2 α < 2 by means of König's theorem. König's theorem states that i∈I j i < i∈I k i for I an index set, j i and k i are cardinals j i < k i , and is the cardinal product function. If I = , j i = 2 i and k i = 2 , then we have i< 2 i < (2 ) = 2 (see [11] Theorem 5.16ii). Hence almost all (2 − α< 2 α = 2 ) sets of cardinality (i.e. sets expressible as a -sequence) are losslessly incompressible.
Since all three cases have been been established, the lemma follows.

The Generalised Continuum Hypothesis as an Information-Theoretic Axiom
In this section we prove a theorem that shows that GCH is an informationtheoretic axiom. First, however we define the notion of interleaved enumeration for use in Theorem 9 et seq. Definition 8. An interleaved enumeration of two sets U and V is created by forming a new enumeration h from f an enumeration function for U and g is an enumeration function for V as follows: h α = f inf (α)+f in(α)/2 if ordinal α has a Cantor normal form 23 comprising an (possibly zero) infinite part inf (α), and an even finite part f in(α) (including 0) and h α = g inf (α)+(f in(α)+1)/2 if f in(α) is odd.
Theorem 9. GCH is equivalent to 24 the assertion that the amount of information needed to decide the relation x ∈ X by an interleaved enumeration of X or 2 ℵ − X is < ℵ + 1, for any given binary ℵ-sequence x of length at most cardinal ℵ ≥ ℵ 0 and X has cardinality ≤ 2 ℵ .
Proof. Assume that: a) ∅ ⊆ X ⊆ 2 ℵ , b) X has cardinality ℵ < c < 2 ℵ , c) Any x ∈ X is expressed as a binary sequence of length at most cardinal ℵ ≥ ℵ 0 , and d) The amount of information needed to decide the relation x ∈ X by an interleaved enumeration of X or 2 ℵ − X is < ℵ + 1. 23 The Cantor normal form is a representation of any ordinal in the form n<ω i=1 ω b i ×c i , where c i are positive integers and ordinals b i are such that b i > b j and bn ≥ 0 for i < j. 24 Strictly the inference from the information limitation principle to GCH is probabilistic (true almost always) in cardinality terms rather than logically necessary.
The proof is summarized in the tables below, where a means that the option is possible and × means that the option is impossible.   Table 1 and proof references Proof references: 1.
x ∈ X would almost always be decided in ≥ ℵ + 1 bits for a given enumeration of X, contradicting assumption d).

An Information Minimization Principle
This information minimization principle is an expression of the fact that all sets and all membership relations can be hypercomputed and that a set and a relation contain a certain number of bits of information, and it does not matter how those bits are enumerated, as some enumeration of this number of bits will define the set and decide the truth of the relation for particular sets. We could in fact define a set X of cardinality ≤ 2 ℵ as a set of sets x that can be defined in ≤ ℵ bits by enumeration and the membership relation between x and X (see Theorem 10) can be decided in ≤ ℵ bits by enumeration.
This may seem in conflict with the finite case, but membership of a finite set of 2 n members for n ≥ 1 (which can be taken to be natural numbers or binary sequences representing natural numbers) can be decided in ≤ n + 1 bits by using a binary search algorithm if X and the complement of X are ordered in ascending order, say X = {x(i) : 1 ≤ i ≤ 2 n } and x(i) = −1 if x(i) is not defined. Then to decide whether x ∈ X, follow the algorithm in the following pseudo-code, where all variables are natural numbers.

End loop return False
This program runs for ≤ n + 1 steps in terms of the number of members of X enumerated. Of course the binary search could also be applied to the complement of X, but the run time is again ≤ n + 1 steps in an enumeration. While the efficient enumeration of X or the complement to decide x ∈ X relies on specific linear orderings of X, the search process defines a binary expansion (whether the midpoint is to the "left" or "right" of x in the ordering) of any x ∈ 2 n with a final member of the sequence representing the decision whether x ∈ X or not. In fact the binary expansion of "left" and "right" labels mutually defines the sequence of midpoints. This is suggestive of the approach in Theorem 9 that an efficient enumeration represents x ∈ X as a binary ℵ-sequence representing x followed by a decision whether x ∈ X. It lends support to the view that an efficient enumeration of X ⊆ 2 ℵ is always representable as a binary ℵ-sequence representing x followed by a decision whether x ∈ X. More generally, it is also possible to use a midpoint construction where X is a dense subset of a closed interval in the standard topology of the real line, say [0, 1], by choosing the midpoint of the interval if the midpoint is a member of the interval or choosing a member of the set near the midpoint (using the Axiom of Choice) otherwise. Then the ω-sequence of near-midpoints will converge to the point x in the interval (unless the near-midpoint algorithm chooses x at some finite stage in the enumeration), which may or may not be a member of X.
By the definition of the number of bits of information, for every set X ⊆ 2 ℵ there is a losslessly compressed set Y (i.e. cardinality |Y | ≤ |X|) that contains the same information as X. Let us assume that we can well-order a binary 2 ℵ -sequence in a monotonic way with the constant sequence with the smaller cardinality as the initial sequence. This is possible by choosing members of the sequence with value 0 and building a sequence and doing the same for members of the sequence with value 1, and then concatenating them with the smallest set first. Otherwise if the sequences have equal length of 2 ℵ a binary 2 ℵ ×2-sequence will be needed. Then we see that the maximum lossless compression occurs when one of the constant sequences is empty, and in general lossless compressibility will depend on the cardinality of the smaller constant sequence. But is this the minimum amount of bits needed to decide x ∈ X? The answer in general is "no" because each x has a representation as a binary ℵ-sequence and it possible to add an extra bit to every binary ℵ-sequence to indicate whether x ∈ X or not. Lossless compressibility adds complication to computation of the minimum steps in the computation of x ∈ X because in general the index of x in an arbitrary binary 2 ℵ -sequence will need to be represented as an ordinal < 2 ℵ but when the repeated pattern is a constant value then x ∈ X can be determined in a number of bits ≤ , where is the length of the initial sequence before the repeated pattern. If, however, we consider only losslessly incompressible sets X we can state a principle of information minimization as follows: 26 Principle of Information Minimization: For all losslessly incompressible sets X ⊆ 2 ℵ and x ∈ 2 ℵ and for all relations x ∈ X there is a minimum amount of information µ such that if a ν, ν, ν -hypercomputer a can decide x ∈ X in ≤ ν steps by any enumeration of X and 2 ℵ − X, it follows that a µ, µ, µhypercomputer can decide x ∈ X in µ ≤ ν steps by an interleaved enumeration of X and 2 ℵ − X.
a Numbers of registers and states that are greater than the length of the computation are not used; hence the number of states and registers are set equal to the length of the computations.
The argument for the Principle of Information Minimization is that an enumeration that locates x in an interleaved way in X and 2 ℵ − X (which is efficient for infinite sets X) should take a number of steps no more than the number of bits of information in x ∈ X. It should be noted that if X is losslessly incompressible then so is 2 ℵ − X as any pattern in a binary 2 ℵ -sequence representing X will corresponding to a bit-flipped pattern in 2 ℵ − X. As further motivation for this argument, we can, as noted above, regard the shortest enumeration of a member x off a set X as an optimal search algorithm for x. That is to say, each successive bit of x 26 This view does not contradict the speed up theorems in formal axiomatic systems, see [2], because axiomatic systems constrain the proof method to a finite sequence of computation steps, albeit from a number of different axioms that depend on the axiom system. corresponds to a choice of (nested) intervals in a linear order of X. Each interval can be represented by a member of the interval, and after the number of bits equal to the length of x, ℵ, x will be definitely be located or not, i.e. x ∈ X will be decided by enumeration. This motivation will not be pursued further in this paper because it needs the development of topological arguments to explain the idea more fully. , In Theorem 10 below we show (highly non-constructively) that the number of bits of information in the relation x ∈ X for X ⊆ 2 α is < ℵ + 1. Let us take X ⊂ 2 ℵ to be a losslessly incompressible set of cardinality 2 ℵ which is entangled in losslessly incompressible set 2 ℵ − X, i.e. each ℵ-sequence in X is covered by ℵ-sequences in 2 ℵ − X and vice versa. 27 The most interesting case 28 is when both X and 2 ℵ − X have cardinality 2 ℵ . X can be constructed by the Axiom of Choice, making sure that for each initial < ℵ-sequence, s, one ℵ-sequence x that has s as an initial < ℵ-sequence is selected to be put in X, and one ℵ-sequence y = x that has s as an initial < ℵ-sequence is selected to be put in 2 ℵ − X; and dividing other members of 2 ℵ equally among X and 2 ℵ − X (by well-ordering 2 ℵ − S, where S is the set of ℵ-sequences already selected, and alternately putting members of the well-order in X and 2 ℵ − X, putting limit ordinal members in X for definiteness, since the number of successor ordinals is the same as the number of limit ordinals < 2 ℵ ). It is shown in Lemma 7 that almost all sets of infinite cardinality are not losslessly compressible in terms of number of bits of information, so we can choose two incompressible sets of cardinality 2 ℵ (as the constraint of X and 2 ℵ − X each containing a dense subset of cardinality ℵ does not affect the choice of other members of X and 2 ℵ − X). Corollary 11 shows that GCH follows from Theorem 9 for X and 2 ℵ − X incompressible.
Theorem 10. A universal hypercomputer computes the minimal amount of information needed to decide the relation x ∈ X, where x is any binary sequence of length at most cardinal ℵ ≥ ℵ 0 and X has cardinality ≤ 2 ℵ , in V as ℵ.
Proof. For a set X that consists of binary ℵ-sequences, associate to every binary ℵ- Call the associated set 2 ℵ( (X). Properties of sets can be recovered from the associated sets, e.g.
Associated sets are sets where membership is always decided, which is true of membership computed by a universal hypercomputer (see Theorem 13) 29 . If then a set X is identified with its associated set 2 ℵ( (X), 30 then any x ∈ X can be decided 27 We can also say that both X and 2 ℵ − X are dense in 2 ℵ . 28 The other cases are dealt with in Corollary 11. 29 It is possible to take a topological approach to the hypercomputation of x ∈ X. The set X can be given a topology where basic open sets are sets of ℵ-sequences that extend some initial < ℵ-sequence. It can be seen that basic open sets are closed as well as open (because they have their own limit points and no limit points belonging to their complement in X). The intersection of basic clopen (closed and open) sets that are neighbourhoods of x have intersection x if x ∈ X and is empty otherwise. After ℵ steps a hypercomputer can decide whether x ∈ X or not. Replacement of sets by associated sets is a clearer hypercomputational approach to deciding set membership than a topological approach.
30 Associated sets obey the standard rules of intersection, union and complement but only functions from one set to another that are allowed are those that preserve the o(ℵ) + 1-th member in steps of cardinality ≤ ℵ, i.e. in < ℵ+1 bits, by enumerating the o(ℵ)+1-sequence y ∈ 2 ℵ (X) corresponding to x, and checking its o(ℵ) + 1-th member.
x ∈ X cannot be decided in < ℵ steps in general because x requires ℵ bits to be specified if x is a losslessly incompressible binary ℵ-sequence (which always exist for infinite ℵ by Lemma 7).
Corollary 11. GCH is computed as true in V if the Information Minimization Principle holds.
Proof. By Theorem 10 ℵ is the minimum number of bits needed to decide x ∈ X. Choose X ⊂ 2 ℵ and 2 ℵ − X to be losslessly incompressible sets of cardinality 2 ℵ (see Remark 8). Since X and 2 ℵ − X are losslessly incompressible sets, it follows that we can apply the Information Minimization Principle. Then, since a 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer can decide x ∈ X by interleaved enumeration of X and 2 ℵ − X in < 2 ℵ bits, it follows from the Information Minimization Principle that a ℵ + 1, ℵ + 1, ℵ + 1 -hypercomputer can decide x ∈ X by interleaved enumeration 31 of X and 2 ℵ − X in (any ordinal of cardinality) ℵ steps, i.e. the number of steps is < ℵ + 1 bits. Hence 2 ℵ = ℵ + 1 follows directly from Theorem 9; or we can note that we have x ∈ X if and only x is in an interleaved enumeration of X and 2 ℵ − X in < 2 ℵ steps (since an interleaved enumeration can be created from enumerations of X and 2 ℵ − X, see Definition 8) only if x is in an interleaved enumeration of X and 2 ℵ − X in < ℵ + 1 steps for losslessly incompressible X and 2 ℵ − X. It follows that 2 ℵ ≤ ℵ + 1, and ℵ + 1 ≤ 2 ℵ by Cantor's theorem. Other cases are where X and 2 ℵ − X are losslessly incompressible sets and one has cardinality ≤ ℵ (including being empty or being countable); and where X and 2 ℵ − X are incompressible sets and one of X or 2 ℵ − X and has cardinality ℵ < c < 2 ℵ . The former case shows that x ∈ X can be decided in ≤ ℵ steps, which is consistent with Theorem 9. The latter case is shown by Theorem 9 to be impossible (since x ∈ X can be decided in < c or < 2 ℵ steps, leading to c = 2 ℵ = ℵ + 1). Hence we have shown GCH is computed as true in V based on Theorem 10.
Remark 12. The result in Theorem 10 is highly non-constructive, and relies on there existing a set Y which corresponds to set X ⊆ 2 ℵ such that Y is a set of o(ℵ) + 1-sequences which computes the decision problem for every x ∈ X and appends the results to the ℵ-sequence for x in 2 ℵ . This set Y , or 2 ℵ (X) as it was called in Theorem 10, is not computable in general by a finite computer, but needs a (universal) hypercomputer. It is possible, as noted above, to reject this view on the grounds of its computational or ontological assumptions (that every set is computable and every relation decidable). It is also possible to substitute other bounds on the decision problem for x ∈ X, such as linking sets to formulas of fixed bounded quantifier complexity,; but those bounds of course would also need motivation. It is also worth noting that Theorem 10 also leads to a very nice structure for, for example, the real numbers. Two entangled uncountable sets of of the binary sequence representing set x in the domain of the function. However, it is true that every set that exists in the Von Neumann universe of sets, V , has an associated set, because 2 ℵ( (X) can always be hypercomputed from X. 31 The program for interleaved enumeration will loop through members of X and 2 ℵ − X in a specific order and exit and return true when it matches a specific ℵ-sequence x (which it always does in < 2 ℵ steps). It is identical to the program for (∃y)R(y) ∧ ∃y)S(y) in Theorem 13 below with R(y) = (x = y ∧ y ∈ X).and S(y) = (x = y ∧ y ∈ 2 ℵ − X), although we only need to load in ℵ + 1 members of X and 2 ℵ − X in light of the Information Minimization Principle.
real numbers are either one countable set entangled with an uncountable set of real numbers (viz. a continuum) or two entangled continua. 32 6. Results about the Universal hypercomputer Theorem 13. A serial 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer can compute a) the truth of firstorder propositions with quantification over sets that require ≤ ℵ bits of information to define, b) the truth of first-order propositions like a) but with the addition of allowing set membership of sets that require ≤ 2 ℵ bits of information to define, and c) a serial 2 2 ℵ , 2 2 ℵ , 2 2 ℵ -hypercomputer can compute the truth of second-order propositions about sets that require ≤ ℵ bits of information to define.
Proof. a) To start, the truth of recursive relations involving finitely many sets that require ≤ ℵ bits of information to define (including the standard logical operators ∧, ∨,→, ↔ and ¬) can be decided by a program with finitely many instructions in ≤ ℵ steps because the recursive relation generates a finite program and ≤ ℵ steps are needed, one for each bit. Then to decide (∀x)R(x) for x a set that requires ≤ ℵ bits of information to define and R recursive, loop through the set of all sets that require ≤ ℵ bits of information to define, run the program for R(x) in disjoint register sets in series, and then copy the results (0 or 1, i.e. false or true) to another disjoint set of registers, the computation having 2 ℵ steps 33 . To "loop through" the quantification domain, coding can be used to detect in finitely many instructions which registers have been accessed by the program, 34 and the least unaccessed member of the set can be accessed next 35 . To create and load all sets that require ≤ ℵ bits of information to define requires a program of length ≤ 2 ℵ because there are ≤ 2 ℵ such sets to be computed, each requiring ≤ ℵ instructions. The conjunction ("and") of the truth values of R(x) is then computed by a finite program (see footnote 11 for the outline of a finite program to compute the truth value of a conjunction), and (∀x)R(x) is true if and only if the conjunction has value 1 (true). (∃x)R(x) can be decided similarly using disjunctions ("or") rather than conjunctions. By induction on quantifier complexity the truth of any firstorder proposition about sets that require ≤ ℵ bits of information to define (with a recursive quantifier free formula) can be decided by a 2 ℵ , < ℵ 0 , 2 ℵ -hypercomputer given a set of sets that require ≤ ℵ bits of information to define. If the loading of the input is included, a serial 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer suffices to compute the truth of any first-order quantified proposition about sets that require ≤ ℵ bits of information to define.
32 Of course the topological properties of the two entangled continua may be different, for example a Cantor set and an open dense continuum. 33 Any set that requires ≤ ℵ bits of information to define can be either be a member or not a member of the set of such sets; hence the cardinality of the set of all sets that require ≤ ℵ bits of information to define, X say, is the same as the set of all functions ℵ → 2, i.e. 2 ℵ . Hence the total number of steps to loop through every member of X is ℵ × 2 ℵ = 2 ℵ . 34 If a sequence a 1 , a 2 , · · · , a i<ℵ , · · · of length 2 ℵ , where a i is a member of the quantification domain and a binary sequence of length < ℵ + 1, is coded as a 1 , 1, a 2 , 1, · · · , 1, a i<2 ℵ , 1, · · · , by placing a 1 marker after every successor and limit member of the sequence, then the 1 can be replaced with 0 if the previous register has been accessed by the program. The program can proceed until it finds a register succeeded by a 1.
35 Looping requires one new state, which acts as a label for the start of the loop and which which is the next state for instructions in the loop after the program for R(x) has run. b) To show that a first-order quantified proposition with quantification over sets that require ≤ ℵ bits of information to define and with the addition of specific sets that require ≤ 2 ℵ bits of information to define can also be computed by a serial 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer, we note that a serial 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer can compute any set that require ≤ 2 ℵ bits of information to define by starting with a blank tape (i.e. all 0 s) and running a program of length 2 ℵ to write a value (0 or 1 ) to each register. Membership of a set, x ∈ X, where each x must take ≤ ℵ bits to define to be consistent with a), 36 can therefore be computed by a serial 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer by looping through the set X with current value y ∈ X and checking whether y = x. The inductive argument in a) above can then be applied to show that a serial 2 ℵ , 2 ℵ , 2 ℵ -hypercomputer can compute the truth of any first-order proposition with quantification over sets that require ≤ ℵ bits of information to define and which have set membership of sets that require ≤ 2 ℵ bits of information to define.
c) The truth of a second-order proposition of set theory with quantification over sets that require ≤ 2 ℵ bits of information and sets of sets that require ≤ ℵ bits of information can be decided by "looping through" every set of sets that require ≤ ℵ bits of information, 37 which requires 2 2 ℵ registers and 2 2 ℵ steps with a finite program and which depends on 2 2 ℵ instructions to create and "load" the data, i.e. the set of sets of sets that require ≤ ℵ bits of information.
Theorem 14. A parallel 2 ℵ , ℵ, ℵ -hypercomputer can compute a) the truth of firstorder propositions with quantification over sets that require ≤ ℵ bits of information to define, b) the truth of first-order propositions like a) but with the addition of allowing set membership of sets that require ≤ 2 ℵ bits of information to define, and c) a parallel 2 2 ℵ , ℵ, ℵ -hypercomputer can compute the truth of second-order propositions about sets that require ≤ ℵ bits of information to define. a) Note that a parallel 2 ℵ , ℵ, ℵ -hypercomputer can write 2 ℵ sets that require ≤ ℵ bits of information to define into the registers in parallel. Proceed by induction with the hypothesis that a parallel 2 ℵ , ℵ, ℵ -hypercomputer can compute the truth of first-order quantified propositions of sets that require ≤ ℵ bits of information to define, noting that for the basis case of a recursive relationship between finitely many sets that require ≤ ℵ bits of information to define it takes ≤ ℵ instructions and ≤ ℵ steps to write finitely many sets that require ≤ ℵ bits of information to define to a set of registers and then finitely many instructions and ≤ ℵ steps to compute the recursive relationship for those sets. For the induction step, note that for (∀x)R(x) or (∃x)R(x), 2 ℵ sets that require ≤ ℵ bits of information to define can be loaded by a parallel 2 ℵ , ℵ, ℵ -hypercomputer across 2 ℵ disjoint sets of 2 ℵ registers and the quantification can be parallelised by running a (finite) program for deciding R(x) in parallel in ℵ steps, for (∀x)R(x) writing 1 to an output register of the management program initially and then writing 0 to the output register if any of the R(x) computes as false, while for (∃x)R(x) writing 0 to an output register initially and then writing 1 to the output register if any of the R(x) computes as true. 36 x ∈ 2 ℵ as x takes ≤ ℵ bits to define. 37 Note that a marker such as 1, 0, 1 can be added to each set of sets that require ≤ ℵ bits of information to define in the sequence of registers. b) If we add propositions involving membership of ≤ 2 ℵ specific sets, assumed for consistency with a) to consist of members which have ≤ ℵ bits to define, then to write a specific set requires a parallel 2 ℵ , ℵ, ℵ -hypercomputer if each disjoint set of 2 ℵ registers contains one set that requires ≤ ℵ bits of information to define. 38 Testing membership of a specific set of sets that require ≤ ℵ bits of information to define, r, requires matching r against 2 ℵ disjoint sets of registers which contain one set that requires ≤ ℵ bits of information to define, s α<2 ℵ , which can be done in parallel with a finite program in ℵ steps as follows. Use r and s α from the input registers and create a set of working registers, D α<2 ℵ , with one register each, written W α , in 1 step and with a finite program writing 1 to each W α in parallel. For r and each s α , for ordinal β < ℵ perform the operation (r) β ↔ (s α ) β 39 in parallel, which returns 1 if (r) β = (s α ) β and 0 otherwise; and if the result is 0 write 0 to W α and then halt the program; otherwise write 1 to W α and then move right one register along r and s α to (r) β+1 and (s α ) β+1 . At limit ordinals λ, proceed as normal by performing the operation (r) λ ↔ (s α ) λ . 40 c) Each of a maximum of 2 2 ℵ sets of sets that require ≤ 2 ℵ bits of information to define can be represented as specific sets when computing the truth of first-order quantified propositions involving such sets. Put more formally, since a parallel 2 ℵ , ℵ, ℵ -hypercomputer can compute the truth of a first-order quantified proposition with quantification over sets of sets that require ≤ ℵ bits of information to define with the addition of membership of specific sets that require ≤ 2 ℵ bits of information to define, if R(X), for X a set of sets that require ≤ ℵ bits of information to define, is a formula of set theory with free variable X, then (∀X)R(X) can be computed in parallel across 2 2 ℵ disjoint sets of 2 ℵ registers by writing 1 to an output register of the management program initially and then writing 0 if any of R(X) is false; and for (∃X)R(X) by writing 0 to an output register initially and then writing 1 if any of R(X) is true. By induction on quantifier complexity of a second-order predicate A(X), since the parallel computation adds 2 steps and needs a finite program to implement A(X) on each parallel hypercomputer, it can be seen that a parallel 2 2 ℵ , ℵ, ℵ -hypercomputer can compute the truth of secondorder quantified propositions about sets that require ≤ 2 ℵ bits of information to define. 38 It is assumed that the ≤ ℵ bits are presented serially and cannot be parallelised, for example by a recursive relationship. 39 That is ((r) β ∧ (sα) β ) ∨ ((¬r) β ∧ (¬sα) β ). 40 To implement the pseudo-code as a program, it is possible to use a hypercomputer with three ordinary states, 2,3,4, an initial state, 1, a halting state, 5, with the following instructions, assuming that the program starts in state 1, that two sets that require ≤ ℵ bits of information to define are for simplicity stored in W 1,α<ℵ,γ and W 2,α<ℵ,γ , the result of bit-wise comparison of the sets that require ≤ ℵ bits of information to define is stored in W 3,1 . A suitable program is γ, 1, W 1 , 0, 2, 3 , 4 , γ, 1, W 1 , 1, 2, 3 , 4 , γ, 4, W 1 , 0, 8, 1 , 3 , γ, 4, W 1 , 1, 8, 1 , 2 , γ, 3, W 2 , 1, 1, 3 , 5 , γ, 2, W 2 , 0, 1, 3 , 5 , γ, 3, W 2 , 0, 8, 1 , 4 , γ, 2, W 2 , 1, 8, 1 , 4 , γ, 1, W 0 , 0, 12, 0 , 1 , γ, 1, W 0 , 1, 12, 0 , 1 , γ, 1, W 0 , 1, 0, 5 .
The reason that the state with the main loop is the highest ordinary state is 4 is to allow the program to start in the main loop at limit ordinals. It can be seen that the program will either halt in state 5 with output 0 or in state 4 with output 1 when the computation runs to completion (i.e. at step o(ℵ)).
Remark 15. An ordinal hypercomputer is very powerful indeed; [12,14] show that, with a finite program and a set of registers indexed by all bounded sets of ordinals, the class of all ordinal computable sets of ordinals that can be computed from finitely many ordinal parameters is Gödel's constructible set universe L. This result shows that with finite programs only sets of ordinals definable by formulas in the language of set theory can be computed using an ordinal hypercomputer. In general sets of size ℵ will not be definable by a finite program, and we note that the construction of a set of size ℵ requires a serial ℵ, ℵ, ℵ -hypercomputer or a parallel ℵ, 1, 1 -hypercomputer 41 . We have seen that the class of all serial 2 2 ℵ , 2 2 ℵ , 2 2 ℵ hypercomputers or parallel 2 2 ℵ , ℵ, ℵ -hypercomputers computes truth in the set theoretic universe V for first-order and second-order propositions of set theory with finitely many quantifiers. If we allow a parallel hypercomputer to have ≤ 2 ℵ parallel hypercomputers chained together, then to compute a predicate of length with quantifiers, the program will have length and will have steps; hence a parallel 2 2 ℵ , , -hypercomputer will suffice. But from the point of view of standard second-order set theory with finitely long predicates and finitely many quantifiers, the class of all parallel 2 2 ℵ , ℵ, ℵ -hypercomputers computes the set of all true propositions.