The OEIS and its potential for expansion

Although the very most important sequences in mathematics are already in the OEIS, there remain a large number of sequences still not in the OEIS, and this is still after disregarding sequences that can't be added to the OEIS.

Considerations of the infinite

The set of all integer sequences (ordered lists, i.e. tuples, with finite or countably infinite count of finite integer members) has cardinality $\scriptstyle {\aleph _{0}}^{\aleph _{0}}\,$ since there is a countable infinity, $\scriptstyle \aleph _{0}\,$ (read aleph-naught; also aleph-null or aleph-zero), of finite integers and we can independently choose up to a countable infinity, $\scriptstyle \aleph _{0}\,$, of finite integer members. Normally, the term infinite sequence refers to a sequence which is infinite in one direction, and finite in the other, i.e. the sequence has a first element (well-ordered), but no last element (a singly-infinite sequence). A doubly-infinite sequence is infinite in both directions, i.e. it has neither a first nor a final element (not well-ordered). Singly-infinite integer sequences are functions from the natural numbers $\scriptstyle \mathbb {N} \,$ to the integers $\scriptstyle \mathbb {Z} \,$, whereas doubly-infinite integer sequences are functions from the integers $\scriptstyle \mathbb {Z} \,$ to the integers $\scriptstyle \mathbb {Z} \,$. Doubly-infinite integer sequences are not included in the OEIS (all OEIS sequences having a first element) although we may sort of include them by reordering them via the mapping $\scriptstyle \lfloor n/2\rfloor *(-1)^{n}\,$ which maps $\scriptstyle \{1,2,3,4,5,...\}\,$ to $\scriptstyle \{0,1,-1,2,-2,...\}\,$ (see A001057). Since $\scriptstyle {\aleph _{0}}^{\aleph _{0}}\,=\,2^{\aleph _{0}}\,=\,c\,$, the cardinality of the set of integer sequences is the same as the cardinality $\scriptstyle 2^{\aleph _{0}}\,$ of the power set of the set of integers and the cardinality of the set of real numbers, e.g. cardinality $c\,$ of the continuum. This is an uncountable infinity, the first uncountable infinity $\scriptstyle \aleph _{1}\,$ if we assume the truth of the Continuum Hypothesis, which has been proved independent of the Zermelo-Fraenkel axioms together with the axiom of choice, referred to as ZFC.

An integer sequence is definable, if there exists some finite length predicate (finite length string of symbols chosen from a finite alphabet) $\scriptstyle P(x)\,$ which is true for that integer sequence $\scriptstyle x\,$ and false for all other integer sequences. Therefore, the set of definable sequences is countable (with cardinality equal to that of the set of integers, $\scriptstyle \aleph _{0}\,$). Almost all integer sequences are thus undefinable.

An integer sequence is (Turing) computable if there exists a halting algorithm (a finite string of symbols chosen from a fixed alphabet) using finite resources (finite count of discrete computation steps, finite count of discrete memory information units) which given $\scriptstyle n\,$, calculates $\scriptstyle a_{n}\,$, for all $\scriptstyle n\,\geq \,1\,$. Therefore, the set of computable sequences is countable (with cardinality equal to that of the set of integers, $\scriptstyle \aleph _{0}\,$). Almost all integer sequences are thus uncomputable, making the computable sequences a proper subset of the definable sequences: there exist definable but uncomputable sequences. Some uncomputable sequences might have some members which are actually computable, making those sequences partially computable, so to speak. The computable sequences very likely have measure 0 among the (at least) partially computable sequences, which themselves very likely have density 0 among the definable sequences.

Examples of definable but uncomputable sequences (although their first few members are computable) are:

• A060843, Busy Beaver problem: maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting.
• A028444, Busy Beaver sequence, or Rado's sigma function: maximum number of 1's that an n-state, 2-symbol, 5-tuple Turing machine can print on an initially blank tape before halting.
• A004147, Number of n-state Turing machines which halt.
• A079365, Binary expansion of the Chaitin Omega number $\scriptstyle \Omega _{U}\,$.

