Re: Alan Turings halting proof is incorrectly formed PT Herc

From: Anonymous (Anonymous_at_home.net)
Date: 06/30/04 

Date: Wed, 30 Jun 2004 12:42:59 GMT

You are right in saying that there could be programs written that will check
if any program that is a member of a specific subset of all possible
programs halts. If you are trying to make this subset as large as possible
then why exclude ALL programs that reference HALTNODIAGONAL, why not simply
exclude the ones such that their reference to HALTNODIAGONAL causes a
logical contradiction in HALTNODIAGONAL being recursive?

I see lots of arguments that hinge solely upon someone's lack of
understanding of the rigorous mathematical foundations of a subject and/or
rigorous mathematical reasoning methods - so I will not get into it with you
regarding HALT. For the benefit of those who are perusing the group to
learn something: this HALTNODIAGONAL is no brilliant foundation shaker ...
it is simply a restatement of the fact that we can determine if SOME
programs halt. Theoretical computer science is not concerned with this,
though ... it is already known.

The significance of HALT is in its theoretical foundational properties - it
is important to understand that in theoretical computer science, programs
are not just things like Microsoft Windows or Adobe Photoshop ... programs
are strings of characters from the alphabet of the programming language.
Determining whether or not Adobe Photoshop halts is no more important than
determining whether or not the DIAG program halts in the construction of the
proof of the halting problem.

"|-|erc" <gotcha@beauty.com> wrote in message
news:8BnEc.70810$sj4.20780@news-server.bigpond.net.au...
> "Kevin Stern" <K-Stern@neiu.edu> wrote in
>
> > This is not the halting problem, Herc. This is a different problem.
> > To say that the halting proof is incorrectly formed is a faulty
> > conclusion.
> >
> > Is your question, though, as follows?
> >
> > Can there be a machine HALTNODIAGONAL that analyzes a program and
> > outputs 'Yes' if it halts, 'No' if it does not and 'YahRight!' if it
> > references HALTNODIAGONAL.
> >
> > If so, then I don't know the answer off hand. I don't immediately see
> > any 'proof' that there could not be such a machine - I suspect that
> > there is no simple and elegant proof either way since (unless I'm
> > missing a 'trick') it seems that you've eliminated the possibility of
> > self-reference.
> >
> > This has also degerated into an uninteresting problem since you're
> > looking for a very specific contrived machine whereas the halting
> > problem is looking for a general machine that fulfills a very useful
> > and fundamental purpose. You see, we already know that one can write
> > a program that will decide if SOME programs will halt or not - this
> > was never an issue.
> >
> > Hope this helps,
> >
>
>
> Does a program exist that can systematically tell me whether a given input
program will halt?
>
> That is the question, halting proof is an ill conceived representation of
the question,
> since it answers NO.
>
> The correct answer is, COULD BE, as long as it doesn't analyse itself.
>
> A trillion dollar software industry suggests it could be an interesting
problem.
>
> Herc
>
>
>

Relevant Pages

  • Re: On The Proper Formulation Of The Halting Problem
    ... >> formulation of the Halting Problem is more or less along ... >> will halt, wwill loop, and vice versa. ...
    (sci.logic)
  • Re: Alan Turings halting proof is incorrectly formed PT Herc
    ... regarding HALT. ... Theoretical computer science is not concerned with this, ... >> This is not the halting problem, ... >> To say that the halting proof is incorrectly formed is a faulty ...
    (sci.math)
  • Re: Alan Turings halting proof is incorrectly formed PT Herc
    ... regarding HALT. ... Theoretical computer science is not concerned with this, ... >> This is not the halting problem, ... >> To say that the halting proof is incorrectly formed is a faulty ...
    (sci.logic)
  • Re: PROOF that numbers are countable
    ... you're the one claiming such an enumeration of halting ... > halt, feel free. ... > If it is as powerful as TMs, then there are constructs that do not halt. ... > claim applies to your special selection, ...
    (comp.theory)
  • Re: before Cantor there was Rantor
    ... >>halting proof is contradiiction of the existence of a particular defined ... halt function is a SPECIFIC function. ... I did disprove the Halting Proof. ... in that time then it outputs TRUE, otherwise it timed out and outputs DONTKNOW. ...
    (sci.math)