FOM: Precision and Turing-computability

nitzpon nitzpon at science.uva.nl
Fri May 24 08:55:07 EDT 2002


gandy gives a quite exhaustive analysis of the question wether 'every
machine is a turing-machine' in his article:

Gandy, Robin.  Church's thesis and principles for mechanisms.  
The Kleene Symposium. Proceedings of the Symposium held at the 
University of Wisconsin, Madison, Wis., June 18--24, 1978. 
Edited by Jon Barwise, H. Jerome Keisler and Kenneth Kunen. 
Studies in Logic and the Foundations of Mathematics, 101. 
North-Holland Publishing Co., Amsterdam-New York, 1980. xx+425 pp.
ISBN: 0-444-85345-6  MR 82h:03036 (Reviewer: Douglas Cenzer) 03D10
(03A05)

as far as i know that's kind of the definite opinion on the subject
(loose of the question wether machines that do not satisfty the
conditions stated there might exist)
but i would be very interested in different opinions on that (and such
machines as mentioned above..)


Paul LE MEUR wrote:
> 
> We can't measure any physical magnitude with an infinite precision.
> I'm not a physicist but this seems widely admitted.
> 
> Another hypothesis that seems reasonable, probably less than the first though,
> but that I've seen enounced:
> For any given finite precision, any physical phenomenon can be predicted by a
> Turing machine with this precision.
> (like an instance of the N-body problem)
> 
> Then if both are true, there can exist no machine that computes a non-Turing-
> computable function.
> 
> My questions are:
> What are the current opinions on these two hypothesis?
> And, if true, do you agree they prove Church-Turing thesis?
> 
> Thank you.
> 
> Paul Le Meur




More information about the FOM mailing list