Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!ittatc!dcdwest!sdcsvax!ncr-sd!hp-sdd!hplabs!oliveb!glacier!kestrel!ladkin
From: ladkin@kestrel.ARPA (Peter Ladkin)
Newsgroups: net.singles
Subject: Re: Value of Computer Science degree
Message-ID: <5541@kestrel.ARPA>
Date: Fri, 7-Mar-86 18:01:02 EST
Article-I.D.: kestrel.5541
Posted: Fri Mar  7 18:01:02 1986
Date-Received: Mon, 10-Mar-86 08:42:10 EST
References: <214@eddie.UUCP> <3850042@csd2.UUCP>
Organization: Kestrel Institute, Palo Alto, CA
Lines: 19

In article <3850042@csd2.UUCP>, sykora@csd2.UUCP (Michael Sykora) writes:
> >/* gds@eddie.UUCP (Greg Skinner) /  5:03 pm  Feb 16, 1986 */
> >Apparently, this was one of those MIT Course 6 people that "can't
> >program themselves out of a wet bag", because if they had learned
> >anything in their theoretical computer courses, they would have known
> >that such a program is mathematically impossible.
> 
> Is this notion not based on Church's Thesis, which, while there is
> a great deal of evidence to support it, is not mathematically provable?

No, it's not based on Church's Thesis. The claim is that such
a problem is not Turing-computable (this is what is meant by
stating that such a program is *mathematically impossible*).
Church's Thesis would state that the computable functions
are precisely the Turing-computable functions, and it is this
which cannot admit of a proof (although a refutation, if there
is one, would be to exhibit a computable function that isn't TC).

Peter ladkin