Refutation of the DisProof of the Halting Problem

Discussion in 'C++' started by Peter Olcott, Jul 25, 2004.

  1. Peter Olcott

    Peter Olcott Guest

    The Halting Problem can not be solved within the degree of
    expressability of a TM. My solution only worked because of
    its more limited degree of expressability.

    There is no such thing as a void function in a TM, thus there is
    no way to make constructing the counter-example program
    impossible for a TM.
    Peter Olcott, Jul 25, 2004
    #1
    1. Advertising

  2. "Peter Olcott" <> wrote in message
    news:SXSMc.134873$...
    > The Halting Problem can not be solved within the degree of
    > expressability of a TM. My solution only worked because of
    > its more limited degree of expressability.
    >
    > There is no such thing as a void function in a TM, thus there is
    > no way to make constructing the counter-example program
    > impossible for a TM.


    I think I already asked you to stop posting this stuff, but you appear
    to have a halting problem.

    Jonathan
    Jonathan Turkanis, Jul 25, 2004
    #2
    1. Advertising

  3. Peter Olcott

    Marc Goodman Guest

    Peter Olcott wrote:
    > The Halting Problem can not be solved within the degree of
    > expressability of a TM. My solution only worked because of
    > its more limited degree of expressability.
    >
    > There is no such thing as a void function in a TM, thus there is
    > no way to make constructing the counter-example program
    > impossible for a TM.


    This is either a much better forgery than last time, or a
    very surprising turn of events.
    Marc Goodman, Jul 25, 2004
    #3
  4. Peter Olcott

    Peter Olcott Guest

    "Jonathan Turkanis" <> wrote in message news:...
    >
    > "Peter Olcott" <> wrote in message
    > news:SXSMc.134873$...
    > > The Halting Problem can not be solved within the degree of
    > > expressability of a TM. My solution only worked because of
    > > its more limited degree of expressability.
    > >
    > > There is no such thing as a void function in a TM, thus there is
    > > no way to make constructing the counter-example program
    > > impossible for a TM.

    >
    > I think I already asked you to stop posting this stuff, but you appear
    > to have a halting problem.
    >
    > Jonathan
    >


    Well it looks like I am wrong that I am wrong again.
    This time I won't bother with anything less than a full
    refutation of the original proof. I do have a basis for
    disproving the original proof.
    Peter Olcott, Jul 26, 2004
    #4
  5. Peter Olcott

    Peter Olcott Guest

    "Marc Goodman" <> wrote in message news:pgTMc.184435$XM6.144686@attbi_s53...
    > Peter Olcott wrote:
    > > The Halting Problem can not be solved within the degree of
    > > expressability of a TM. My solution only worked because of
    > > its more limited degree of expressability.
    > >
    > > There is no such thing as a void function in a TM, thus there is
    > > no way to make constructing the counter-example program
    > > impossible for a TM.

    >
    > This is either a much better forgery than last time, or a
    > very surprising turn of events.
    >

    It is a very surprising turn of events. There was one message
    That I read this morning that got me thinking. After I thought
    about it I realized that my solution would not apply to Turing
    Machines. Not that my solution required something more than
    a Turing Machine, but something less. My solution required
    data hiding that is not available on a Turing Machine. One
    thing that the results in is the fact that I did not (yet) correctly
    refute, or solve the original Halting Problem.

    A solution such as the one that I was proposing would have probably
    been obvious to Turing, long ago, if these features would have been
    invented at the time. So it is not exactly that my solution is wrong,
    it is still right in a sense. It is more along the lines that it is of much
    less consequence that I had hoped.

    I do have a whole other solution in mind. It merely requires the
    application of ideas that I already posted. I think that I can still
    disprove the original Halting Problem. It does look like it would
    be a waste of time to provide anything less than a direct frontal
    attack on the original proof. In it current form no one would accept
    it.

    I will post it in another thread anyway, just to get on record
    as this idea's originator.
    Peter Olcott, Jul 26, 2004
    #5
  6. In sci.logic, Peter Olcott
    <>
    wrote
    on Sun, 25 Jul 2004 18:26:58 GMT
    <SXSMc.134873$>:
    > The Halting Problem can not be solved within the degree of
    > expressability of a TM. My solution only worked because of
    > its more limited degree of expressability.
    >
    > There is no such thing as a void function in a TM, thus there is
    > no way to make constructing the counter-example program
    > impossible for a TM.
    >


    Well, the following TM:

    StartState: S
    HaltState: H
    Alphabet: [A-Za-z0-9_]
    TransitionFunction:

    From: S
    With: *
    To: H
    Moving: Sit

    will probably be as close to a void function as one can allow. :)

    --
    #191,
    It's still legal to go .sigless.
    The Ghost In The Machine, Jul 26, 2004
    #6
  7. Peter Olcott wrote:
    >
    > "Marc Goodman" <> wrote in message news:pgTMc.184435$XM6.144686@attbi_s53...
    > > Peter Olcott wrote:
    > > > The Halting Problem can not be solved within the degree of
    > > > expressability of a TM. My solution only worked because of
    > > > its more limited degree of expressability.
    > > >
    > > > There is no such thing as a void function in a TM, thus there is
    > > > no way to make constructing the counter-example program
    > > > impossible for a TM.

    > >
    > > This is either a much better forgery than last time, or a
    > > very surprising turn of events.
    > >

    > It is a very surprising turn of events.


    Not really.
    Peter, you are on a completely wrong track.

    For one thing there is the claim of the so called 'Halting Problem':
    No such function can exist.

    And then there is the proof for this claim:
    Based on the assumption that such a function exists, it can be shown
    that this assumption leads to a contradiction: namely that the function
    cannot exist.

    But note: The proof you are attacking is based on the *assumption* that
    such a function exists.

    So when you attack the proof, and turn it around, all you end up with is:
    Based on the assumption that such a function exists, that function can be
    written.

    That's not nearly of the same quality as the original proof. If I assume
    the moon consists of chesse, then I can conclude that the moons material
    is cheese. Fine. It's all based on the assumption. But: If I can proove
    that even if I assume that the moon is made of cheese the only conclusion
    is that it is not made of cheese, I have shown something important: No matter
    what I do or assume, the moon cannot be made of cheese.

    You should familiarize yourself with proofing methods in a better way. The
    type of proof used for prooving that Halting problem can only be used to
    show that X does not exist. It always works the same way

    * 1) assume X
    * 2) show that assuming X leads to a contradiction. You can use X in that
    proof
    * 3) only logical conclusion: -> X cannot be assumed

    If you need to show that X really exists, you need a different type of proof.
    Just fighting step 2) in the above is not enough.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Jul 26, 2004
    #7
  8. Peter Olcott

    Peter Olcott Guest

    "Karl Heinz Buchegger" <> wrote in message news:...
    > Peter Olcott wrote:
    > For one thing there is the claim of the so called 'Halting Problem':
    > No such function can exist.


    So as soon as I show that there is a way to make such a function this proof
    has been refuted.

    > And then there is the proof for this claim:
    > Based on the assumption that such a function exists, it can be shown
    > that this assumption leads to a contradiction: namely that the function
    > cannot exist.


    I can show that it does not lead to a contradiction.
    That it leads to a contradiction is a conclusion that does not follow
    from the proof.

    > But note: The proof you are attacking is based on the *assumption* that
    > such a function exists.
    >
    > So when you attack the proof, and turn it around, all you end up with is:
    > Based on the assumption that such a function exists, that function can be
    > written.


    I end up with the fact that the proof that shows that it is impossible
    is incorrect. This by itself is an amazing feat. No one has even
    questioned this proof for 68 years. They all accept it as fact.
    I can't proof that a program can be written to determine if every other
    program halts. I can show the the proof that this can not be done
    is incorrect. This thread's title indicates that my prior efforts did
    mnot address the original proof, because these prior efforts can
    not be implemented as a Turing Machine. I have another method
    that can be implemented as a Turing Machine.

    > Karl Heinz Buchegger
    >
    Peter Olcott, Jul 26, 2004
    #8
  9. Peter Olcott wrote:
    >
    >
    > > But note: The proof you are attacking is based on the *assumption* that
    > > such a function exists.
    > >
    > > So when you attack the proof, and turn it around, all you end up with is:
    > > Based on the assumption that such a function exists, that function can be
    > > written.

    >
    > I end up with the fact that the proof that shows that it is impossible
    > is incorrect.


    The last time: You did not.
    What you did is: you modified the proof.
    But there is nothing wrong with the original proof. All its steps
    are correct.

    > This by itself is an amazing feat. No one has even
    > questioned this proof for 68 years.


    Thats because the proof is correct.

    > They all accept it as fact.
    > I can't proof that a program can be written to determine if every other
    > program halts. I can show the the proof that this can not be done
    > is incorrect.


    No you cannot. In order to show this, you *have to leave the proof
    as it is*. No modifications allowed. As soon as you modify the proof
    you are no longer proving or disproving the proof. You are proving
    or disproving something else.


    I will not respond any longer.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Jul 26, 2004
    #9
  10. Peter Olcott wrote:
    >
    > No one has even
    > questioned this proof for 68 years.


    I recommend reading
    Douglas R. Hofstadter
    Goedel, Escher, Bach

    The whole book turns around Goedels famous proof.
    In fact the Halting Problem and the way it is proofed
    is just a variation of Hilberts Problem and the way Goedel
    put it to an end. The book extends this and shows how
    this has implications and what can be learned from it
    in various other disciplines which range from computers
    to biology.
    And: While it is not an easy read (at least it wasn't for me),
    it is still fun to read and I would count it as one of the
    most important books I have ever read.

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Jul 26, 2004
    #10
  11. Peter Olcott

    Robert Low Guest

    Peter Olcott <> wrote:
    >is incorrect. This by itself is an amazing feat. No one has even
    >questioned this proof for 68 years. They all accept it as fact.


    You don't have much idea of what 'reading a proof' entails,
    do you? You go in waiting to be persuaded, and when you've
    finished reading it you understand why it's correct. That's
    kind of the point of proofs, you see.

    >I can't proof that a program can be written to determine if every other
    >program halts.


    Correct. (Because no such program can exist.)

    > I can show the the proof that this can not be done
    >is incorrect.


    Incorrect. There are various correct proofs that the
    halting problem is unsolvable available in undergraduate
    text books. In fact, it's not even clear to me just
    *which* proof you claim to be incorrect; I saw at least
    one correct proof posted in response to you.
    --
    Rob. http://www.mis.coventry.ac.uk/~mtx014/
    Robert Low, Jul 26, 2004
    #11
  12. Peter Olcott

    Anonymous Guest

    You got it Peter! Very good!

    "Peter Olcott" <> wrote in message
    news:SXSMc.134873$...
    > The Halting Problem can not be solved within the degree of
    > expressability of a TM. My solution only worked because of
    > its more limited degree of expressability.
    >
    > There is no such thing as a void function in a TM, thus there is
    > no way to make constructing the counter-example program
    > impossible for a TM.
    >
    >
    >
    >
    Anonymous, Jul 27, 2004
    #12
  13. Peter Olcott

    Bryan Olson Guest

    Peter Olcott wrote:
    > It is a very surprising turn of events. There was one message
    > That I read this morning that got me thinking. After I thought
    > about it I realized that my solution would not apply to Turing
    > Machines. Not that my solution required something more than
    > a Turing Machine, but something less.


    That much is right. A model of computation *less* powerful than
    Turing's may admit a program that decides the model's halting
    problem. Halting is undecidable in any programming language that
    is 'complete' in the sense of the Church-Turing thesis.


    --
    --Bryan
    Bryan Olson, Jul 27, 2004
    #13
  14. Peter Olcott

    Peter Olcott Guest

    "Bryan Olson" <> wrote in message news:...
    > Peter Olcott wrote:
    > > It is a very surprising turn of events. There was one message
    > > That I read this morning that got me thinking. After I thought
    > > about it I realized that my solution would not apply to Turing
    > > Machines. Not that my solution required something more than
    > > a Turing Machine, but something less.

    >
    > That much is right. A model of computation *less* powerful than
    > Turing's may admit a program that decides the model's halting
    > problem. Halting is undecidable in any programming language that
    > is 'complete' in the sense of the Church-Turing thesis.
    >
    >
    > --
    > --Bryan


    Well on to my proof of that case.
    Peter Olcott, Jul 27, 2004
    #14
  15. Peter Olcott

    Peter Olcott Guest

    "Anonymous" <> wrote in message news:4HgNc.3267$...
    > You got it Peter! Very good!
    >
    > "Peter Olcott" <> wrote in message
    > news:SXSMc.134873$...
    > > The Halting Problem can not be solved within the degree of
    > > expressability of a TM. My solution only worked because of
    > > its more limited degree of expressability.
    > >
    > > There is no such thing as a void function in a TM, thus there is
    > > no way to make constructing the counter-example program
    > > impossible for a TM.
    > >

    Except that I have now figured out how to solve it for Turing Machines
    with a Turing Machine. See my newest thread.
    Peter Olcott, Jul 27, 2004
    #15
  16. "Peter Olcott" <> wrote:

    > Well on to my proof of that case.


    Why bother? No one cares about that case.

    xanthian.



    --
    Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
    Kent Paul Dolan, Jul 27, 2004
    #16
  17. "Peter Olcott" <> wrote:

    > Except that I have now figured out how to solve it
    > for Turing Machines with a Turing Machine. See my
    > newest thread.


    No, you didn't, and just as in the case of your
    former bogus proof, no one needs to look at your
    current bogus proof to know otherwise.

    I'm sure you will spend another month or so calling
    all the people who understand what it means that the
    task you are claiming to have accomplished, has been
    proved to be impossible to accomplish, nasty names
    for trusting that entirely lucid, easily understood
    proof over your obfuscated muddle of a non-proof,
    again.

    You'll eventually find out you are wrong, again.

    You'll have learned nothing, as you learned nothing
    this time, and set off down the same barricaded
    path, again, no doubt.

    That's why what you have is called "INVINCIBLE
    ignorance"; nothing short of death can cure it.

    xanthian.




    --
    Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
    Kent Paul Dolan, Jul 27, 2004
    #17
  18. In message <HtZMc.136094$>,
    Peter Olcott <> writes
    >
    >"Jonathan Turkanis" <> wrote in message
    >news:...
    >>
    >> "Peter Olcott" <> wrote in message
    >> news:SXSMc.134873$...
    >> > The Halting Problem can not be solved within the degree of
    >> > expressability of a TM. My solution only worked because of
    >> > its more limited degree of expressability.
    >> >
    >> > There is no such thing as a void function in a TM, thus there is
    >> > no way to make constructing the counter-example program
    >> > impossible for a TM.

    >>
    >> I think I already asked you to stop posting this stuff, but you appear
    >> to have a halting problem.
    >>

    >
    >Well it looks like I am wrong that I am wrong again.
    >This time I won't bother with anything less than a full
    >refutation of the original proof. I do have a basis for
    >disproving the original proof.
    >
    >

    Do you know James Harris?

    --
    Richard Herring
    Richard Herring, Jul 27, 2004
    #18
  19. "Bryan Olson" <> wrote in message
    news:...
    > Peter Olcott wrote:
    > > It is a very surprising turn of events. There was one message
    > > That I read this morning that got me thinking. After I thought
    > > about it I realized that my solution would not apply to Turing
    > > Machines. Not that my solution required something more than
    > > a Turing Machine, but something less.

    >
    > That much is right. A model of computation *less* powerful than
    > Turing's may admit a program that decides the model's halting
    > problem. Halting is undecidable in any programming language that
    > is 'complete' in the sense of the Church-Turing thesis.


    Moreover, a language that admits a program that decides the halting problem
    cannot be powerful enough to program its own interpreter.
    Andrew Koenig, Jul 27, 2004
    #19
  20. "Peter Olcott" <> wrote in message
    news:5%iNc.332300$...

    > > That much is right. A model of computation *less* powerful than
    > > Turing's may admit a program that decides the model's halting
    > > problem. Halting is undecidable in any programming language that
    > > is 'complete' in the sense of the Church-Turing thesis.


    > Well on to my proof of that case.


    The trouble is that a computational model that is restricted enough to allow
    the halting problem to be proved is not very useful. In particular, any
    programming language that conforms to such a computational model cannot be
    strong enough to program an interpreter for its own language.
    Andrew Koenig, Jul 27, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dushkin
    Replies:
    0
    Views:
    350
    dushkin
    Apr 23, 2006
  2. Peter Olcott

    Solution to the halting Problem?

    Peter Olcott, Jul 21, 2004, in forum: C++
    Replies:
    117
    Views:
    2,172
    Howard
    Aug 10, 2004
  3. Peter Olcott
    Replies:
    245
    Views:
    3,638
    Will Twentyman
    Aug 21, 2004
  4. >parr\(*>

    Re: Halting Problem: Give up

    >parr\(*>, Aug 15, 2004, in forum: C++
    Replies:
    10
    Views:
    579
    edens rand mair fheal greykitten tomys des anges
    Aug 16, 2004
  5. Roedy Green

    The halting problem revisited

    Roedy Green, Mar 26, 2011, in forum: Java
    Replies:
    76
    Views:
    1,545
    javax.swing.JSnarker
    Apr 5, 2011
Loading...

Share This Page