Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site psuvax1.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!unc!mcnc!philabs!cmcl2!seismo!rochester!cmu-cs-pt!cadre!psuvax1!simon
From: simon@psuvax1.UUCP (Janos Simon)
Newsgroups: net.ai
Subject: Re: AI and Turing's Thesis
Message-ID: <1647@psuvax1.UUCP>
Date: Tue, 21-May-85 14:25:42 EDT
Article-I.D.: psuvax1.1647
Posted: Tue May 21 14:25:42 1985
Date-Received: Fri, 24-May-85 05:58:07 EDT
References: <113@nvuxf.UUCP> <388@linus.UUCP>
Reply-To: simon@psuvax1.UUCP (Janos Simon)
Organization: Pennsylvania State Univ.
Lines: 46
Summary: Clarification on the meaning of Church's thesis

[]
There's been a lot of needless confusion in recent postings. Church's thesis
says that anything that can be precisely described, can be computed by a
Turing machine. The question, then is: "Is the human mind equivalent to a Turing
machine?", and there is a strong urge in some people to respond "no".

Justifications for a negative answer can be 
1)"we're not Turing machines"
or
2)"because we can do X, but Turing machines can't".

Objection 1) is clearly valid, and can be forcefully put (e.g. we have feelings,
we have an immortal soul, we are creative, we are organic and think in parallel)Nonetheless, it should be discarded. What matters is not what motivates us or
how we do things, but the result of such actions. That is, in order to prove 
that Church's thesis is not applicable to human minds, we must give a 
justification of type 2). (read Turing's original paper on AI for a MUCH better
debunking of such objections).

Objection 2) has never been successfully used. For example, the version X="debugprograms" is clearly false: we can debug SOME programs. So can 
computers. (The unsolvability of the halting problem does NOT mean
that a machine cannot decide whether another will halt or not - it says that
the decider cannot do it for an ARBITRARY machine. Compilers routinely decide
that certain programs will run forever, and refuse to run them. The fact
that these programs are easily detectable is irrelevant.

Previous postings fall into one of these categories. For example, Hewitt's
examples of asynchronous parallel computation can be easily simulated by a 
Turing machine - it will be less efficient, but Church's thesis says nothing
about efficiency. The fact that the brain does not work like a Turing machine
does not mean it cannot be simulated by one: the motion of springs has little
resemblance to electric current in circuits, but analog computers use the
equivalence of the respective differential equations.
As for our purported ability to decide whether programs will halt, consider the
procedure below:

let Next(a,b,c,n) be a subroutine that returns the next 4-tuple of positive 
integers in some standard ordering (e.g. increasing values of a+b+c+n, ordered
lexicographically within a given value), starting with (1,1,1,1).

	while 1|=0 do
		Next(a,b,c,n);
		if n>2 then if a**n + b**n = c**n then halt
	od

I would warmly welcome a proof that this procedure halts (or that it loops
forever).