Re: Impossible Database Design?

On Monday, September 30, 2013 11:37:06 AM UTC+8, Derek Asirvadem wrote:  On Wednesday, 17 May 2006 07:41:32 UTC+10, Nikolai Onken wrote:

[snip]

I was prompted to read that "Impossible Database Design?" thread from 7 years ago, and found something Bob Badour said which was unchallenged at the time. Better late than never I guess...

> With all due respect, inifinite is about capacity and the impossibility
> of representing each of an infinite set of values in a finite space.

For this statement to be correct it must be assumed the (non)existential quantification over finite spaces is outside the universal quantification over the values of the infinite set.

I believe in the context of the somewhat superficial discussion (about finite versus infinite), the statement was intended to suggest that infinite data types are not useful to computer science. If so I'd call that a gross misrepresentation!

In fact computer science very commonly deals with (countably) infinite types for which there exists a finite representation of every value of the type. It is common for programming language semantics to be defined with respect to an abstract machine with unbounded memory (what else does Turing complete mean?).

This is not merely some academic point. Open any book on practical algorithms and data structures and see all sorts of infinite data types (strings, lists, trees, queues, ...). Mathematical induction is often used to prove theorems about algorithms for an infinity of inputs. Most computer languages are infinite (i.e. the set of sentences that conform to the grammar is infinite). Imposing finite limits all over the place would just add horrendous complexity.

Actual memory usage of a real computer is typically a global dynamic property over multiple processes which is quite unpredictable and largely irrelevant to the design and implementation of general purpose data structures and algorithms. Of course well written programs try to avoid excessive memory usage, and that normally means both finite and infinite data types are appropriate in its design. I would say programmers mostly reason about the execution of their programs on an abstract machine with unlimited memory (whether they realise it or not).

The Turing machine with its infinite tape captures our intuition of what it means to be computable. Some people think the infinite tape is available to be fully used in some sense, but actually computable functions have to terminate after a finite number of steps for each input which means only a finite amount of tape is ever used. The infinite tape just ensures it doesn't run out before it would otherwise have terminated.

TTM has a prescription that all types are finite. I find that completely unreasonable (baffling really). I discussed this on TTM mailing list and people were divided on the issue.

David Received on Mon Oct 07 2013 - 05:59:16 CEST