Now, there is up to $\scriptstyle \aleph _{0}\,$ families (of up to $\scriptstyle \aleph _{0}\,$ families... [with up to an arbitrarily large but finite count $\scriptstyle k\,$ of such levels]) of up to $\scriptstyle \aleph _{0}\,$ integer sequences with up to $\scriptstyle \aleph _{0}\,$ members of arbitrarily large but finite size, which implies that we have up to $\scriptstyle {\aleph _{0}}^{(k+2)}\,=\,\aleph _{0}\,$ members (of arbitrarily large but finite size) to calculate and store...

With a Turing machine equivalent computer we can calculate any finite count of members of any finite count of families (of any finite count of families... [with any finite count $\scriptstyle k\,$ of such levels]) of any finite count of integer sequences. Of course, at any point in time our actual computing resources (maximal allowable computation steps and information units) will have an upper bound, which for the last 45 years (since 1965) have been growing exponentially (according to Moore's law, e.g. doubling approximately every 18 months). A cheap 2 TB hard drive could store up to 1 million sequences (with an average of 2 MB per sequence); for $50,000 we could store 1 billion sequences at $100 per 4 TB.

Now, let's get speculative and assume that we can circumvent many fundamental laws and limitations of physics (e.g. atomic structure of matter, speed of light, Heisenberg uncertainty principle, Planck time, Planck length, Von Neumann-Landauer limit...) and consider the idea of hypercomputation (super-Turing computation).

The hypercomputing paradigm allows us to do a countably infinite ($\scriptstyle \aleph _{0}\,$) number computation steps in a finite amount of time (e.g. with a convergent time hyperprocessor) and the means of storing a countable infinity ($\scriptstyle \aleph _{0}\,$) of information units in a finite amount of space.

A hyperprocessor (a convergent time processor, also called Accelerated Turing machine or Zeno machine) might execute the first CPU cycle in 1/2 second, after which each following CPU cycle would take half the time of the preceding CPU cycle, for a total of $\scriptstyle \aleph _{0}\,$ CPU cycles in 1 second. The $\scriptstyle n\,$^th CPU cycle, $\scriptstyle n\,\geq \,0\,$, would then start at time $\scriptstyle 1-1/2^{n}\,$ second and last $\scriptstyle 1/2^{n+1}\,$ second.

A hypermemory/hyperstorage (convergent space memory/storage) might store the first bit in 1/2 cm³, after which each following bit would need half the space of the preceding bit, so begetting a countable infinity ($\scriptstyle \aleph _{0}\,$) of bits in 1 cm³. Assuming a constant area of 1 cm², the $\scriptstyle n\,$^th bit, $\scriptstyle n\,\geq \,0\,$, would then be stored at location starting at $\scriptstyle 1-1/2^{n}\,$ cm over a length of $\scriptstyle 1/2^{n+1}\,$ cm.

We would then need to use a Gödel numbering storage addressing scheme to store, for each of the $\scriptstyle \aleph _{0}\,$ definable integer sequences, the sequence definition, its properties, its algorithm of arbitrary large but finite complexity and the resulting up to $\scriptstyle \aleph _{0}\,$ computable members of arbitrary large but finite size from the set of integers. We would also need to use a Gödel numbering processor dispatching scheme to calculate, for each of the $\scriptstyle \aleph _{0}\,$ definable integer sequences, the up to $\scriptstyle \aleph _{0}\,$ computable members.

There still remains the issue of discovering and/or inventing a countable infinity of definitions and algorithms (for all the definable and partially computable (i.e. computable at least for some members) integer sequences)! Unless there exists a meta-algorithm to generate the $\scriptstyle \aleph _{0}\,$ definitions and algorithms for all the definable and at least partially computable integer sequences, we are out of luck...

It is trivial to create $\scriptstyle \aleph _{0}\,$ sequences (which is infinitely times more than the 200,000+ sequences in the OEIS) Here are many examples:

• the family of constant sequences, $\scriptstyle a,(a)\,\in \,\mathbb {Z} \,$, which contains $\scriptstyle \aleph _{0}\,$ sequences;
• the family of arithmetic sequences, $\scriptstyle an+b,(a,b)\,\in \,{\mathbb {Z} }^{2}\,$ with $\scriptstyle a\,\neq \,0\,$, which contains $\scriptstyle {\aleph _{0}}^{2}\,=\,\aleph _{0}\,$ sequences;
• the family of quadratic sequences, $\scriptstyle an^{2}+bn+c,(a,b,c)\,\in \,{\mathbb {Z} }^{3}\,$ with $\scriptstyle a\,\neq \,0\,$, which contains $\scriptstyle {\aleph _{0}}^{3}\,=\,\aleph _{0}\,$ sequences;
• the family of cubic sequences, $\scriptstyle an^{3}+bn^{2}+cn+d,(a,b,c,d)\,\in \,{\mathbb {Z} }^{4}\,$ with $\scriptstyle a\,\neq \,0\,$, which contains $\scriptstyle {\aleph _{0}}^{4}\,=\,\aleph _{0}\,$ sequences which obviously generalizes to the super-family of algebraic sequences, which contains $\scriptstyle \aleph _{0}\,$ families of sequences;
• the family of $\scriptstyle k\,$-gonal (2D figurate numbers,) $\scriptstyle k\,\geq \,3\,$, which contains $\scriptstyle \aleph _{0}\,$ sequences;
• the family of $\scriptstyle k\,$-hedral (3D figurate numbers,) $\scriptstyle k\,\geq \,4\,$, which contains $\scriptstyle \aleph _{0}\,$ sequences;
• the family of $\scriptstyle k\,$-choron (4D figurate numbers,) $\scriptstyle k\,\geq \,5\,$, which contains $\scriptstyle \aleph _{0}\,$ sequences which obviously generalizes to the super-family of $\scriptstyle k\,$-nD-topal (nD figurate numbers), $\scriptstyle k\,\geq \,n+1\,$, sequences, which contains $\scriptstyle \aleph _{0}\,$ families of sequences;
• the family of power ($\scriptstyle k\,$^$\scriptstyle n\,$) sequences, $\scriptstyle k\,\geq \,2\,$, which contains $\scriptstyle \aleph _{0}\,$ sequences;
• the family of tetration ($\scriptstyle k\,$^^$\scriptstyle n\,$) sequences, $\scriptstyle k\,\geq \,2\,$, which contains $\scriptstyle \aleph _{0}\,$ sequences;
• the family of pentation ($\scriptstyle k\,$^^^$\scriptstyle n\,$) sequences, $\scriptstyle k\,\geq \,2\,$, which contains $\scriptstyle \aleph _{0}\,$ sequences which obviously generalizes to the super-family of $\scriptstyle t\,$-ation ($\scriptstyle k\,$^$\scriptstyle \,\cdots ~t-2{\rm {~times}}~\cdots \,$ ^$\scriptstyle n\,$), $\scriptstyle k\,\geq \,2,\,t\,\geq \,3\,$, sequences, which contains $\scriptstyle \aleph _{0}\,$ families of sequences;
• the family of $\scriptstyle k\,$-almost primes sequences, $\scriptstyle k\,\geq \,0\,$, which contains $\scriptstyle \aleph _{0}\,$ sequences, and so on...

Now, let's suppose a meta-algorithm to generate the $\scriptstyle \aleph _{0}\,$ definitions for all the definable sequences and algorithms for all the (at least) partially computable integer sequences (really for ALL, how on earth are we going to know we found them ALL!?) is conceivable. We would still only produce the countable set of (at least) partially computable sequences (for which at least one member is computable) which very likely have a density of 0 (measure 0) among the infinitely countable set of definable integer sequences which themselves are an infinitely countable subset of the uncountable set of all integer sequences (definable or undefinable).

In conclusion

The OEIS will continue to expand for the foreseeable future, but ultimately this expansion will be bounded by human commonsense, reader interest and editor patience.

References

• "Hypercomputing Models," Mike Stannet, p. 135, and "The Myth of Hypercompution," Martin Davis, p. 195, in Alan Turing — Life and Legacy of a Great Thinker, Christof Teuscher (Ed.), Springer 2004.

External links

• Christof Teuscher (Ed.), Alan Turing: Life and Legacy of a Great Thinker, Springer, 2004.
• hypercomputation.net.
• Eric W. Weisstein, Aleph-0, from MathWorld — A Wolfram Web Resource.
• Eric W. Weisstein, Aleph-1, from MathWorld — A Wolfram Web Resource.
• Eric W. Weisstein, Continuum Hypothesis, from MathWorld — A Wolfram Web Resource.
• Eric W. Weisstein, Integer Sequence, from MathWorld — A Wolfram Web Resource.