P
D
David Hilsee
Peter Olcott said:
Off-topic, but I'll bite.
I went to that link expecting a lot more than I found. I was expecting a
very thorough proof that showed that the Halting Problem had a flaw. I kept
re-reading the page because I thought that I had missed something. I guess
I didn't, because all I found was a way to modify or create a program so
that it is possible to know if it will halt. Even then, the second
objection listed on that page shows that it doesn't always work. If I
misunderstood the solution, then feel free to correct me.
The first link on that page defines the halting problem very clearly: No
program can ever be written to determine whether any arbitrary program will
halt. The key phrase here is "any arbitrary." If you try to refute the
claim by modifying the code, then you cannot claim that your solution works
for an arbitrary program. When the claim says arbitrary, it means any
program that could ever exist. Limiting the considered programs to special
cases does not refute the claim. It is very easy for anyone to produce
special cases where it is certain that the program will halt.
In short, your assertion that the "possibility of creating one or more
instances of WillHalt() that permit LoopIfHalts() to function does not
refute this method" is incorrect. The meaning of "any arbitrary" is not
negotiable. Like I said, if I misunderstood what that link was trying to
say, correct me. I'm very tired right now and it's possible that I
misinterpreted something.
Nice domain, though.
T
tom_usenet
What's this got to do with standard C++?
Tom
P
Peter Olcott
David Hilsee said:
It works FOR any arbitrary program. It does not work WITH any
arbitrary program. The original analyzer had to be changed. Now
every program analyzed will result in Halting or Not Halting, as long
as the security of the solution has not been violated. If it has been
violated, then after this has been corrected. it will now work with
the program that it did not work for.
T
tom_usenet
Do you understand how proof by contradiction works? It seems not. See:
http://zimmer.csufresno.edu/~larryc/proofs/proofs.contradict.html
I found this bit particularly amusing:
"The LoopIfHalts() function depends upon access to the return value of
the WillHalt() function. If every possible access to this value is
completely denied to every other program, then LoopIfHalts() can not
possibly effect the WillHalt() function."
So, in other works, WillHalt is no longer a function that can check
whether a program halts or not, since you've just said you can't get
at the return value!
Tom
S
Stewart Gordon
Peter said:
You mean you're planning to sell that page?
That seems to be a bit of a proof by semantic shift. The link you cited
states the theorem specifically refers to functions that return the
result.
Anyway, I still can't see how this refutes the seemingly obvious statement:
If it is possible to write a function that calculates X, then it is
possible to write a function that calculates X and returns X to the caller.
Stewart.
S
Stewart Gordon
Stewart Gordon wrote:
What I actually meant to say is: One of the links you cited states the
theorem specifically with respect to functions that return the result.
But still....
And by the way, I've noticed that the term "halting problem" has two
very different definitions, based on the double meaning of "problem":
(a) the challenge itself of finding an algorithm to determine whether an
algorithm will halt
(b) the fact that no such algorithm can exist.
Definition (a) is the one I had always understood, and it took me a
moment to get my head around your using definition (b), only to be
followed by a semantic shift to (a) about 1/5 of the way down.
Stewart.
<snip>
What I actually meant to say is: One of the links you cited states the
theorem specifically with respect to functions that return the result.
But still....
And by the way, I've noticed that the term "halting problem" has two
very different definitions, based on the double meaning of "problem":
(a) the challenge itself of finding an algorithm to determine whether an
algorithm will halt
(b) the fact that no such algorithm can exist.
Definition (a) is the one I had always understood, and it took me a
moment to get my head around your using definition (b), only to be
followed by a semantic shift to (a) about 1/5 of the way down.
Stewart.
K
Keith H Duggar
Perhaps this was actually intended as a joke of some kind.
If not, it's good to keep in mind that the internet, in my
experience, is replete with misinformation.
Or we could conclude that the NIST definition is flawed or
your interpretation is flawed in some way. Indeed, I believe
the interpretation is flawed as the NIST definition seems
slightly ambiguous to me. Perhaps this phrasing is better
No program can ever be written to determine whether
any and all programs will halt.
Then again this phrasing seems to require an infinite amount
of work (this is the problem with natural language ambiguity)
though it seems to be more inline with the framing of the
halting problem as a question of decidability.
The language
ATM = { <M,w> | M is a Turing Machine and M accepts w }
is undecidable.
The authors misinterpretation of the halting problem seems to
come into play with his refute of objection (2) we he believes
it is sufficient to show that the proof does not apply to SOME
program. When it fact the opposite is true. The proof only
need to apply to a SINGLE program to be valid since this
single program would then be undecidable and since it is a
member of ATM then ATM is undecidable. In fact, the proof
only need to apply to a SINGLE program on a SINGLE input to
be valid.
The author also assumes that the proof requires the ability
to RUN and then READ the output of any program. This is not
the case. In fact, the proof assumes the ability to SIMULATE
or even ANALYZE in any way a program. Were we only able to
RUN a TM then the proof of the halting problem is even
simpler since it is impossible to even create a "WillHalt"
function. For example
M1 = loops on w1
WillHalt ( M1 , w1 ) = ?
In trying ot run M1 on w1 WillHalt will simply loop and thus
not halt. On the other hand, a simulation of M1 can stop at any
time.
Yet, even with the additional power to simulate or analyze
any and every TM it is impossible to decide language ATM.
If not, it's good to keep in mind that the internet, in my
experience, is replete with misinformation.
Or we could conclude that the NIST definition is flawed or
your interpretation is flawed in some way. Indeed, I believe
the interpretation is flawed as the NIST definition seems
slightly ambiguous to me. Perhaps this phrasing is better
No program can ever be written to determine whether
any and all programs will halt.
Then again this phrasing seems to require an infinite amount
of work (this is the problem with natural language ambiguity)
though it seems to be more inline with the framing of the
halting problem as a question of decidability.
The language
ATM = { <M,w> | M is a Turing Machine and M accepts w }
is undecidable.
The authors misinterpretation of the halting problem seems to
come into play with his refute of objection (2) we he believes
it is sufficient to show that the proof does not apply to SOME
program. When it fact the opposite is true. The proof only
need to apply to a SINGLE program to be valid since this
single program would then be undecidable and since it is a
member of ATM then ATM is undecidable. In fact, the proof
only need to apply to a SINGLE program on a SINGLE input to
be valid.
The author also assumes that the proof requires the ability
to RUN and then READ the output of any program. This is not
the case. In fact, the proof assumes the ability to SIMULATE
or even ANALYZE in any way a program. Were we only able to
RUN a TM then the proof of the halting problem is even
simpler since it is impossible to even create a "WillHalt"
function. For example
M1 = loops on w1
WillHalt ( M1 , w1 ) = ?
In trying ot run M1 on w1 WillHalt will simply loop and thus
not halt. On the other hand, a simulation of M1 can stop at any
time.
Yet, even with the additional power to simulate or analyze
any and every TM it is impossible to decide language ATM.
O
Old Wolf
Peter Olcott said:
Please quit your courses immediately and sign up for a course on
elementary logic.
Your argument is akin to this one: "If my computer had no CPU, it
wouldn't work. Therefore my computer doesn't work."
(replace 'my computer' with 'the original proof' and 'no CPU' with
'no return value for WillHalt').
Some other logical flaws in your argument:
You have misunderstood the OP (Original Proof). The OP starts with:
X = "bool WillHalt() exists"
where WillHalt and its return value are described on the original
page. It explains (in English) why 'X' is equivalent to the
statement of the halting problem.
You are arguing about "void WillHalt()", which has nothing
to do with the OP.
The OP is actually a "reductio ad absurdum". Its structure is
"if X is possible then Y is possible. But Y is clearly impossible."
Many people have trouble grasping this concept (I have no idea why).
If your proof also shows that Y is impossible then you have
only strengthened the OP! If your proof shows that Y is possible
then you have not added to or detracted from it. In order to attack
the OP, you could do one of the following:
- show that X is not equivalent to the halting problem
- show that "if X is possible then Y is possible" is not correct
- show that "Y is impossible" is not correct
You also seem to be of the opinion that refuting the OP
means that you have proved that there is a solution to the HP.
Far from it. Even if you do refute the OP, then there are dozens
of other non-equivalent proofs of the HP. Even if you go further and
refute all known proofs of the HP, it doesn't make it wrong.
It just means that we don't know whether or not there is a solution.
You would actually have to find a solution, or prove that a solution
exists (a very different matter to finding flaws in non-existence proofs).
Finally, most of the effort in your 'proof' seems to have gone into
showing "if bool WillHalt() exists, then void WillHalt() exists". This
is as obvious as it is irrelevant, because the existence of such a
function does not affect the OP. When you revise your page, you should
concentrate on explaining why you think such a function affects the HP
or the OP, and perhaps provide your proof as a footnote.
P
Peter Olcott
tom_usenet said:
In case you are unfamiliar, the LoopIfHalts() function is the
counter-example used to prove that the Halting Problem
can not be solved. By making LoopIfHalts() impossible
to construct, the original basis of the halting Problem ceases
to exist.
P
Peter Olcott
Stewart Gordon said:You mean you're planning to sell that page?
That seems to be a bit of a proof by semantic shift. The link you cited
states the theorem specifically refers to functions that return the
result.
Although the corrected halt analyzer is no longer prohibited from
determining if any program halts, it had to be modified.
Since it is possible to write X that does not return a value to its caller, then
its possible to prevent the basis for proving that solving the Halting Problem
is impossible to exist.
In all thoses instances where you do not return the result to the caller,
you have solved the Halting Problem.
P
Peter Olcott
Stewart Gordon said:
That's just an example of the original unsolved problem.
P
Peter Olcott
Keith H Duggar said:
There does not exist any program in the set of all possible
programs a program that would cause my method to fail to
provide the correct halting result.
D
David Hilsee
Peter Olcott said:
This paragraph is contradictory:
"The possibility of creating one or more instances of WillHalt() that permit
LoopIfHalts() to function does not refute this method. In other words
defeating the security in less than every possible case does not prove that
this method does not work. One single case where the security is not
circumvented proves that the idea still works. Even a single case proves
that this method still works because this single case would form the
required single counter-example to refute the claim:
No program can ever be written to determine whether any arbitrary program
will halt"
This paragraph admits that it is possible to create a LoopIfHalts function
that causes the WillHalt() method to fail, and then says that this is not
proof that the method does not work. However, it is most certainly proof
that the method does not work in every case, which means that it fails to
meet the requirement, which is that it must work for "any arbitrary
program." One single case where the "security is not circumvented" only
proves that the method works for that single case, which is not proof that
it works for any program. That last sentence is confusing, because it
states that a program that can work for a single case is enough to refute
the claim that a program cannot work for every case. This is obviously
false.
BTW, I think the first link returned on my Google search
(http://www.cgl.uwaterloo.ca/~csk/halt/) had a more applicable description
and better source code than the one on halting-problem.com.
P
Peter Olcott
"The possibility of creating one or more instances of WillHalt() that permit
Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
It would be like trying to prove that no cars run by taking one car
and driving it into a tree, so that it does not run. What about all the
cars that were not driven into trees? Don't all these other cars prove
that cars run?
It does work for any arbitrary program as its input parameter.
There is no program that it can not correctly determine halting
status. It even works for the original Halting Problem example,
as input.
Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
It would be like trying to prove that no cars run by taking one car
and driving it into a tree, so that it does not run. What about all the
cars that were not driven into trees? Don't all these other cars prove
that cars run?
It does work for any arbitrary program as its input parameter.
There is no program that it can not correctly determine halting
status. It even works for the original Halting Problem example,
as input.
O
Owen Jacobson
There is no way to put this nicely: you are completely, 100% incorrect.
The nature of a formal proof is such that a single counterexample
disproves it.
If the thesis was "All cars run correctly." then finding a single broken
car disproves the thesis, even in the presence of an infinite number of
similar, working cars. The halting problem is similar: "There is[0] an
algorithm that can determine if any given algorithm will halt, that will
also itself halt for all possible inputs."[1]
You refer in your proof to memory protection and specific hardware
devices; none of these are relevant to the halting problem, which deals
solely with algorithms and their inputs and outputs -- usually, the
initial and final states of an ideal Turing machine.
Also sprach Peter Olcott:
Then it's not a general solution to the halting problem, is it? It's a
solution that applies to a subset of possible algorithms.
And now, a practical example. Does the following algorithm, as
expressed in C, halt (terminate)? Would it halt if the maximum value of a
long was unbounded (this is, after all, merely a C implementation of an
algorithm written with no respect for bytes)?
int main () {
long i, j, k;
for(i=j=k=1;--j||k;k=j?i%j?k:k-j
j=i+=2));}
Spoiler:
Guvf cebtenz frnepurf hagvy vg svaqf na bqq cresrpg ahzore, gura unygf. Vg
unygf vs naq bayl vs fhpu n ahzore rkvfgf, juvpu vf n znwbe bcra dhrfgvba
va zngurzngvpf. Fb, nsgre praghevrf bs jbex, zngurzngvpvnaf unir lrg gb
qvfpbire jurgure n fvzcyr P cebtenz unygf.
<uggc://ra.jvxvcrqvn.bet/jvxv/Unygvat_ceboyrz>
[0] Read as 'Define', if you like.
[1] Actually, it also covers knowing the input to the algorithm under test.
D
David Hilsee
Peter Olcott said:
The challenge is not to produce a program that works correctly in general.
The phrase "in general" really means "some of the time," and it's easy to
produce a program that sometimes works. The challenge is to produce a
program that works on all input programs. That is, it always works, no
matter what.
Sticking with the car analogy, if I challenge you to produce a car that
always worked if I drove it into any tree, and you produced a car that works
when one drives it into oak trees but not when one drives it into pine
trees, then you have not met my challenge. The challenge is not to produce
a car that runs after driving it into certain trees, so the car does not
meet the requirements described in the challenge.
You already said that it does not work for a specific instance, so it does
not work for any arbitrary program. To work for an arbitrary program it
must work for all programs, including the "one specific instance" that, by
your own admission above, it fails to handle correctly.
J
Jonathan Turkanis
Peter Olcott said:
1. The halting problem is not an assertion (it's a set of strings or
integers) and so can't be proven or disproven.
2. There are lots of interesting problems in the theory of computation
which haven't already been solved. Try working on one of those.
Jonathan
T
tom_usenet
*If* a solution to the halting problem exists, *then* it *must* be
possible to write WillHalt such that it returns to a caller whether
the passed program halts or not. The fact that you can write a
function that doesn't return the result to the caller is of no
relevance whatsoever. The rest follows directly from there.
If you can't see it, it's really not worth discussing further; if your
logic is that far off track then I'd just be banging my head against a
brick wall.
Tom
S
Stewart Gordon
Peter Olcott wrote:
That doesn't follow. If it's possible to write a function that
calculates X, how can it be impossible to modify it so that it returns
X? Can you supply an example of such a function?
No I haven't. Disproving the validity of a proof is very different from
disproving the original theorem. The people who found fault in the many
attempted proofs of Fermat's Last Theorem didn't succeed in discovering
that Fermat's Last Theorem is actually false.
The statement "it is possible to write X that does not return a value to
its caller" depends on the statement "it is possible to write X". I.e.
we need to come up with the algorithm itself, before we can write it to
either return its result or not return its result.
Stewart.
That doesn't follow. If it's possible to write a function that
calculates X, how can it be impossible to modify it so that it returns
X? Can you supply an example of such a function?
No I haven't. Disproving the validity of a proof is very different from
disproving the original theorem. The people who found fault in the many
attempted proofs of Fermat's Last Theorem didn't succeed in discovering
that Fermat's Last Theorem is actually false.
The statement "it is possible to write X that does not return a value to
its caller" depends on the statement "it is possible to write X". I.e.
we need to come up with the algorithm itself, before we can write it to
either return its result or not return its result.
Stewart.