4
$\begingroup$

Background: Oeis

OEIS, the online encyclopedia of integer sequences tabularizes functions from the natural numbers to the integers. It looks like most sequences they list are computable. Some are finite. The database can also list sequences of fractions by listing nominators and denominators separately. They can also list (computable) real numbers by listing their decimal or binary expansion. They can also list sequences of multiple arguments by linearizing (diagonalizing) them in some way.

So oeis covers functions and sequences of integer and rational arguments and values, plus separate (computable) real numbers.

You can argue about whether the usues that require some interpretation I mentioned are legitimate but thats the state of things. I'm also not sure whether they allow uncomputable sequences, or how these would be defined in their format.

They have code in a few programming languages for generating many of the sequences.

All our friends like factorials, fibonaccis, digits of pi etc are there.

Continuous functions

But there's another class of functions we are very interested in which are the real valued ones. Let me restrict the discussion to multi argued, single valued computable continuous functions from Rn to R.

I think it would be cool if there where some formal, but community driven database of such functions in the spirit of Oeis, Wikidata and Wikipedia.

The database would for each entry provide programs of a standardized format for a variety of programming languages that could be used to compute the values of the listed functions to any precision for any computable (or at least rational) real number arguments. The accuracy should be trackable, i.e. the epsilon in the convergent series should be computable as well, as required in constructive analysis. Interval arithmetic would be supported as well.

This database would contain algorithms written in say C, Mathematica and other languages that would be download, compile and usable as such, automatically. In that sense it would list human defined machine usable data like say the wikidata.org project.

In a sense, this would be the basis for a large numerics library.

These functions dont really fit into oeis (unless you would allow a finite sequence representing the algorithm). Of course some analytic and algebraic functions could be fit into oeis by listing the coefficients appearing in their definitions but I think a special purpose database is more suitable.

Question

What do you think?

Does a formal, simple, coherent, public repository (an encyclopedia of computable functions if you will) for such functions already exist?

Is there some existing project we could shoehorn into supporting something like this, e.g. wikidata?

What considerations for making something like this work did I miss?

Is this even the right audience to ask this?

Details

I think multiple arguments are required, but one output is enough because the individual components could be listed separately. Clearly this would also support complex valued functions by splitting the arguments and return values into real and imaginary part.

But maybe multiple output values should still be allowed to support more efficient algorithms?

I would especially like to have standardized downloadable code. Unfortunately this is not the case for oeis, c.f.

https://mathematica.stackexchange.com/questions/40/is-it-possible-to-invoke-the-oeis-from-mathematica

Ideally, oeis would be structured such that in Mathematica

OEIS["A000142"][5]

would be 5!, i.e. just another way of saying Factorial[5] Similarly, this database would be organized such that e.g.

OECF["C456"][0.5]

Is another way of writing Sin[0.5].

I'm open for ideas for the name of the thing, but I think the numbering should work like wikidata's Q1,...,Q1234,... system without a fixed number of digits to support any growth.

As for continuity: I think we can't measure the degree of approximation of a non continuous real-valued function. Computing say the inidcator function of the rationals makes no sense. On the other hand, the Heaviside step function seems easy enough to compute.

$\endgroup$
  • 1
    $\begingroup$ Regarding OEIS look-up, note that Sage already has this feature. E.g., oeis("A000142") returns $5!$, and oeis([1, 1, 2, 6, 24], max_results=4) finds the factorial sequence (among others, each being addressable), etc. $\endgroup$ – r.e.s. Jul 2 '16 at 2:09
  • $\begingroup$ Thanks for the pointer. But again by nature of the current Oeis this package cannot give more than the terms listed in there. I'd love to have parametric reusable programs in oeis for any sequence. $\endgroup$ – masterxilo Jul 2 '16 at 12:16
  • 1
    $\begingroup$ In Sage, some infinite OEIS sequences are implemented via the sloane_functions module.; e.g., sloane.A000142 computes arbitrarily many terms. $\endgroup$ – r.e.s. Jul 2 '16 at 14:29
  • $\begingroup$ functions.wolfram.com seems to be a project going somewhat in that direction. $\endgroup$ – masterxilo Aug 18 '16 at 22:24
  • $\begingroup$ Writing numerical algorithms for evaluating real-valued functions to fixed precision, one should be aware of the table-makers dilemma: Correctly rounding a function's value might require unbounded computation time... $\endgroup$ – masterxilo Oct 4 '16 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.