Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site sbcs.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!mcnc!philabs!sbcs!debray
From: debray@sbcs.UUCP (Saumya Debray)
Newsgroups: net.ai
Subject: Re: AI and Turing's Thesis (undecidability)
Message-ID: <323@sbcs.UUCP>
Date: Tue, 11-Jun-85 23:08:53 EDT
Article-I.D.: sbcs.323
Posted: Tue Jun 11 23:08:53 1985
Date-Received: Fri, 14-Jun-85 06:14:25 EDT
References: <441@wdl1.UUCP>
Organization: Computer Science Dept, SUNY@Stony Brook
Lines: 32

>      Undecidability is confusing to many people.  It helps to remember that
> formal undecidability can only arise for machines which are either 
> nondeterministic or have infinite memory.  This follows from the observation
> that a machine with finite memory and deterministic state transitions must 
> eventually either repeat a previous state, there being a finite number of
> such,  or halt.  So this is a total nonissue for all real computers.

Technically, you're right.  However, the virtual address space of most
"real" computers is so large that it is, for all practical purposes as far
as checking repitition of previous machine states is concerned, infinite.
In other words, not many people I know will spend a lot of time writing
code to check whether my VAX is repeating states.

>      The whole issue of undecidability is a red herring in the AI and
> computer field, and should be put to rest.
>

I wish undecidability would go away, it'd certainly make life easier for me
(and, I'm sure, a lot of other people).  Unfortunately, it's a very
pertinent issue for programs that manipulate other programs, e.g.
optimizing compilers.  Simple questions like "will this variable be
instantiated at this point in this Prolog program?" are undecidable in
general (as most "interesting" program properties are, ref: Rice's
theorem), so such optimizers must be careful to err on the side of caution,
in order to guarantee soundness.
-- 
Saumya Debray
SUNY at Stony Brook

	uucp: {allegra, hocsd, philabs, ogcvax} !sbcs!debray
	arpa: debray%suny-sb.csnet@csnet-relay.arpa
	CSNet: debray@sbcs.csnet