Re: Alan Turing's Halting Problem is incorrectly formed (PART-TWO)

From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 06/20/04 

Date: 20 Jun 2004 17:53:55 -0400

 : > : PREMISES:
 : > : (1) The Halting Problem was specified in such a way that a solution
 : > : was defined to be impossible.
 : >
 : > That is false.
 : > The problem has to do with the possible existence of something.
 : > If it turns out that the something doesn't exist, that does NOT
 : > mean that "the solution to the problem was defined to be impossible".

"Peter Olcott" <olcott@worldnet.att.net> writes:
 : Yet this is not the case with the solution to the Halting Problem

Yes, it is.

 : (and square circles).

It's the same thing.

 : In both these cases it is not merely that no
 : solution has been found to satisfy the requirements of the problem.

How can you say "merely"?? In both cases it is the case
that no individual in the relevant domain satisfies
the requirements. Your "has been" is just plain evil: THERE IS NO
*TIME* involved here! EVERY last thing in the domain either does
or doesn't satisfy the requirements! AT THE *SAME* time! At ALL
times! NOW AND FOREVERmore!

 : In BOTH these cases the problem is defined in such a way that
 : no solutions are possible.

True, but IN MATH, it is ALWAYS like that!
The natural numbers have been defined in such a way that
no natural n can possibly satisfy the requirements of being > 2 and
having a corresponding x,y, and z such that x^n + y^n = z^n.
SO WHAT? Are you going to say that Fermat's Last Theorem is ILL-FORMED??
That is just stupid.

 : The lack of solution is directly derived
 : from the definition of the problem itself.

The lack of a solution to Fermat's Last Theorem is also
"directly derived from the definition of the problem itself".
IN MATH, EVERYthing is derived from definitions! BY DEFINITION!

In the case of the halting problem, what you are calling a
"solution" is starting to get complicated. There are TWO DIFFERENT
solutions to "the halting problem". If you define the problem by
"a solution to this problem is a TM-program that halts yes on (M,w)
when M halts on w and otherwise halts no", then yes, the problem
has no solutions.
But if you define "the halting problem" as "is there a TM that
always halts on (M,w) telling whether M halts on w?" then
the answer, "No, there is no such TM" (or, perhaps, rather,
a PROOF that there is no such TM) IS *ITSELF*THE* solution
to "the halting problem".

In EITHER case, NEITHER of these problem-definitions is flawed
or ill-formed as a definition. If the question is to find
a closed curve that is both circular and square, then the answer
is that there isn't one (or, rather, is a proof that there
isn't one). Ditto for a TM satisfying the Halt(,)
spec, or a barber shaving all&only those who don't shave themselves,
or a set containing all&only sets that don't contain themselves.
There are literally millions of properties with the meta-property
that you can't actually find even 1 thing having the property.
That does NOT make the properties or the associated problem of
finding something having them "ill-formed". It just means the
answer was no. 

-- 
 --- 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: Is the Halting Problem merely an ill-formed question?
    ... It either halts or it doesn't; ... THEY CAN write on their tapes. ... if (MalignantSelfReference(SourceCode, InputData)) ... that the Halting Problem is solvable, I am only at most attempting to show the ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... It does not go into an infinite loop if and only if it halts. ... >>This is how the Halting Problem is defined. ... It is not the analogy that is crucial. ... >>the student's could determine their own grades. ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... It does not go into an infinite loop if and only if it halts. ... >>This is how the Halting Problem is defined. ... It is not the analogy that is crucial. ... >>the student's could determine their own grades. ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is incorrectly formed (PART-TWO)
    ... [halting problem without assuming the existence of a machine solving the ... Where did I assume the existence of a machine solving the ... > which we mean that it outputs 1 if E halts when given. ... the construction goes trough no matter what "hypothetical" ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... of the Halting Problem ever actually existed. ... Proving a positive provides only showing a single example. ... presumed the third step from the incorrect second step. ... > TM with impossible properties (it halts iff it doesn't). ...
    (sci.logic)