## digitalmars.D - [OT] A model for recording everything that is computable

- Justin Johansson <no spam.com> Aug 13 2010

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

Aug 13 2010