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