Refutation of the DisProof of the Halting Problem

P

Peter Olcott

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

Jonathan Turkanis

Peter Olcott said:
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
 
M

Marc Goodman

Peter said:
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.
 
P

Peter Olcott

Jonathan Turkanis said:
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.
 
P

Peter Olcott

Marc Goodman said:
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.
 
T

The Ghost In The Machine

In sci.logic, Peter Olcott
<[email protected]>
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.

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. :)
 
K

Karl Heinz Buchegger

Peter said:
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.
 
P

Peter Olcott

Karl Heinz Buchegger said:
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.
 
K

Karl Heinz Buchegger

Peter said:
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.
 
K

Karl Heinz Buchegger

Peter said:
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.
 
R

Robert Low

Peter Olcott said:
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.
 
B

Bryan Olson

Peter said:
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.
 
P

Peter Olcott

Bryan Olson said:
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.
 
P

Peter Olcott

Anonymous said:
You got it Peter! Very good!
Except that I have now figured out how to solve it for Turing Machines
with a Turing Machine. See my newest thread.
 
K

Kent Paul Dolan

Peter Olcott said:
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.
 
R

Richard Herring

In message said:
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?
 
A

Andrew Koenig

Bryan Olson said:
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.
 
A

Andrew Koenig

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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top