X-Message-Number: 8679 Date: Wed, 15 Oct 1997 08:21:44 -0400 From: "John P. Pietrzak" <> Subject: Do computers compute? References: <> Thomas Donaldson wrote: > As for Turing's thesis as distinct from Turing machines, exactly what > was his thesis? Please excuse me for jumping in on this one, but I think I can give a little information here. If what we're talking about is the Church- Turing thesis, it's basically the idea that the notion of computability is tied to exactly what the Turing Machine does (Church came up with an equivalent mathematical structure to Turing's around the same time). Quoting from what has become my favorite reference in the last few weeks, Hopcroft & Ullman's book, p. 166 says The assumption that the intuitive notion of "computable function" can be identified with the class of partial recursive functions is known as Church's hypothesis or the Church-Turing thesis. While we cannot hope to "prove" Church's hypothesis as long as the informal notion of "computable" remains an informal notion, we can give evidence for its reasonableness. As long as our intuitive notion of "computable" places no bound on the number of steps or the amount of storage, it would seem that the partial recursive functions are intuitively computable, although some would argue that a function is not "computable" unless we can bound the computation in advance or at least establish whether or not the computation eventually terminates. What is less clear is whether the class of partial recursive functions includes all "computable" functions. Logicians have presented many other formalisms such as the lambda calculus, Post systems, and general recursive functions. All have been shown to define the same class of functions, i.e., the partial recursive functions. In addition, abstract computer models [...] also give rise to the partial recursive functions. They go on from here to describe one of their abstract computer models. (The partial recursive functions mentioned here are simply the set of functions able to be computed by a Turing Machine.) Unfortunately, this doesn't give you an absolute answer as to what a computer is, but at least you can see that neither Hopcroft or Ullman (or Church or Turing for that matter) knew exactly what a computer was either. John Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8679