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