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

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

Date: 11 Aug 2004 14:14:15 -0400

Chris Menzel <cmenzel@remove-this.tamu.edu> writes:
 : Unfortunately, arguing with liars and hacks is pointless. Best simply
 : to state the facts and point to the documentation for the sake of
 : interested bystanders in danger of being misled and walk away. To wit:
 : There is an elementary proof that the Halting Problem is unsolvable (one
 : version: http://tinyurl.com/6ow6c).

One could get a little more elementary by working backwards.
The important part of this proof has nothing whatsoever to do with
TMs. Suppose you just had a machine with an input tape, and
after you started the machine running on the tape, it [necessarily]
either halted or it didn't. That is the important property that TMs have, for
purposes of this proof. The other properties don't matter much. You don't have
to know that tapes have cells, or can have characters written in them.
You don't have to know that they have a beginning but not an end, or that
the machine has a head that can move left or right on them. ALL you have
to know is that they not only can, BUT MUST, halt or not, on every invocation,
on every input. And you have to know that inputs can somehow describe
machines (so that it is possible for any machine to be fed in -- or, at least,
for an accurate DESCRIPTION of that machine, to be fed in -- as input
to any other).

Define "loop" by saying that an invocation M(w) (of a machine M, or a machine
described by string M, on input w) loops iff it doesn't halt.

Now, the question is: can there or can there not exist: a machine that
Loops on [all and only] input-descriptions of those machines that DON'T
Loop on input-descriptions of themSELVES ?

The answer is, no, there can't.
The related question is, can there or can
there not exist a machine that:

Halts on [all and only] input-descriptions of those machines that DON'T
Halt on input-descriptions of themSELVES ?

The answer to this is no as well, but you don't have to prove it from
the first one. You can prove it independently. Each of these proofs
looks exactly the same as the proof that there can't
exist [in this town] a barber who

Shaves [all & only] men [in this town][ who DON'T
shave themselves,

or the proof that there can't exist a set that

Contains [all and only] those sets that DON'T
Contain themselves.

PO's real problem, and the reason why he has always needed to be in sci.logic
as opposed to comp.theory, is that he didn't know THIS. The fact that
he doesn't understand what abstraction is is arguably secondary.
First you have to understand what logic is. 

-- 
 --- 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

Relevant Pages

  • Re: Do Write Once TMs Halt?
    ... then it will never halt. ... Assume we have a TM that can only read from the tape and move ... No State/Input combination can appear more than once in a Halting Path ... (see loops, below). ...
    (comp.theory)
  • Re: Seaming Flats
    ... > "The original olive-drab version of the tape was developed ... Just because a story "fits the facts" doesn't make it true! ... would seem obvious that there has been a confusion between "Duct Tape" and ... "Duck Tape" but no unequivocal evidence which way the metamorphosis actually ...
    (rec.arts.theatre.stagecraft)
  • Re: Harbhajan a liar , a chucker and a cheat
    ... about the way the Aussie supporters gather their facts. ... was racist and Herbies is backtracking ...
    (rec.sport.cricket)
  • Re: Harbhajan a liar , a chucker and a cheat
    ... about the way the Aussie supporters gather their facts. ... was racist and Herbies is backtracking ...
    (rec.sport.cricket)
  • Re: Warning to PlusNet users, old & new
    ... who fails to realise facts. ... I don't really care what you think, until the service grinds to a halt ...
    (uk.telecom.broadband)
Loading