Re: Alan Turings halting proof is incorrectly formed PT Herc

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

  • Next message: Alex Vinokur: "Computing Huffman codes on a Turing Machine" 
    Date: Wed, 30 Jun 2004 12:58:21 GMT

    This may have been unclear. Please note: I am not saying that
    HALTNODIAGONAL exists. A proof either way would most likely be extremely
    arduous since we're dealing with a contrived subset of all programs. But
    whether or not HALTNODIAGONAL exists is of no consequence to theoretical
    computer science.

    "Anonymous" <Anonymous@home.net> wrote in message
    news:nzyEc.5655$og4.1519@newssvr16.news.prodigy.com...
    > 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
    > >
    > >
    > >
    >
    >

  • Next message: Alex Vinokur: "Computing Huffman codes on a Turing Machine"

    Relevant Pages