ladkin@KESTREL.ARPA (Peter Ladkin) (11/05/86)
Here's a quick shot at an A/D distinction.
The problem with the rationals was that the ordering and the operations
are easily translatable into computations on the natural numbers.
So, the proposal is:
DIGITAL: computations on a structure S that is recursively
isomorphic to a definable fragment of Peano Arithmetic.
ANALOG: computations on a dense structure that
is not recursively isomorphic to a definable fragment of Peano
Arithmetic.
Note there can be computations which are neither analog nor
digital according to this definition.
The rationale for this choice depends on two considerations.
(1) One must not be able to transform one kind of computation
into the other, which can be done only if there is a machine
(aka recursive function) that can do it.
(2) The distinction must not collapse in the face of the
possibility that physics will tell us the world is
fundamentally discrete (or fundamentally continuous), since
if Gerald Holton is to be believed, physical science has
been wavering between one and the other for thousands of years.
So the discrete/continuous nature of nature can be regarded
as a metaphysical issue, and we want to finesse this in our
definition to make it physically realistic.
I chose Peano Arithmetic as the base structure because it is
intuitively discrete, and all the digital structures that have
been proposed fit the criterion that they can be recursively
mapped into simple discrete arithmetic.
The density-of-values criterion for analog computation seems
intuitively plausible, and if one wants to make the distinction
between analog and digital into a feature of the world, not merely
of the representation chosen, one needs to assure consideration
(1) above.
If quantum physics ultimately tells us that the world is discrete,
there is no reason to assume that the discreteness in the world
will provide us with recursive functions mapping that discreteness
into the natural numbers, so analog computations will survive that
discovery.
Peter Ladkin
ladkin@kestrel.arpa