[OT] A model for recording everything that is computable

[Justin Johansson]

I'd like to re-intro this off-topic which I alluded to a week or
so ago with this snippet from "Frontiers in Theoretical Physics" at
http://www.kavlifoundation.org/frontiers-theoretical-physics

<quote>
Computation increasingly defines the limit of what we know in science,” 
says theorist Michael Freedman of Microsoft’s Station Q at the 
University of California, Santa Barbara. “At some time this century, we 
expect to pass from classical to quantum,” he says, and “in a sense 
that’s the ultimate transition. We’ll be able to compute everything that 
can be computed.
</quote>

Now, for the entertainment of D NG readers, may we consider the
discovery or invention of a model that (1) is capable of recording
everything that is computable and (2) is readily interrogated to access
any precomputed result given the inputs to the computation that
produces that same result.

If everything that is computable was precomputed and saved in WORM
(write-once-read-many) storage (i.e. immutable once constructed)
storage, what best (define 'best'?) data model would be appropriate,
or, better still, would be (or become) apparent from mathematical
axioms?

Assuming that the WORM device with infinite storage capacity required
for this task is also 100% reliable, then we may further assume that
there is no need for redundancy (of data storage) and specify that
orthogonality is the essence of the data model.

So what kind of data model is called for?  What say, in lay-speak,
an N-dimensional spreadsheet (N being a strictly positiver integer,
zero being trivially ruled out)?

What minimum value of N (i.e. dimensionality of the spreadsheet)
suffices to make a storage model amenable to (1) and (2) above?

Further, while it is apparent that one or more dimensions of
the spreadsheet be comprised an infinite number of cells,
should this number be countably infinite or uncountable infinite
in any particular dimension?

My first guess for such a data model is an infinite 2-dimensional
relational table (of the Codd and Date type) suggesting that the
number of rows in the table is uncountably infinite and that the
number of columns is countably infinite.  Admittedly this is a
hazarded guess and not backed by anything remotely resembling a
proof.  I'm really just throwing this up as a starting point for
consideration.

What are your ideas?

Some other apt references for this topic:

Relational Algebra
http://en.wikipedia.org/wiki/Relational_algebra

Computational complexity theory
http://en.wikipedia.org/wiki/Computational_complexity_theory

 From Everything2
http://everything2.com/title/computer+science

<quote>
So zooming in a little, we have have to figure out how exactly to go 
about computing things (the DFA), and how to represent information (the 
tape). Incidentally, this is why computer geeks go around making CS 
metaphors about every real-life thing (i.e., the conversation stack, 
binary search) -- because the majority of real life is dealing with 
information  and solving problems.
</quote>

Google search on
relational functional model

Cheers
Justin Johansson