Re: What is the Result from Invoking this Halt Function?

From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 08/18/04 

Date: 18 Aug 2004 10:32:16 -0400

Simon G Best <s.g.best@btopenworld.com> writes:

 : I would just like to say: I am an idiot! :*>

Ditto.
I mean that *I* am an idiot, not that Simon is.

 : I am an idiot! :*>
 :
 : I've been thinking all this time that that paper was the one with
 : The Halting Problem in it,

ditto.

 : and it wasn't :-(

Aw, c'mon:
 : [...]
 : > Turing's proof in this part of the paper was of that no machine
 : > can determine in all cases whether a machine is circular or circle-free.

This really IS close enough.
"circle-free" is close enough to meaning "non-halting".

 : > "The halting problem" is teensy potatoes after all that, but he
 : > didn't address it specifically as such in this paper; it does follow easily from
 : > what he did prove.

That is sort of not the problem.
The problem is that when TMs don't halt, there are 2
different ways of looking at that. 1 way is that the result
they were trying to compute was infinitary to begin with, so
non-halting is necessary to successfully returning a result
(i.e., to being "non-circular"). In the paper, halting,
COUNTER-intuitively, is a case of "circular", i.e. FAILING.
The other way is that the input string is intended to be
finite (and the output one is too), in which case halting
is necessary to a successfully returning a result and non-halting
is failure. The problem is that the latter convention is typical
nowadays for thinking of TMs as computing partial recursive functions
(as OPPOSED to "enumerators" of infinitary structures), but the former
is "original". It also bears stressing that in both contexts, "the other"
kind of machine is tolerated as valid-though-"exceptional". 

-- 
 --- The history of our nation has demonstrated that separate is seldom, if ever, equal.
 --- (Feb.3,2004) Supreme Judicial Court of Massachusetts (4-3), adv.Sen.#2175
Quantcast