117  7081 
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:qG*********************@bgtnsc04-news.ops.worldnet.att.net... www.halting-problem.com
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.
--
David Hilsee
On Wed, 21 Jul 2004 02:38:14 GMT, "Peter Olcott"
<ol****@worldnet.att.net> wrote: www.halting-problem.com
What's this got to do with standard C++?
Tom
"David Hilsee" <da*************@yahoo.com> wrote in message news:w5********************@comcast.com... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:qG*********************@bgtnsc04-news.ops.worldnet.att.net... www.halting-problem.com
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.
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.
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.
--
David Hilsee
On Wed, 21 Jul 2004 12:04:55 GMT, "Peter Olcott"
<ol****@worldnet.att.net> wrote: 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.
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.
Do you understand how proof by contradiction works? It seems not. See: http://zimmer.csufresno.edu/~larryc/...ontradict.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
Peter Olcott wrote: www.halting-problem.com
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.
--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Stewart Gordon wrote:
<snip> 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.
<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.
--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
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. The NIST definition of the Halting Problem is assumed:
No program can ever be written to determine whether
any arbitrary program will halt
This version of the Halting Problem is supposed to be
analogous to every other version, thus valid refutations
of this version should equally apply (with adaptation)
to all other versions.
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.
"Peter Olcott" <ol****@worldnet.att.net> wrote: www.halting-problem.com
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:
Method of this Proof
X = The solution to the Halting Problem
Y = The basis of the original proof
Z = The basis of this proof
Structure of Original Proof---->Y makes X impossible
Structure of This Proof--------->Z makes Y impossible
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.
"tom_usenet" <to********@hotmail.com> wrote in message news:re********************************@4ax.com... On Wed, 21 Jul 2004 12:04:55 GMT, "Peter Olcott"
<ol****@worldnet.att.net> wrote:
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.
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.
Do you understand how proof by contradiction works? It seems not. See:
http://zimmer.csufresno.edu/~larryc/...ontradict.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
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.
"Stewart Gordon" <sm*******@yahoo.com> wrote in message news:cd**********@sun-cc204.lut.ac.uk... Peter Olcott wrote:
www.halting-problem.com
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.
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.
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.
Stewart.
--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
"Stewart Gordon" <sm*******@yahoo.com> wrote in message news:cd**********@sun-cc204.lut.ac.uk... Stewart Gordon wrote:
<snip> 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. <snip>
That's just an example of the original unsolved problem.
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.
--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
"Keith H Duggar" <du****@mit.edu> wrote in message news:b4*************************@posting.google.co m... 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
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.
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.
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Gb********************@bgtnsc05-news.ops.worldnet.att.net...
"Keith H Duggar" <du****@mit.edu> wrote in message
news:b4*************************@posting.google.co m... 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
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.
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.
--
David Hilsee
> "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.
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?
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."
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.
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.
--
David Hilsee
On Thu, 22 Jul 2004 02:23:39 +0000, Peter Olcott wrote: "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.
Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
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.
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?
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:
In all thoses instances where you do not return the result to the
caller, you have solved the Halting Problem.
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.
--
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Ly********************@bgtnsc04-news.ops.worldnet.att.net... Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
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.
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?
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.
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.
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.
--
David Hilsee
"Peter Olcott" <ol****@worldnet.att.net> wrote: www.halting-problem.com
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
On Thu, 22 Jul 2004 00:35:24 GMT, "Peter Olcott"
<ol****@worldnet.att.net> wrote: 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.
*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
Peter Olcott wrote:
<snip> 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.
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.
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?
In all thoses instances where you do not return the result to the
caller, you have solved the Halting Problem.
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.
--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Peter Olcott wrote:
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.
Hmm.
There is a wall in front of me. I can see it. But if I close my eyes, the wall
vanishes and thus I have proven that there is no wall.
--
Karl Heinz Buchegger kb******@gascad.at
> 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.
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?
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]
I am not claiming that every implementation of a Halt() analyzer always
works correctly. If I was claiming this then finding a single instance of
a Halt analyzer that does not work correctly would refute my claim.
I am claiming that the Halt analyzer that is implemented according to
my method would work correctly all the time. As proof of this, this
method would correctly process the original Halting Problem, and
determine that it would halt. I will post this example later on.
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.
Under the assumption that "any computation that can be carried out
by mechanical means can be carried out by some Turing Machine."
I don't think that it says anywhere in the literature that a solution to
the Halting Problem that can not be implemented as a Turing Machine
doesn't count.
Also sprach Peter Olcott:
In all thoses instances where you do not return the result to the
caller, you have solved the Halting Problem.
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.
Not at all. The algorithms that test the return value of the Halt analyzer
are no longer in the set of possible algorithms. They become syntactically
incorrect once the Halt analyzer is changed from returning bool, to returning
void (nothing).
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));
}
This is not the Halting Problem. Also from what I understand this does
not form an analytical impossibility.
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.
--
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.
In article <u-********************@comcast.com>,
David Hilsee <da*************@yahoo.com> wrote: "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Ly********************@bgtnsc04-news.ops.worldnet.att.net... Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
The challenge is not to produce a program that works correctly in general.
The phrase "in general" really means "some of the time,"
No.
A "general solution" to a problem is a solution that works *all* *the*
*time*. Artificially restricting the set of problems you might be able
to solve means you're only solving it for a set of special cases; this
is rarely interesting.
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.
Yes. This is what's referred to in mathese as a "general solution".
dave
--
Dave Vandervies dj******@csclub.uwaterloo.ca
[This] is otherwise known as 'learning by experience'. I don't often
come across people who publicly state they're not interested in that.
--Arthur van der Harg in the scary devil monastery
"David Hilsee" <da*************@yahoo.com> wrote in message news:u-********************@comcast.com... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Ly********************@bgtnsc04-news.ops.worldnet.att.net... Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
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.
Big difference between the former and the latter. My method works
on the former, yet will not work if you smash the machine that it is
working on, this could be construed to be included in the latter.
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?
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
That its not my claim, it is for any input. To be analogous, any grade
or brand of gasoline.
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.
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.
You already said that it does not work for a specific instance, so it does
It works for all inputs. It does not work in all instances such as destroying
the machine that is is running on.
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.
--
David Hilsee
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:40***************@gascad.at... Peter Olcott wrote:
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.
Hmm.
There is a wall in front of me. I can see it. But if I close my eyes, the wall
vanishes and thus I have proven that there is no wall.
--
Karl Heinz Buchegger
kb******@gascad.at
It is not merely an input restriction, if this is all that it is, then I would have
shown nothing of consequence. I have changed the Halt analyzer such that
programs that check its return value can not exist. They can not exist because
they become syntactically incorrect. My idea works for all programs that
can exist.
"tom_usenet" <to********@hotmail.com> wrote in message news:j8********************************@4ax.com... On Thu, 22 Jul 2004 00:35:24 GMT, "Peter Olcott"
<ol****@worldnet.att.net> wrote:
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.
*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.
You can do this, and my original unmodified halt analyzer can determine
that this function would halt, even though it could not make this determination
itself. My uncorrupted halt analyzer still works for all inputs.
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
"Dave Vandervies" <dj******@csclub.uwaterloo.ca> wrote in message
news:cd**********@rumours.uwaterloo.ca... In article <u-********************@comcast.com>,
David Hilsee <da*************@yahoo.com> wrote:"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Ly********************@bgtnsc04-news.ops.worldnet.att.net... Providing one specific instance where the method can be made to fail
does not at all refute that the method works correctly in general.
The challenge is not to produce a program that works correctly in
general.The phrase "in general" really means "some of the time,"
No.
A "general solution" to a problem is a solution that works *all* *the*
*time*. Artificially restricting the set of problems you might be able
to solve means you're only solving it for a set of special cases; this
is rarely interesting.
This is the second time in the past few days that someone has taken
something that I said using common parlance as something completely
different. I must be really good at confusing people.
The meaning I was using is the common, everyday meaning. Example usage: "In
general, I like cake, but I don't like carrot cake." In that case, it
should be taken to mean "usually" or "generally." If one were trying to say
that a solution was a general solution, they should probably avoid using the
phrase "in general" because that can mean something completely different. I
assumed that Peter meant "usually" because otherwise the statement that he
made wouldn't make sense. Also, he wasn't using a whole lot of "mathese,"
or at least nothing on the level of "general solution," so I had no reason
to suspect that he meant something other than "usually." I'm pretty sure
that he was not restricting the set of problems because he had already said
that he is considering the entire set of all possible programs as input.
--
David Hilsee
> A "general solution" to a problem is a solution that works *all* *the* *time*. Artificially restricting the set of problems you might be able
to solve means you're only solving it for a set of special cases; this
is rarely interesting.
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.
My solution works on all inputs. It even determines that the original
halting problem will halt. It does not work under all conditions. It
does not work:
(1) If you destroy the computer.
(2) Turn the computer off
(3) Unplug the computer
(4) Erase the software
(5) Modify the executable adding bugs.
Since it does work on ALL INPUTS it is a general solution
to the Halting Problem.
Yes. This is what's referred to in mathese as a "general solution".
dave
--
Dave Vandervies dj******@csclub.uwaterloo.ca
[This] is otherwise known as 'learning by experience'. I don't often
come across people who publicly state they're not interested in that.
--Arthur van der Harg in the scary devil monastery
> > 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.
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?
The function that does not return a value does correctly determine
halting for all inputs, including the function that does return this value.
There is no possible case where the original Halting Problem can
arise with the corrected function. You can make it not work by
adding bugs to its code. You can also make it not work by
destroying the computer that it is running on. Neither of these
refute the fact that it solves the Halting Problem. The only thing
that would refute that it solves the Halting Problem would be to
find any program that it can not correctly determine halting for.
Since it can correctly determine halting for the original Halting
Problem, the original Halting Problem is completely refuted.
In all thoses instances where you do not return the result to the
caller, you have solved the Halting Problem.
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
A single valid counter-example is all that is required. I provided that.
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.
This is not true. This is not required. I did not prove that a program
that can determine whether or not any arbitrary program halts must
exist. All that I did was show that the original proof was in error in
concluding that it can't exist.
Stewart.
--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:yn*********************@bgtnsc04-news.ops.worldnet.att.net... You already said that it does not work for a specific instance, so it
does
It works for all inputs. It does not work in all instances such as
destroying the machine that is is running on.
I think I get what you're saying now. That paragraph (which has now changed
to provide better wording) claiming that one can make a LoopIfHalts that
fails is not about creating new input source, it is about modifying (on the
page, it is referred to as "corrupting") the example so it no longer works.
Originally, it sounded like the claim was that a modified version of the
source you provided is somehow invalid input and can be ignored.
For example, I thought you were saying that the following program "doesn't
count."
// Some source taken from http://www.cgl.uwaterloo.ca/~csk/halt/
int WillHaltWithReturnValue(string SourceCode, string InputData) {
if (TheProgramWillHalt(SourceCode, InputData))
return TRUE;
else if (TheProgramWillNotHalt(SourceCode, InputData))
return FALSE;
else
return UNKNOWN;
}
bool stops_on_self( char * program ) {
return WillHaltWithReturnValue( program, program ) == TRUE;
}
bool bobs_yer_uncle( char * program ) {
if( stops_on_self( program ) ) {
while( 1 ) {}
return false;
} else {
return false;
}
}
Now you can apply the same reasoning from the link I provided to show that
your program does not work for this case, because the new
WillHaltWithReturnValue function does the same exact thing that your
WillHalt() does except it returns the conclusion. If
WillHaltWithReturnValue() can be proven to not work (and it can, as shown in
the link I provided), then that means that WillHalt() does not work because
the modifications made do not affect the conclusion that the function
reaches. This code was partially inspired by tom_usenet's comment that
"*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." Throughout the discussion, I thought you had already
considered the above source as an input, but for some reason you were
refusing to accept it as valid. Tom's comment triggered a thought that this
might not be the case, so I decided to explain his statement in more detail.
--
David Hilsee
"David Hilsee" <da*************@yahoo.com> wrote in message news:s8********************@comcast.com... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:yn*********************@bgtnsc04-news.ops.worldnet.att.net...
You already said that it does not work for a specific instance, so it does
It works for all inputs. It does not work in all instances such as
destroying the machine that is is running on.
I think I get what you're saying now. That paragraph (which has now changed
to provide better wording) claiming that one can make a LoopIfHalts that
fails is not about creating new input source, it is about modifying (on the
page, it is referred to as "corrupting") the example so it no longer works.
Originally, it sounded like the claim was that a modified version of the
source you provided is somehow invalid input and can be ignored.
All syntactically correct programs are valid input.
In theory I could also include syntactically incorrect
programs, and then output compiler error messages.
For example, I thought you were saying that the following program "doesn't
count."
// Some source taken from http://www.cgl.uwaterloo.ca/~csk/halt/
int WillHaltWithReturnValue(string SourceCode, string InputData) {
if (TheProgramWillHalt(SourceCode, InputData))
return TRUE;
else if (TheProgramWillNotHalt(SourceCode, InputData))
return FALSE;
else
return UNKNOWN;
}
bool stops_on_self( char * program ) {
return WillHaltWithReturnValue( program, program ) == TRUE;
}
bool bobs_yer_uncle( char * program ) {
if( stops_on_self( program ) ) {
while( 1 ) {}
return false;
} else {
return false;
}
}
Now you can apply the same reasoning from the link I provided to show that
your program does not work for this case, because the new
WillHaltWithReturnValue function does the same exact thing that your
WillHalt() does except it returns the conclusion. If
Nope. Its not like that. My void WillHalt() does determine that the
above sequence of programs will halt. The corrupted version can't
determine whether or not the above sequence will halt, but my
version can always make this determination correctly.
My void WillHalt() is not locked into the double-bind as the
corrupted version is. My version can determine that the corrupted
version will halt, and not have this used to negate the result.
WillHaltWithReturnValue() can be proven to not work (and it can, as shown in
the link I provided), then that means that WillHalt() does not work because
the modifications made do not affect the conclusion that the function
reaches. This code was partially inspired by tom_usenet's comment that
This is the tricky part. It actually does modify the conclusion that it
reaches. If everything else is the same, except in one case you return
the result to the caller, and in the other case you do not return the result
to the caller, the result differs. The reason that the result differs is that
in one case the result is fed back to the program that you are analyzing,
and in the other case this result is not fed back. This changes the way that
the analyzed program behaves, thus chaning the result of your analysis.
"*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."
No sorry that is merely a false statement.
Throughout the discussion, I thought you had already
considered the above source as an input, but for some reason you were
refusing to accept it as valid. Tom's comment triggered a thought that this
might not be the case, so I decided to explain his statement in more detail.
--
David Hilsee
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:6z*********************@bgtnsc04-news.ops.worldnet.att.net... WillHaltWithReturnValue() can be proven to not work (and it can, as
shown in the link I provided), then that means that WillHalt() does not work
because the modifications made do not affect the conclusion that the function
reaches. This code was partially inspired by tom_usenet's comment that
This is the tricky part. It actually does modify the conclusion that it
reaches. If everything else is the same, except in one case you return
the result to the caller, and in the other case you do not return the
result to the caller, the result differs. The reason that the result differs is
that in one case the result is fed back to the program that you are analyzing,
and in the other case this result is not fed back. This changes the way
that the analyzed program behaves, thus chaning the result of your analysis.
I didn't think that I was going to have to post something else to further my
explanation, but I guess I was wrong.
You cannot argue that the result is different. While it is true that the
code is different and the characters written to the screen are different,
the ANSWER (AKA conclusion) is the same for every input. That is, for every
input that WillHalt() displays "The Program Will Halt",
WillHaltWithReturnValue() will return TRUE, and for every input that
WillHalt() displays "The Program Will Not Halt", WillHaltWithReturnValue()
will return FALSE, and for every input that WillHalt() displays "Security
Has Been Breached, Take Corrective Action", WillHaltWithReturnValue() will
return UNKNOWN. If you're trying to say that there is a case where
WillHaltWithReturnValue() and WillHalt() can come to a different conclusion
when passed the same source, then you're either grasping at straws or just
plain wrong. The only way that could be possible is if SecureOutput() does
something that changes the conclusion, and in that case, I would just make
the code that changes the conclusion a part of WillHaltWithReturnValue() so
the return values still match the screen output.
Therefore, since WillHalt() reaches the same conclusion
WillHaltWithReturnValue() does for every input source, and
WillHaltWithReturnValue() can be shown to not work for the input I gave, it
follows that WillHalt() also will not work for the input I gave. In the
original halting problem, WillHalt() failed because its return value could
be shown to contradict itself. In this case, to avoid that contradiction,
the value of WillHaltWithReturnValue() must not match the output that
WillHalt() wrote to the screen, and that is impossible.
--
David Hilsee
In article <ZK*********************@bgtnsc04-news.ops.worldnet.att.net>,
Peter Olcott <ol****@worldnet.att.net> wrote [losing attributions on
quoted material]: 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
A single valid counter-example is all that is required. I provided that.
You demonstrated the existence of a program and input for which it's
possible to determine that it can halt. You have not proven anything
about any other program or input, or about "programs and input"
in general.
Please apply your solution to the halting program to this program and tell
us whether it halts on the input "1". Assume a correctly implemented
bignum library and the generally accepted mathematical definition of
"perfect number".
--------
#include "bignum.h"
int main()
{
bignum b=read_bignum_from_input();
while(true)
{
if(is_bignum_a_perfect_number(b))
return 0;
b+=BIGNUM_TWO;
}
/*not reached*/
}
--------
If you are not able to do this, you haven't solved the halting problem.
Solutions that only apply to some special case are Not Interesting.
Are you really so thick that you're Not Getting This, or are you just
trolling?
dave
--
Dave Vandervies dj******@csclub.uwaterloo.ca
The full rant is left as an exercise for the motivated reader.
--David Rush in comp.lang.scheme
> If you are not able to do this, you haven't solved the halting problem. Solutions that only apply to some special case are Not Interesting.
If you want to be completely precise, then I have not actually
solved the Halting Problem, yet have proven that the original
proof that a solution is impossible, is incorrect.
Are you really so thick that you're Not Getting This, or are you just
trolling?
dave
--
Dave Vandervies dj******@csclub.uwaterloo.ca
The full rant is left as an exercise for the motivated reader.
--David Rush in comp.lang.scheme
> You cannot argue that the result is different. While it is true that the code is different and the characters written to the screen are different,
the ANSWER (AKA conclusion) is the same for every input. That is, for every
input that WillHalt() displays "The Program Will Halt",
WillHaltWithReturnValue() will return TRUE, and for every input that
WillHalt() displays "The Program Will Not Halt", WillHaltWithReturnValue()
will return FALSE,
No that is simply not the case.
http://home.att.net/~olcott/halting/example.html
If you walk through an execution trace of the above int WillHalt(LoopIfHalts, LoopIfHalts)
the result is that WillHalt() returns UNKNOWN, thus LoopIfHalt() halts. It returns
UNKNOWN specifically because bool WillHalt() knows that it can't say that LoopIfHalt()
halts, because this makes it not halt. Therefore you fall through to the other conditions.
If you walk through the same execution trace with void WillHalt() you get a
completely different result. You get this different result specifically because
void WillHalt() does not feed its result back to its caller, thus modifying
the behavior of its caller. Since the caller is also the program being analyzed,
then different behavior by the caller entails a different result from the analysis.
and for every input that WillHalt() displays "Security
Has Been Breached, Take Corrective Action", WillHaltWithReturnValue() will
return UNKNOWN. If you're trying to say that there is a case where
WillHaltWithReturnValue() and WillHalt() can come to a different conclusion
when passed the same source, then you're either grasping at straws or just
plain wrong. The only way that could be possible is if SecureOutput() does
something that changes the conclusion, and in that case, I would just make
the code that changes the conclusion a part of WillHaltWithReturnValue() so
the return values still match the screen output.
Therefore, since WillHalt() reaches the same conclusion
WillHaltWithReturnValue() does for every input source, and
WillHaltWithReturnValue() can be shown to not work for the input I gave, it
follows that WillHalt() also will not work for the input I gave. In the
original halting problem, WillHalt() failed because its return value could
be shown to contradict itself. In this case, to avoid that contradiction,
the value of WillHaltWithReturnValue() must not match the output that
WillHalt() wrote to the screen, and that is impossible.
--
David Hilsee
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:F9********************@bgtnsc05-news.ops.worldnet.att.net... You cannot argue that the result is different. While it is true that
the code is different and the characters written to the screen are
different, the ANSWER (AKA conclusion) is the same for every input. That is, for
every input that WillHalt() displays "The Program Will Halt",
WillHaltWithReturnValue() will return TRUE, and for every input that
WillHalt() displays "The Program Will Not Halt",
WillHaltWithReturnValue() will return FALSE,
No that is simply not the case.
http://home.att.net/~olcott/halting/example.html
If you walk through an execution trace of the above int
WillHalt(LoopIfHalts, LoopIfHalts) the result is that WillHalt() returns UNKNOWN, thus LoopIfHalt() halts. It
returns UNKNOWN specifically because bool WillHalt() knows that it can't say that
LoopIfHalt() halts, because this makes it not halt. Therefore you fall through to the
other conditions.
If you walk through the same execution trace with void WillHalt() you get
a completely different result. You get this different result specifically
because void WillHalt() does not feed its result back to its caller, thus
modifying the behavior of its caller. Since the caller is also the program being
analyzed, then different behavior by the caller entails a different result from the
analysis.
Are we talking about the same two functions? Here they are again:
int WillHaltWithReturnValue(string SourceCode, string InputData) {
if (TheProgramWillHalt(SourceCode, InputData))
return TRUE;
else if (TheProgramWillNotHalt(SourceCode, InputData))
return FALSE;
else
return UNKNOWN;
}
void WillHalt(string SourceCode, string InputData)
{
if (TheProgramWillHalt(SourceCode, InputData))
SecureOutput("The Program Will Halt");
else if (TheProgramWillNotHalt(SourceCode, InputData))
SecureOutput("The Program Will Not Halt");
else
SecureOutput("Security Has Been Breached, Take Corrective Action");
}
I am arguing that if both SourceCode parameters are equal to each other and
both InputData parameters are equal to each other, then there is a
one-to-one mapping (in both directions) between TRUE, FALSE, UNKNOWN and
"The Program Will Halt", "The Program Will Not Halt", and "Security Has Been
Breached, Take Corrective Action", respectively. My previous post shows
that if you accept that this is true, then that means that WillHalt() is
using the same exact logic as WillHaltWithReturnValue(), so you must accept
that WillHalt() does not work because WillHaltWithReturnValue() has already
been shown to be wrong. In short, the logic of the functions are unaffected
by the presence of output statements, so, if one's logic is unacceptable,
the other's logic is unacceptable, period.
If you can prove that WillHaltWithReturnValue()'s return codes do not have a
one-to-one mapping (in both directions) to WillHalt()'s output statements,
then please do it. Do not tell me to walk through the execution trace
myself and discover what happens, because I have walked through all of the
possible execution traces and have determined that there is no difference in
the results. Using only the above source, start with a pair of strings as
input parameters, walk through both functions' execution traces using
whatever notation for branches that you wish you use, and prove that there
could be a case where the statement written to the screen does not match the
corresponding return value as I described. If you can do that, then you
have shown that WillHalt() could work where WillHaltWithReturnValue() did
not, and therefore you will have proven that there is a potential solution
to the halting problem. If you cannot do that, then the halting problem
remains as it was before you came up with this "solution."
I'm getting the impression that you don't understand what I'm trying to say,
so the above was an attempt to cut out all of the extraneous talk and focus
on the exact conundrum that must be dealt with. If you refuse to respond
with the example exactly as I requested and instead resort to asserting that
something is different between the two, I will assume that you are trying to
irritate me and I will not respond, except possibly with a short, caustic
(possibly insulting, depending on my mood) message explaining how you did
not satisfy my request. I'm sorry to seem rude, but I have explained
everything in the best way I can, and this discussion is trying my patience.
Looking back, I find it amazing that I have not cursed like a sailor in one
of my posts.
--
David Hilsee
On Thu, 22 Jul 2004 22:40:32 GMT, "Peter Olcott"
<ol****@worldnet.att.net> wrote:
"tom_usenet" <to********@hotmail.com> wrote in message news:j8********************************@4ax.com... On Thu, 22 Jul 2004 00:35:24 GMT, "Peter Olcott"
<ol****@worldnet.att.net> wrote:
>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.
*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.
You can do this, and my original unmodified halt analyzer can determine
that this function would halt, even though it could not make this determination
itself. My uncorrupted halt analyzer still works for all inputs.
This is infuriating, so this will be my last post on this subject.
a) You haven't proved that your "halt analyzer" works for all inputs,
only that the contradiction for the bool returning one doesn't apply.
b) The bool returning WillHalt function *cannot exist* - it is a
logical contradiction. So how can your function determine that it
would halt?
Go and read up on logic and the concept of proof, and stop being such
a fool.
Tom
Peter Olcott wrote: If you are not able to do this, you haven't solved the halting problem.
Solutions that only apply to some special case are Not Interesting.
If you want to be completely precise, then I have not actually
solved the Halting Problem, yet have proven that the original
proof that a solution is impossible, is incorrect.
You did this by modifying the original proof. Your intention
is clear: You modified the original proof in such a way that
the whole idea of the proof is no longer possible. So what you
showed is: With a modification, the proof is no longer applyable.
Not really an interesting result.
--
Karl Heinz Buchegger kb******@gascad.at
tom_usenet wrote:
On Thu, 22 Jul 2004 23:08:34 -0400, "David Hilsee"
<da*************@yahoo.com> wrote:
I suggest you stop here; Olcott is a classic usenet crackpot who
doesn't understand logic.
I remember of another 'proof' from him. The proof went along:
Execute the algorithm in question and wait. If the algorithm terminates
in x seconds then it obviously halted. If not, the algorithm will never
halt.
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote: 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.
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?
The function that does not return a value does correctly determine
halting for all inputs, including the function that does return this
value.
Then so will the one generated by modifying your algorithm, replacing
all occurrences of 'write the result to console' or whatever with
'return the result', and changing nothing else.
Even if the result is built up and written to the console little by
little, all occurrences of 'write to console' can be replaced by 'write
to a file', and then the final action of WillHalt can be to read the
file back in and return its contents. Or you can bypass the file, and
use an in-memory buffer.
<snip> 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
A single valid counter-example is all that is required. I provided
that.
<snip>
What are you referring to as "a single valid counter-example"? A single
algorithm that can be proven to halt or not halt given arbitrary input?
That isn't what the halting problem means.
Or a single version of WillHalt that will not work with the original
proof? A necessary prerequisite for the theorem to be false is that
your version of WillHalt genuinely cannot be changed into one that is
compatible with the proof. And obviously your example doesn't satisfy
this requirement.
The logic of the proof is still there, it just has one more link in its
chain.
WillHalt can be constructed
=> WillHalt that returns its result can be constructed
=> The LoopIfHalts function can be constructed based on the
result-returning WillHalt
=> The LoopIfHaltsOnItself function can be constructed
=> LoopIfHaltsOnItself can be applied to itself
=> Contradiction.
Here, I'll go down in history for having just extended the standard
proof to deal with your idea.
Stewart.
--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
tom_usenet wrote:
This is infuriating, so this will be my last post on this subject.
You don't remember the fun and games last time Olcott was here? His
"faster" string implementation? You're just wasting your time...
Jacques.
"tom_usenet" <to********@hotmail.com> wrote in message
news:60********************************@4ax.com... On Thu, 22 Jul 2004 23:08:34 -0400, "David Hilsee"
<da*************@yahoo.com> wrote:
I suggest you stop here; Olcott is a classic usenet crackpot who
doesn't understand logic. See:
http://www.google.co.uk/groups?safe=...Peter%20Olcott
Tom
I remember the FastString class. In my mind, I didn't classify him as a
crackpot when I read his posts about FastString. I just thought that he
enjoyed showing that he could write a class that, for most test cases, is
more efficient than certain std::string implementations.
Thanks for cutting in. This cycle might not end if I don't stop, breathe
deeply, and just walk away from the argument.
--
David Hilsee
Stewart Gordon wrote: The function that does not return a value does correctly determine
halting for all inputs, including the function that does return this
value.
Then so will the one generated by modifying your algorithm, replacing
all occurrences of 'write the result to console' or whatever with
'return the result', and changing nothing else.
Even if the result is built up and written to the console little by
little, all occurrences of 'write to console' can be replaced by 'write
to a file', and then the final action of WillHalt can be to read the
file back in and return its contents. Or you can bypass the file, and
use an in-memory buffer.
Peter does not understand that algorithms produce a result. In which form
this result is presented is completely unimportant and such not part of
the algorithm. And having an algorithm which produces absolutely no result
(or does not present its result) is of no particular use. However there
will always be ways to feed the result back to the program. Hint to Peter:
even if you eliminate all ways that your program can directly get at the
result, there are ways to do it. Eg. By calling you version of the WillHalt()
function and then asking the user what the WillHalt() function output was.
Peter reminds me of the Crab in Hofstadter's "Goedel, Escher, Bach" trying
to defend the idea of a record player that can reproduce any and all sounds.
--
Karl Heinz Buchegger kb******@gascad.at
On Fri, 23 Jul 2004 07:10:18 -0400, "David Hilsee"
<da*************@yahoo.com> wrote: "tom_usenet" <to********@hotmail.com> wrote in message
news:60********************************@4ax.com.. . On Thu, 22 Jul 2004 23:08:34 -0400, "David Hilsee"
<da*************@yahoo.com> wrote:
I suggest you stop here; Olcott is a classic usenet crackpot who
doesn't understand logic. See:
http://www.google.co.uk/groups?safe=...Peter%20Olcott
Tom
I remember the FastString class. In my mind, I didn't classify him as a
crackpot when I read his posts about FastString. I just thought that he
enjoyed showing that he could write a class that, for most test cases, is
more efficient than certain std::string implementations.
Yes, I was one of the unfortunate perpetrators of the thread. I no
longer remember the details of his flawed logic, but I distinctly
remember that his argumentative style was highly dishonest and
illogical. His FastString contained several bugs which helped it
outperform std::string. e.g. s += s[0]; didn't always work, and it
wasn't exception safe. But it was of course much slower in some
circumstances, and he never gave a real world example to demonstrate
it's superiority outside benchmarks. OTOH, the thread was useful in
highlighting the performance problems of std::string, which tries to
be a jack of all trades and is therefore a master of none.
Thanks for cutting in. This cycle might not end if I don't stop, breathe
deeply, and just walk away from the argument.
I could see this one turning into a big thread, and it's not worth
wasting your time trying to persuade a crackpot that they are one. He
clearly doesn't understand the concept of formal proofs. He'd get
"null points" if he submitted his "proofs" to a
teacher/academic/mathematician/etc.
Tom
On Fri, 23 Jul 2004 21:56:57 +1200, Jacques Labuschagne
<ja*****@clawshrimp.com> wrote: tom_usenet wrote:
This is infuriating, so this will be my last post on this subject.
You don't remember the fun and games last time Olcott was here? His
"faster" string implementation? You're just wasting your time...
Yes, I remember quite clearly, although he did at least have 1 or 2
valid points in that thread, rather than the 0 success rate in this
one. It's worth posting a few times just so that the uninitiated
reading the thread have no doubt about who is correct and who very
definitely isn't. I've bowed out too now though (and I posted
something similar to your post yesterday in the another thread
strand!).
Tom
> a) You haven't proved that your "halt analyzer" works for all inputs, only that the contradiction for the bool returning one doesn't apply.
b) The bool returning WillHalt function *cannot exist* - it is a
logical contradiction. So how can your function determine that it
would halt?
If you bothered to read what I said instead of just making assumptions,
then you would already have this answer.
Go and read up on logic and the concept of proof, and stop being such
a fool.
Tom
> Peter does not understand that algorithms produce a result. In which form this result is presented is completely unimportant and such not part of
the algorithm.
Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.
And having an algorithm which produces absolutely no result
(or does not present its result) is of no particular use. However there
You didn't bother to read what I said all the way through either did you?
If you would have read what I said ALL THE WAY THROUGH, you
would see that your last statemnt is false.
will always be ways to feed the result back to the program. Hint to Peter:
even if you eliminate all ways that your program can directly get at the
result, there are ways to do it. Eg. By calling you version of the WillHalt()
function and then asking the user what the WillHalt() function output was.
This will not work in this case. That would be answers to frequent objections
02.
Peter reminds me of the Crab in Hofstadter's "Goedel, Escher, Bach" trying
to defend the idea of a record player that can reproduce any and all sounds.
--
Karl Heinz Buchegger
kb******@gascad.at
"David Hilsee" <da*************@yahoo.com> wrote in message news:Vo********************@comcast.com... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:F9********************@bgtnsc05-news.ops.worldnet.att.net... You cannot argue that the result is different. While it is true that the code is different and the characters written to the screen are different, the ANSWER (AKA conclusion) is the same for every input. That is, for every input that WillHalt() displays "The Program Will Halt",
WillHaltWithReturnValue() will return TRUE, and for every input that
WillHalt() displays "The Program Will Not Halt", WillHaltWithReturnValue() will return FALSE,
No that is simply not the case.
http://home.att.net/~olcott/halting/example.html
If you walk through an execution trace of the above int
WillHalt(LoopIfHalts, LoopIfHalts) the result is that WillHalt() returns UNKNOWN, thus LoopIfHalt() halts. It
returns UNKNOWN specifically because bool WillHalt() knows that it can't say that
LoopIfHalt() halts, because this makes it not halt. Therefore you fall through to the
other conditions.
If you walk through the same execution trace with void WillHalt() you get
a completely different result. You get this different result specifically
because void WillHalt() does not feed its result back to its caller, thus
modifying the behavior of its caller. Since the caller is also the program being
analyzed, then different behavior by the caller entails a different result from the
analysis.
Are we talking about the same two functions? Here they are again:
int WillHaltWithReturnValue(string SourceCode, string InputData) {
if (TheProgramWillHalt(SourceCode, InputData))
return TRUE;
else if (TheProgramWillNotHalt(SourceCode, InputData))
return FALSE;
else
return UNKNOWN;
}
void WillHalt(string SourceCode, string InputData)
{
if (TheProgramWillHalt(SourceCode, InputData))
SecureOutput("The Program Will Halt");
else if (TheProgramWillNotHalt(SourceCode, InputData))
SecureOutput("The Program Will Not Halt");
else
SecureOutput("Security Has Been Breached, Take Corrective Action");
}
I am arguing that if both SourceCode parameters are equal to each other and
both InputData parameters are equal to each other, then there is a
one-to-one mapping (in both directions) between TRUE, FALSE, UNKNOWN and
"The Program Will Halt", "The Program Will Not Halt", and "Security Has Been
Breached, Take Corrective Action", respectively. My previous post shows
that if you accept that this is true, then that means that WillHalt() is
using the same exact logic as WillHaltWithReturnValue(), so you must accept
that WillHalt() does not work because WillHaltWithReturnValue() has already
been shown to be wrong. In short, the logic of the functions are unaffected
Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.
by the presence of output statements, so, if one's logic is unacceptable,
the other's logic is unacceptable, period.
If you can prove that WillHaltWithReturnValue()'s return codes do not have a
one-to-one mapping (in both directions) to WillHalt()'s output statements,
then please do it. Do not tell me to walk through the execution trace
myself and discover what happens, because I have walked through all of the
possible execution traces and have determined that there is no difference in
the results. Using only the above source, start with a pair of strings as
input parameters, walk through both functions' execution traces using
whatever notation for branches that you wish you use, and prove that there
could be a case where the statement written to the screen does not match the
corresponding return value as I described. If you can do that, then you
have shown that WillHalt() could work where WillHaltWithReturnValue() did
not, and therefore you will have proven that there is a potential solution
to the halting problem. If you cannot do that, then the halting problem
remains as it was before you came up with this "solution."
I'm getting the impression that you don't understand what I'm trying to say,
so the above was an attempt to cut out all of the extraneous talk and focus
on the exact conundrum that must be dealt with. If you refuse to respond
with the example exactly as I requested and instead resort to asserting that
something is different between the two, I will assume that you are trying to
irritate me and I will not respond, except possibly with a short, caustic
(possibly insulting, depending on my mood) message explaining how you did
not satisfy my request. I'm sorry to seem rude, but I have explained
everything in the best way I can, and this discussion is trying my patience.
Looking back, I find it amazing that I have not cursed like a sailor in one
of my posts.
--
David Hilsee
Peter Olcott wrote: Peter does not understand that algorithms produce a result. In which form
this result is presented is completely unimportant and such not part of
the algorithm.
Since the result is returned to the program being analyzed, and the result
changes the behavior of the program being analyzed, therefore the result
of the analysis is different. If the result is NOT returned to the program
being analyzed, then the behavior of the program is NOT changed, and
the result of the analysis is conclusive. It really very simple.
Here is you logical flaw.
As long as you somehow present the result (and you have to do that, otherwise
the whole thing is useless) there are *always* ways to 'return' the result
to the program. Even if that means that the program asks the user: 'What
was the result?' and the user has to enter what WillHalt() printed on the
screen. So even if you try to eliminate all ways to return that information
to the program (as you do by dropping the return value, not allowing the
program to get at that information from the screen buffer memory and whatever
you thouhgt up on your web site) there is only one way to completely close
the information-return-path: not outputting that information at all. But then
your WillHalt() tester is useless.
So there are 2 choices:
1) either WillHalt() outputs some information
2) or it does not. In this case it is useless because it is the nature of
a tester to come up with some result. No result -> no tester
From this it follows that we have to accept 1)
Now if we are with choice 1) then it doesn't matter what you do, the calling
function can get at that information which makes your method just a complicated
case of the original proof. And the conclusion from the original method was:
WillHalt() cannot exist.
qed
And having an algorithm which produces absolutely no result
(or does not present its result) is of no particular use. However there
You didn't bother to read what I said all the way through either did you?
If you would have read what I said ALL THE WAY THROUGH, you
would see that your last statemnt is false.
Well.
If I am presented with a proof that something cannot exist and minds
brigther then you or I or the complete intelligence of that group confirmed
that proof to be correct, I don't question it.
--
Karl Heinz Buchegger kb******@gascad.at This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Peter Olcott |
last post by:
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...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |
