Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!bloom-beacon!cs.glasgow.ac.UK!jack
From: jack@cs.glasgow.ac.UK (Mr Jack Campin)
Newsgroups: comp.ai.digest
Subject: continuity and computability
Message-ID: <10507.8810031349@vanuata.cs.glasgow.ac.uk>
Date: 3 Oct 88 13:49:33 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Organization: The Internet
Lines: 32
Approved: ailist@ai.ai.mit.edu


smryan@garth.UUCP (Steven Ryan) wrote:

>> "Insufficient attention has been paid to the problem of continuous
>> actions." Now, a question that immediately comes to mind is "What problem?"

> Continuous systems are computable using calculus, but is this `effective
> computation?' Calculus uses a number of existence theorems which prove some
> point or set exists, but provide no method to effectively compute the value.

> It is not clear that all natural phenomena can be modelled on the discrete
> and finite digital computer. If not, what computer could we use?

I brought up this same point in the Usenet sci.logic newsgroup a short while
ago. There is a precise sense in which analogue computers are more powerful
than digital ones - i.e. there are continuous phenomena unsimulatable on a
Turing machine.

Most of the work on this has been done by Marian Pour-El and her coworkers.
An early paper is "A computable ordinary differential equation which possesses
no computable solution", Annals of Mathematical Logic, volume 17, 1979, pages
61-90. This result is a bit of a cheat (the way the equation is set up has
little relation to anything in the physical world) but I believe later papers
tighten it up somewhat (one uses the wave equation, which you'd expect to be a
powerful computing device given that interferometers can calculate Fourier
transforms in constant time). I haven't seen these later articles, though.

-- 
Jack Campin,  Computing Science Department, Glasgow University, 17 Lilybank
Gardens, Glasgow G12 8QQ, SCOTLAND.   041 339 8855 x6045 wk 041 556 1878 ho
ARPA: jack%cs.glasgow.ac.uk@nss.cs.ucl.ac.uk      USENET: jack@glasgow.uucp
JANET: jack@uk.ac.glasgow.cs   PLINGnet: ...mcvax!ukc!cs.glasgow.ac.uk!jack