117  7078 
Peter Olcott wrote:
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.
An important part of that proof is *that* the information is returned.
You cannot eliminate that without destroying the proof.
You act like somebody saying:
Hay, in Euclids proof for an infinite amount of prime numbers there
is an addition. I don't like that addition thus I replace it with a
multiplcation. Then the proof no longer works and hence there is
an upper bound for the number of prime numbers.
That's simply absurd.
--
Karl Heinz Buchegger kb******@gascad.at
On Fri, 23 Jul 2004 15:03:08 +0200, Karl Heinz Buchegger
<kb******@gascad.at> wrote: Peter Olcott wrote:
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.
An important part of that proof is *that* the information is returned.
You cannot eliminate that without destroying the proof.
You act like somebody saying:
Hay, in Euclids proof for an infinite amount of prime numbers there
is an addition. I don't like that addition thus I replace it with a
multiplcation. Then the proof no longer works and hence there is
an upper bound for the number of prime numbers.
That's simply absurd.
I wouldn't bother arguing with him if I were you; it's a waste of
time.
Tom
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,
You mean you've found a way to forcibly give a return statement the side
effect of modifying the algorithm it's just finished testing? I'd like
to see it.
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,
<snip>
Who said anything about a program X calling WillHalt(X)?
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... 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,
You mean you've found a way to forcibly give a return statement the side
effect of modifying the algorithm it's just finished testing? I'd like
to see it.
http://www.netaxs.com/people/nerp/au.../halting2.html
This is how the Halting Problem is defined. The only reason
that the Halting Problem is a problem is that your are required
to analyze the same program that is calling your program.
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,
<snip>
Who said anything about a program X calling WillHalt(X)?
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. 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.
An important part of that proof is *that* the information is returned.
You cannot eliminate that without destroying the proof.
It is my goal to destroy this proof. As long as I can refute this statement:
No program can ever be written to determine whether any arbitrary
program will halt
I have correctly refuted the original Halting Problem proof. The mistake all
along is that returning the result to the caller was NEVER REQUIRED.
You act like somebody saying:
Hay, in Euclids proof for an infinite amount of prime numbers there
is an addition. I don't like that addition thus I replace it with a
multiplcation. Then the proof no longer works and hence there is
an upper bound for the number of prime numbers.
That's simply absurd.
--
Karl Heinz Buchegger
kb******@gascad.at
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:eP*********************@bgtnsc04-news.ops.worldnet.att.net...
<snip> 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.
The above paragraph doesn't make sense to me. Do you think that I'm trying
to modify your analysis program? I'm not. I'm producing source code (just
text, not an executable) for you to pass as input to your program. The
input source code resembles the source for your program because it uses the
same logic that your analysis program uses. That's the case when the
program fails: when the input uses a specially-crafted version of the very
program that is performing the analysis. It fails because
WillHaltWithReturnValue() fails, plain and simple.
This will hopefully be my last post in this thread, because tom_usenet has
talked some sense in to me. I'm not going to argue with you any more. I
just wanted to leave a final message with instructions on how you may come
to realize that your function, WillHalt(), is incorrect for the same input
that the other function, WillHaltWithReturnValue() is incorrect. To be
honest, I'm feeling sorry for you because everyone else seems to "get it"
and you don't. If these instructions help you to see the truth, then please
post a response saying so, because it will at least make me feel as though
my time has not been wasted.
Clear your mind of compilers, interpreters, executeable files, memory,
binary, and other things that we use to translate an abstract flow into a an
implementation of that flow, because they are irrelevant. If you ever get
an idea to you could use any of them to differentiate between the two
functions, ignore it. The halting problem works on an abstract machine, and
because all implementations of the machine are subject to the same rules for
implementing the logical flow, anything proven about this primitive abstract
machine applies to any implementation. Consider a fictional machine that
may not be anything like what you are using today. Focus on the Turing
machine.
Avoid using the word "result" to mean something that is a property of the
implementation. For example, do not say that the result is a bit pattern,
or the result is some file, or the result is in the stack. If you do that,
then you are not thinking about the abstract machine. You may accidentally
think that two results are not the same because they do not have the same
representation in the implementation. The representation of a result in the
implementation is irrelevant when considering its correctness. A integer
result of zero that indicates false, a file containing the string "false",
and someone's whispering of "false" in your ear are all equivalent results
because they indicate the same thing. That is, they are the same answer
with a different, irrelevant, representation. As an analogy, if I ask you
to give me the names of all 50 states, and you give me a piece of paper with
them written down, you are just as correct when you say them aloud.
Keep in mind that the UNKNOWN should never be reached for valid input. In
that case, the result must be TRUE or FALSE. If the input is valid and the
program returns UNKNOWN, then it has failed the test. If UNKNOWN were to be
an acceptable answer for valid input, then a program that only consisted of
"return UNKNOWN;" would be a solution. I kept the UNKNOWN value in the
source because I thought it might be used for invalid input and I wanted it
to be as close to the original function as possible. I probably should have
removed it to avoid confusion.
Lastly, avoid focusing on one particular sentence in my posts. I usually
break my posts up into paragraphs for a good reason, so try to understand
the entire paragraph when you apply my posts to your halting problem
"solution."
Now, if you look at the two functions provided and still argue that the
result when display on the screen can be different than the result provided
in the return value, then you must be appealing to an irrelevant
implementation detail that does not affect the result. Once you understand
why both functions, given any input, always produce the same result, you
will understand that they are both wrong when passed the "difficult input"
that looks something like the code I gave you. Remember: a program that,
for every input, always produces the same result as a program that is
incorrect on a particular input will also be incorrect on the same input,
even if the executing code is different. If you're still having problems,
see the post where I provided source code, go to the link I provided, and
make sure you fully understand it. Now consider the case when my source is
passed to your function.
If you think the above points are debateable and wish to respond to them, I
will read your response and consider your counterpoints, but I will probably
not respond back.
--
David Hilsee
> 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.
Ah so the user is a slave to the program? I don't buy it.
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.
I know that this seems like a valid refutation. I also know that it is
not a valid refutation. If this was a valid refutation then it could be
claimed that no program has ever worked, because someone could
always come along and destroy the computer, thus making it not
work. All the I am required to do to refute the original proof is to
derive one single way that the following statement can be refuted:
No program can ever be written to determine whether any
arbitrary program will halt
This way is not required to work under all conditions such as:
(1) Destroying the computer that is running the program.
(2) Erasing the program from the computer.
(3) Inserting bugs into the executable program, thus corrupting it.
It only needs to work correctly for all inputs. My idea would
work correctly for all inputs.
Karl Heinz Buchegger
kb******@gascad.at
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... 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
Except that the statement below has now been refuted:
No program can ever be written to determine whether
any arbitrary program will halt
Since this is the definition of the Halting Problem, the
halting Problem itself has now been refuted.
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@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
I never said anything like that. You must be confusing
me with someone else.
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:jH*********************@bgtnsc05-news.ops.worldnet.att.net... http://www.netaxs.com/people/nerp/au.../halting2.html
This is how the Halting Problem is defined. The only reason
that the Halting Problem is a problem is that your are required
to analyze the same program that is calling your program.
Ugh, I just posted a long message in another thread, claimed it was going to
be my last, and here I am typing another. I just couldn't let this slide.
That is not the reason that the Halting Problem is a problem. It is a
problem because the analyzing program cannot process specific,
specially-designed input sources that contain logic taken from its own
source because, for those sources, the analyzer cannot produce a result that
avoids a contradiction of the result that would be produced by the stolen,
embedded logic if it were executed. That stolen logic may be modified
slightly to produce return values, but as long as the logic produces the
same result, the problem remains.
At least I kept it short and sweet this time.
--
David Hilsee
> 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.
Any method to refute the following definition of the Halting Problem:
No program can ever be written to determine whether any
arbitrary program will halt
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.
bool WillHalt() and LoopIfHalts() only prove that solving the Halting Problem
with bool WillHalt() is impossible. This has been taken to mean that solving the
Halting Problem is impossible. Since void WillHalt() does not get caught in the
double-bind of bool WillHalt(), void WillHalt() solves the Halting Problem.
"David Hilsee" <da*************@yahoo.com> wrote in message news:R8********************@comcast.com... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:jH*********************@bgtnsc05-news.ops.worldnet.att.net... http://www.netaxs.com/people/nerp/au.../halting2.html
This is how the Halting Problem is defined. The only reason
that the Halting Problem is a problem is that your are required
to analyze the same program that is calling your program.
Ugh, I just posted a long message in another thread, claimed it was going to
be my last, and here I am typing another. I just couldn't let this slide.
That is not the reason that the Halting Problem is a problem. It is a
problem because the analyzing program cannot process specific,
specially-designed input sources that contain logic taken from its own
source because, for those sources, the analyzer cannot produce a result that
avoids a contradiction of the result that would be produced by the stolen,
embedded logic if it were executed. That stolen logic may be modified
slightly to produce return values, but as long as the logic produces the
same result, the problem remains.
The logic does not produce the same result. I cut this from my updated website.
(3) The version of the halt analyzer that returns the result back to its caller and the version of the halt analyzer that does not
return its result back to its caller must determine the same result. They must determine the same result because they both use the
same method, and they both operate on the same data. Since we already know that the first one must fail, therefore the second one
must also fail.
The thing to remember here is that the calling program and the program being analyzed are the same program. If returning a value to
the calling program changes its behavior, then it also changes the behavior of the program being analyzed, because they are the same
program.
If the result is returned to the program being analyzed, and this result changes the behavior of the program being analyzed,
therefore that result of the analysis must also change. If the result is NOT returned to the program being analyzed, then the
behavior of this program is NOT changed, and the result of the analysis is conclusive.
At least I kept it short and sweet this time.
--
David Hilsee
On Thu, 22 Jul 2004 12:02:43 +0000, Peter Olcott[2] wrote: 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.
Ah, but all halt analyzers are equivalent[1]. If you can algorithmically
determine that an algorithm will halt, you _can always_ pass that
information on to another algorithm. The fact that you can choose not to
doesn't impact the fact that you also can. Once it's *possible* to relay
that information to another algorithm, even if you choose not to, the
original proof holds.
Recall that all computers[0] can simulate all other computers, as well.
So, while your algorithm may be writing to 'the screen' using 'protected
memory', it may be operating in a simulated environment where those two
operations are implemented by simply storing the displayed information for
later retrieval. This does not change your algoritm one iota: a
simulation has *at least* the same characteristics and capabilities of the
original. This simulation could be on any equally-powerful computer.
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.
Solving the halting problem by extending the machine past
Turing-equivalent capabilities is uninteresting, as being able to solve
the halting problem for Turing machines is a normal feature of a
more-powerful computing paradigm, for reasons that have been covered
elsewhere. Truly "protected" memory, where it is an error (actually a
final state) to read from, is not a feature of Turing-equivalent machines.
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).
(Below I refer to the compound noun 'subjects'; I mean the subject
algorithm M combined with the subject input x.)
Any algorithm that can tell a hypothetical user/observer if the subject
algorithm with the subject input will halt must, by definition, at some
point during its execution contain information about whether the
subjects halt or not. Agreed?
If it contains that information, it *is* *always* possible to write the
exact same algorithm to the point where that information is present, and
then deviate. Up until the point where they deviate, they are the same
algorithm. At the point of deviation, both contain absolute information
about whether subjects halt. Agreed? 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.
No, it's not "the halting problem," it's just an algorithm expressed in C.
But if you've solved the halting problem, you should be able to tell me if
that algorithm will halt.
[0] This is a grotesque generalization and should really read 'all
Turing-complete machines can simulate all other Turing-complete machines'.
However, in the real world there are lots of examples of computers
simulating other computers -- I'm doing some experiments using Bochs, for
instance, which simulates an Intel computer.
[1] If two algorithms produce the same outputs for all inputs, then the
two algorithms are equivalent. They could well be completely different,
internally, but they do the same thing.
[2] I know he's never going to back down on this. This is for fun, not to
try to convince anyone of anything.
--
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.
On Fri, 23 Jul 2004 09:47:06 +0100, 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. See:
http://www.google.co.uk/groups?safe=...Peter%20Olcott
Wonder what'd happen if we locked him and Scott Nudds in a room together...
--
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.
On Fri, 23 Jul 2004 21:46:55 +0000, Peter Olcott wrote: "Stewart Gordon" <sm*******@yahoo.com> wrote in message
news:cd**********@sun-cc204.lut.ac.uk...
You mean you've found a way to forcibly give a return statement the
side effect of modifying the algorithm it's just finished testing? I'd
like to see it.
http://www.netaxs.com/people/nerp/au.../halting2.html This is how the
Halting Problem is defined. The only reason that the Halting Problem is
a problem is that your are required to analyze the same program that is
calling your program.
Wait a moment there, old son. You've said something inconsistent.
Quote (Olcott):
"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."
Message <D1*******************@bgtnsc05-news.ops.worldnet.att.net>
Quote ( http://www.netaxs.com/people/nerp/au...alting2.html):
"Theorem. Turing machine WillHalt(M,w) does not exist."
^^^^^^^^^^^^^^
There's a commonly-accepted definition of the halting problem, used in
computer science. Your own link touches on it: there is no Turing machine
or Turing-equivalent machine that can determine if arbitrary programs (and
inputs) for that machine will halt. Proving that a machine more capable
than a Turing machine (which might hypothetically exist; we'll call it an
Oracle machine because it can compute things that a Turing machine can't)
can solve the halting problem is uninteresting with regards to the halting
problem as originally defined.
--
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.
> Ah, but all halt analyzers are equivalent[1]. If you can algorithmically determine that an algorithm will halt, you _can always_ pass that
information on to another algorithm. The fact that you can choose not to
doesn't impact the fact that you also can. Once it's *possible* to relay
that information to another algorithm, even if you choose not to, the
original proof holds.
Yet only holds for the corrupted version, it does not hold for the uncorrupted
version. The uncorrupted version can even correctly determine that the corrupted
version will definitely halt. This would ONLY form a valid refutation if the
last statement was not true. Since the last statement is true, this attempt at refutation
is analogous to saying I can prove that your program never worked by merely
smashing the computer that it is running on.
Recall that all computers[0] can simulate all other computers, as well.
So, while your algorithm may be writing to 'the screen' using 'protected
memory', it may be operating in a simulated environment where those two
operations are implemented by simply storing the displayed information for
later retrieval. This does not change your algoritm one iota: a
simulation has *at least* the same characteristics and capabilities of the
original. This simulation could be on any equally-powerful computer.
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.
Solving the halting problem by extending the machine past
Turing-equivalent capabilities is uninteresting, as being able to solve
I am not solving the Halting Problem with an imaginary magic machine.
The only capabilities that I am adding are already available in current
hardware. If this solves the Halting Problem, and the original definition
dos not, then I have refuted both the Halting Problem, and the Church-Turing
thesis. Some people have claimed that these additional capabilities are
merely alternate forms of a valid Turing Machine. All they really amount to
are special forms of memory.
the halting problem for Turing machines is a normal feature of a
more-powerful computing paradigm, for reasons that have been covered
elsewhere. Truly "protected" memory, where it is an error (actually a
final state) to read from, is not a feature of Turing-equivalent machines.
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).
(Below I refer to the compound noun 'subjects'; I mean the subject
algorithm M combined with the subject input x.)
Any algorithm that can tell a hypothetical user/observer if the subject
algorithm with the subject input will halt must, by definition, at some
point during its execution contain information about whether the
subjects halt or not. Agreed?
YES.
If it contains that information, it *is* *always* possible to write the
exact same algorithm to the point where that information is present, and
then deviate. Up until the point where they deviate, they are the same
algorithm. At the point of deviation, both contain absolute information
about whether subjects halt. Agreed?
NO.
http://home.att.net/~olcott/halting/...ml#objection03
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.
No, it's not "the halting problem," it's just an algorithm expressed in C.
But if you've solved the halting problem, you should be able to tell me if
that algorithm will halt.
I have not solved every definition of the Halting Problem.
I have only solved the original definition of the Halting Problem.
[0] This is a grotesque generalization and should really read 'all
Turing-complete machines can simulate all other Turing-complete machines'.
However, in the real world there are lots of examples of computers
simulating other computers -- I'm doing some experiments using Bochs, for
instance, which simulates an Intel computer.
[1] If two algorithms produce the same outputs for all inputs, then the
two algorithms are equivalent. They could well be completely different,
internally, but they do the same thing.
[2] I know he's never going to back down on this. This is for fun, not to
try to convince anyone of anything.
--
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.
> Quote ( http://www.netaxs.com/people/nerp/au...alting2.html): "Theorem. Turing machine WillHalt(M,w) does not exist."
^^^^^^^^^^^^^^
There's a commonly-accepted definition of the halting problem, used in
computer science. Your own link touches on it: there is no Turing machine
or Turing-equivalent machine that can determine if arbitrary programs (and
inputs) for that machine will halt. Proving that a machine more capable
than a Turing machine (which might hypothetically exist; we'll call it an
Oracle machine because it can compute things that a Turing machine can't)
can solve the halting problem is uninteresting with regards to the halting
problem as originally defined.
The NIST standard definition of the Halting Problem does not mention TM's
No program can ever be written to determine whether any arbitrary program will halt
http://www.nist.gov/dads/HTML/haltingProblem.html
It is clear that I am not talking about an imaginary magical oracle machine.
Protected memory, ROM memory, and write only memory already exist
in the real world.
--
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.
"David Hilsee" <da*************@yahoo.com> wrote in message news:e7********************@comcast.com... 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.
The above paragraph doesn't make sense to me.
The Halting Problem is defined such that the halt analyzer returns
its result back to the program being analyzed, and this program
being analyzed changes its behavior based on this returned result,
which in turn changes the result of the analysis, which changes the
behavior ad infinitum... Merely refraining from returning the result
breaks this otherwise endless chain.
-- David Hilsee
On Sat, 24 Jul 2004 13:10:48 +0000, Peter Olcott wrote: Recall that all computers[0] can simulate all other computers, as well.
So, while your algorithm may be writing to 'the screen' using 'protected
memory', it may be operating in a simulated environment where those two
operations are implemented by simply storing the displayed information for
later retrieval. This does not change your algoritm one iota: a
simulation has *at least* the same characteristics and capabilities of the
original. This simulation could be on any equally-powerful computer.
This is still an important point. No algorithm can determine whether it's
running on a computing machine or a simulation of a computing machine, and
a simulated computing machine can perform extra operations based on the
simulated algorithm without disturbing its operation.
(Below I refer to the compound noun 'subjects'; I mean the subject
algorithm M combined with the subject input x.)
Any algorithm that can tell a hypothetical user/observer if the subject
algorithm with the subject input will halt must, by definition, at some
point during its execution contain information about whether the
subjects halt or not. Agreed?
YES.
If it contains that information, it *is* *always* possible to write the
exact same algorithm to the point where that information is present, and
then deviate. Up until the point where they deviate, they are the same
algorithm. At the point of deviation, both contain absolute information
about whether subjects halt. Agreed?
NO.
http://home.att.net/~olcott/halting/...ml#objection03
Non-sequitor. You've answered "Do you agree that it must be possible to
return that information to another algorithm?" I'm asking "Do you agree
that it's possible to write other algorithms that, up to the point where
the information about whether the subjects halt exists, are identical?"
Identical means performing the exact same series of operations on the
inputs, starting from the same state. If you examined what the machine
had already done, and what state it was in *at the point where this
information becomes available*, you would not be able to tell which of
yours or some other algorithm you were examining. Agreed?
I have not solved every definition of the Halting Problem.
I have only solved the original definition of the Halting Problem.
This is a mathematical question, where these differences in wording have
specific meanings. Be very careful, and *always* choose the right words.
What you actually have is "an attempted refutation of Turing's proof that
no algorithm can determine whether any arbitrary algorithm and its input
will halt." Verbose, but much more accurate.
--
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.
"Owen Jacobson" <an******@lionsanctuary.net> wrote in message news:pa***************************@lionsanctuary.n et... If it contains that information, it *is* *always* possible to write the
exact same algorithm to the point where that information is present, and
then deviate. Up until the point where they deviate, they are the same
algorithm. At the point of deviation, both contain absolute information
about whether subjects halt. Agreed?
NO.
http://home.att.net/~olcott/halting/...ml#objection03
Non-sequitor. You've answered "Do you agree that it must be possible to
return that information to another algorithm?" I'm asking "Do you agree
that it's possible to write other algorithms that, up to the point where
the information about whether the subjects halt exists, are identical?"
This answer might not directly apply to your example but since it has
been correct in the previous fifty or more similar cases I will provide it
anyway.
In the specific case of the Halting Problem if the only thing that is changed
is the way that the result is output (returned to the caller, or output to the
screen) just this single difference can change the value of the output itself.
Line 01) void LoopIfHalts(string SourceCode, string InputData)
Line 02) {
Line 03) if (WillHalt(SourceCode, InputData) == TRUE)
Line 04) while (TRUE) // loop forever
Line 05) ;
Line 06) else
Line 07) return; // FALSE or UNKNOWN
Line 08) }
Even though the only thing that is changed is the method of output,
the two function invocations have different return values.
(1) bool WillHalt(LoopIfHalts, LoopIfHalts)
(2) void WillHalt(LoopIfHalts, LoopIfHalts)
If the value is returned from the WillHalt() function to the LoopIfHalts() function
(which is also the program being analyzed), then LoopIfHalts() changes its behavior,
(see line 03) thus changing the result of the analysis. If the value is NOT returned
to the LoopIfHalts() function (which is also the program being analyzed), then
LoopIfHalts() can NOT change its behavior, and the result of the analysis is conclusive
rather than undecidable.
This is a mathematical question, where these differences in wording have
specific meanings. Be very careful, and *always* choose the right words.
What you actually have is "an attempted refutation of Turing's proof that
no algorithm can determine whether any arbitrary algorithm and its input
will halt." Verbose, but much more accurate.
I like this better: I have proven that:
No program can ever be written to determine whether any arbitrary
program will halt
Is not proven.
--
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 wrote: 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.
Ah so the user is a slave to the program? I don't buy it.
It doesn't matter what you buy or what you don't buy.
After all the proof doesn't even need to run on a computer.
Forget the physical implementation on a computer, it is not
important in algorithm theory (and BTW cannot be done). The proof
works in a thinking model without the need for actual hardware
like video screens or memory.
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.
I know that this seems like a valid refutation. I also know that it is
not a valid refutation. If this was a valid refutation then it could be
claimed that no program has ever worked, because someone could
always come along and destroy the computer, thus making it not
work.
We are not talking about programs, we are talking about algorithms!
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... 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
Except that the statement below has now been refuted:
No program can ever be written to determine whether
any arbitrary program will halt
Not it has not.
The proof worked the following way:
"Under the assumption that such a function can be written
it has been shown that it cannot be written."
If you modify the proof, you end up with:
"Under the assumption that such a function can be written,
it can be written."
Not a very interesting statement.
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@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
I never said anything like that. You must be confusing
me with someone else.
Could be.
In this case I apologize.
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote: This is a mathematical question, where these differences in wording have
specific meanings. Be very careful, and *always* choose the right words.
What you actually have is "an attempted refutation of Turing's proof that
no algorithm can determine whether any arbitrary algorithm and its input
will halt." Verbose, but much more accurate.
I like this better: I have proven that:
No program can ever be written to determine whether any arbitrary
program will halt
Is not proven.
No, you have not.
There exists a proof for the above sentence. You have prooven something
else. Nobody knows what it is exactly that you have prooven, but it
is definitily not what you think it is. The original proof uses
only accepted methods from prooving theory and thus is without
doubt. Just modifying the proof and hence destroying it, doesn't
make it invalid. It would be a different thing if you can show a flaw
in the *unmodified* proof.
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote: 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.
An important part of that proof is *that* the information is returned.
You cannot eliminate that without destroying the proof.
It is my goal to destroy this proof. As long as I can refute this statement:
No program can ever be written to determine whether any arbitrary
program will halt
I have correctly refuted the original Halting Problem proof. The mistake all
along is that returning the result to the caller was NEVER REQUIRED.
Oh so I'm never allowed to actually try and find out if WillHalt()
succeeds or not. Any sort of indication from WillHalt() that it has
succeeded, be it through a return value or printing to a console or
catching fire, is to still return a result. But you say no result is
required, so how will I know there is a result?
Peter Olcott wrote:
<snip> You mean you've found a way to forcibly give a return statement the
side effect of modifying the algorithm it's just finished testing?
I'd like to see it.
http://www.netaxs.com/people/nerp/au.../halting2.html This is how
the Halting Problem is defined. The only reason that the Halting
Problem is a problem is that your are required to analyze the same
program that is calling your program.
The only thing I can find on that page relating to a function calling
WillHalt on itself is that LoopIfHaltsOnItself(LoopIfHaltsOnItself)
calls WillHalt(LoopIfHaltsOnItself, LoopIfHaltsOnItself). But
LoopIfHaltsOnItself itself doesn't depend on itself at all.
Indeed, the standard proof doesn't require that any function be defined
recursively, as
function Program(input):
if (WillHalt(Program, input)) ...
...
Maybe this is needed for the concept of a 'general solution'. But that
page doesn't seem to state in its definitions whether recursive
functions are allowed. But if they are, then the proof is even easier
than the contortions the standard proof goes through. Just look at this:
function Program(input):
if (WillHalt(Program, input))
while true do {}
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.
"Andrew Heath" <fa**@email.com> wrote in message news:41******@news.comindico.com.au... Peter Olcott wrote: I have correctly refuted the original Halting Problem proof. The mistake all
along is that returning the result to the caller was NEVER REQUIRED.
Oh so I'm never allowed to actually try and find out if WillHalt()
succeeds or not. Any sort of indication from WillHalt() that it has
succeeded, be it through a return value or printing to a console or
catching fire, is to still return a result. But you say no result is
required, so how will I know there is a result?
I said returning the result to the caller, which means returning the result
to the calling function.
"Stewart Gordon" <sm*******@yahoo.com> wrote in message news:ce**********@sun-cc204.lut.ac.uk... Peter Olcott wrote:
Maybe this is needed for the concept of a 'general solution'. But that
page doesn't seem to state in its definitions whether recursive
functions are allowed. But if they are, then the proof is even easier
than the contortions the standard proof goes through. Just look at this:
function Program(input):
if (WillHalt(Program, input))
while true do {}
Stewart.
That can't work because WillHalt() does not reurn a value to the calling
function.
--
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:hy********************@bgtnsc04-news.ops.worldnet.att.net... function Program(input):
if (WillHalt(Program, input))
while true do {}
That can't work because WillHalt() does not reurn a value to the calling
function.
If it does not return a value to the calling function, then in what sense
can it be said to be determining whether Program(input) will halt?
Peter Olcott wrote:
<snip> That can't work because WillHalt() does not reurn a value to the calling
function.
I'm still waiting to see your example of a function that can't possibly
be modified to return its result.
Stewart.
--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.
"Andrew Koenig" <ar*@acm.org> wrote in message news:VF********************@bgtnsc05-news.ops.worldnet.att.net... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:hy********************@bgtnsc04-news.ops.worldnet.att.net...
function Program(input):
if (WillHalt(Program, input))
while true do {}
That can't work because WillHalt() does not reurn a value to the calling
function.
If it does not return a value to the calling function, then in what sense
can it be said to be determining whether Program(input) will halt?
There are a multitude of other ways that the function could provide results.
Returning the result to the calling function is not at all the only possible way.
It is the only way that the Halting Problem is created, thus if this one way
is eliminated, then the Halting Problem ceases to be a problem.
"Stewart Gordon" <sm*******@yahoo.com> wrote in message news:ce**********@sun-cc204.lut.ac.uk... Peter Olcott wrote:
<snip> That can't work because WillHalt() does not reurn a value to the calling
function.
I'm still waiting to see your example of a function that can't possibly
be modified to return its result.
Stewart.
--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.
I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs. If you don't see that this is exactly the same reasoning
then please provide the precise point where the analogy fails to
coincide, and why it fails to coincide.
As soon as you begin providing the results to the calling function,
you have added an error to the original program.
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... It doesn't matter what you buy or what you don't buy.
After all the proof doesn't even need to run on a computer.
Forget the physical implementation on a computer, it is not
important in algorithm theory (and BTW cannot be done). The proof
works in a thinking model without the need for actual hardware
like video screens or memory.
These details are crucial, and if abstracted away cease to correspond
to the actual reality of the posed problem. For example: a separate
memory space could be the mechanism by which the results are kept
from the program being analyzed. At the higher level of abstraction
of pure mathematics, things such as separate memory spaces are
considered to be irrelevant. If they change the outcome of the analysis,
then it is an error to consider them irrelevant.
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.
I know that this seems like a valid refutation. I also know that it is
not a valid refutation. If this was a valid refutation then it could be
claimed that no program has ever worked, because someone could
always come along and destroy the computer, thus making it not
work.
We are not talking about programs, we are talking about algorithms!
--
Karl Heinz Buchegger
kb******@gascad.at
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Zb********************@bgtnsc04-news.ops.worldnet.att.net...
"Stewart Gordon" <sm*******@yahoo.com> wrote in message
news:ce**********@sun-cc204.lut.ac.uk... Peter Olcott wrote:
<snip> That can't work because WillHalt() does not reurn a value to the
calling function.
I'm still waiting to see your example of a function that can't possibly
be modified to return its result.
Stewart.
--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.
I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs. If you don't see that this is exactly the same reasoning
then please provide the precise point where the analogy fails to
coincide, and why it fails to coincide.
As soon as you begin providing the results to the calling function,
you have added an error to the original program.
Everyone keeps bring up that point because your last assertion is bollocks.
To produce the contradictory input source, one can take the logic from the
source code of the analyzer and use it to construct input that will cause it
to contradict its own logic. You have supposedly taken the ability to
construct that source away by making trivial modifications to the analyzer
and claiming that removing them causes the contradiction to not hold, as if
it were necessary for the input to contain a verbatim copy of the analyzer's
source code to show the contradiction.
In other words, nobody in their right mind would claim that the transition
from
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 // This code never gets executed if the solution is properly
implemented
SecureOutput("Security Has Been Breached, Take Corrective Action");
}
to
int WillHalt(string SourceCode, string InputData)
{
if (TheProgramWillHalt(SourceCode, InputData)) {
SecureOutput("The Program Will Halt");
return TRUE;
}
else if (TheProgramWillNotHalt(SourceCode, InputData)) {
SecureOutput("The Program Will Not Halt");
return FALSE;
}
else { // This code never gets executed if the solution is properly
implemented
SecureOutput("Security Has Been Breached, Take Corrective Action");
return UNKNOWN;
}
}
somehow adds an error into the analyzer that causes the return values to not
correlate with the output statements from the previous version.
Your sledgehammer analogy is flawed because the modification does not cause
your analyzer to malfunction.
BTW, the answer to (3) on halting-problem.com makes little sense to me.
Perhaps supplying an introduction and using two different names for the
bool-returning and void-returning method would be better.
--
David Hilsee
Peter Olcott wrote:
"Andrew Koenig" <ar*@acm.org> wrote in message news:VF********************@bgtnsc05-news.ops.worldnet.att.net... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:hy********************@bgtnsc04-news.ops.worldnet.att.net...
> function Program(input):
> if (WillHalt(Program, input))
> while true do {}
That can't work because WillHalt() does not reurn a value to the calling
function.
If it does not return a value to the calling function, then in what sense
can it be said to be determining whether Program(input) will halt?
There are a multitude of other ways that the function could provide results.
Returning the result to the calling function is not at all the only possible way.
It is the only way that the Halting Problem is created, thus if this one way
is eliminated, then the Halting Problem ceases to be a problem.
You constantly mix up the Halting Problem theorem with its proof.
The proof is where the loop construction takes place. So even if you
are right, then it would be this specific proof that vanishes into
air. But this does not mean that the theorem itself vanishes.
BTW: You are wrong. At the moment the function produces a result
there are ways to feed those results back to the caller. You can't
close that door unless you output no result at all.
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote:
"Stewart Gordon" <sm*******@yahoo.com> wrote in message news:ce**********@sun-cc204.lut.ac.uk... Peter Olcott wrote:
<snip> That can't work because WillHalt() does not reurn a value to the calling
function.
I'm still waiting to see your example of a function that can't possibly
be modified to return its result.
Stewart.
--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.
I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs.
Not at all.
The exact equivalent is:
Claim: All computers will run all programs
Disproov: It is possible to smash a computer with a hammer, thus
not all computers can run all programs. At least smashed
computers won't do that.
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at...
It doesn't matter what you buy or what you don't buy.
After all the proof doesn't even need to run on a computer.
Forget the physical implementation on a computer, it is not
important in algorithm theory (and BTW cannot be done). The proof
works in a thinking model without the need for actual hardware
like video screens or memory.
These details are crucial,
Only in your dreams.
In which way is Euclid's proof dependent on the type of paper
I write it on?
Same here.
--
Karl Heinz Buchegger kb******@gascad.at
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
"Andrew Koenig" <ar*@acm.org> wrote in message news:VF********************@bgtnsc05-news.ops.worldnet.att.net... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:hy********************@bgtnsc04-news.ops.worldnet.att.net...
> > function Program(input):
> > if (WillHalt(Program, input))
> > while true do {}
> That can't work because WillHalt() does not reurn a value to the calling
> function.
If it does not return a value to the calling function, then in what sense
can it be said to be determining whether Program(input) will halt?
There are a multitude of other ways that the function could provide results.
Returning the result to the calling function is not at all the only possible way.
It is the only way that the Halting Problem is created, thus if this one way
is eliminated, then the Halting Problem ceases to be a problem.
You constantly mix up the Halting Problem theorem with its proof.
The proof is where the loop construction takes place. So even if you
are right, then it would be this specific proof that vanishes into
air. But this does not mean that the theorem itself vanishes.
When the Proof of the Halting Problem fails to prove that the Halting Problem
is a problem, then it ceases to be a problem.
BTW: You are wrong. At the moment the function produces a result
there are ways to feed those results back to the caller. You can't
close that door unless you output no result at all.
Feeding the results back to the caller does not show that no correct
halt function can possibly be created. It only shows that one of the
ways to attempt to solve the problem does not always work.
Because it is possible to change a program to cause it to cease
to function correctly, in no way shows that the unmodified program
does not work correctly in every case.
--
Karl Heinz Buchegger
kb******@gascad.at
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
"Stewart Gordon" <sm*******@yahoo.com> wrote in message news:ce**********@sun-cc204.lut.ac.uk... Peter Olcott wrote:
<snip>
> That can't work because WillHalt() does not reurn a value to the calling
> function.
I'm still waiting to see your example of a function that can't possibly
be modified to return its result.
Stewart.
--
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.
I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs.
Not at all.
The exact equivalent is:
Claim: All computers will run all programs
Disproov: It is possible to smash a computer with a hammer, thus
not all computers can run all programs. At least smashed
computers won't do that.
But the claim that the Halt function will work under all possible conditions
(including smashing its computer) is not the relevant claim. The relevant
claims is simply will the halt function work for every possible input? If it
fails this claim then the Halting Problem continues to exist. If it passes this
claim, then the Halting Problem ceases to exist. It does pass this claim.
--
Karl Heinz Buchegger
kb******@gascad.at
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at...
It doesn't matter what you buy or what you don't buy.
After all the proof doesn't even need to run on a computer.
Forget the physical implementation on a computer, it is not
important in algorithm theory (and BTW cannot be done). The proof
works in a thinking model without the need for actual hardware
like video screens or memory.
These details are crucial,
Only in your dreams.
In which way is Euclid's proof dependent on the type of paper
I write it on?
Same here.
--
Karl Heinz Buchegger
kb******@gascad.at
Purely mathematical proofs can fail to prove their claims specifically
because these purely mathematical proofs abstract away (remove)
details that change the outcome.
Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
"Andrew Koenig" <ar*@acm.org> wrote in message news:VF********************@bgtnsc05-news.ops.worldnet.att.net...
> "Peter Olcott" <ol****@worldnet.att.net> wrote in message
> news:hy********************@bgtnsc04-news.ops.worldnet.att.net...
>
> > > function Program(input):
> > > if (WillHalt(Program, input))
> > > while true do {}
>
> > That can't work because WillHalt() does not reurn a value to the calling
> > function.
>
> If it does not return a value to the calling function, then in what sense
> can it be said to be determining whether Program(input) will halt?
>
>
There are a multitude of other ways that the function could provide results.
Returning the result to the calling function is not at all the only possible way.
It is the only way that the Halting Problem is created, thus if this one way
is eliminated, then the Halting Problem ceases to be a problem.
You constantly mix up the Halting Problem theorem with its proof.
The proof is where the loop construction takes place. So even if you
are right, then it would be this specific proof that vanishes into
air. But this does not mean that the theorem itself vanishes.
When the Proof of the Halting Problem fails to prove that the Halting Problem
is a problem, then it ceases to be a problem.
You are not an expert in logic, are you?
Read again what you wrote. In the meantime you got so blind that you
don't even see the simplest logic failures in your argumentation.
--
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at...
> It doesn't matter what you buy or what you don't buy.
> After all the proof doesn't even need to run on a computer.
> Forget the physical implementation on a computer, it is not
> important in algorithm theory (and BTW cannot be done). The proof
> works in a thinking model without the need for actual hardware
> like video screens or memory.
These details are crucial,
Only in your dreams.
In which way is Euclid's proof dependent on the type of paper
I write it on?
Same here.
--
Karl Heinz Buchegger
kb******@gascad.at
Purely mathematical proofs can fail to prove their claims specifically
because these purely mathematical proofs abstract away (remove)
details that change the outcome.
Example?
--
Karl Heinz Buchegger kb******@gascad.at
"David Hilsee" <da*************@yahoo.com> wrote in message news:cr********************@comcast.com... "Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:Zb********************@bgtnsc04-news.ops.worldnet.att.net...
I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs. If you don't see that this is exactly the same reasoning
then please provide the precise point where the analogy fails to
coincide, and why it fails to coincide.
As soon as you begin providing the results to the calling function,
you have added an error to the original program.
Everyone keeps bring up that point because your last assertion is bollocks.
To produce the contradictory input source, one can take the logic from the
source code of the analyzer and use it to construct input that will cause it
to contradict its own logic.
First of all it will not contradict its own logic, it will merely fail to return a result
that would otherwise cause a contradiction. Secondly it only does this specifically
because an error has been added to its code. If this error is not added, then
it functions correctly. There is nothing to prevent it from functioning correctly
besides the error. If will even function correctly using the program with the error
as input, thus it still works for all possible inputs. Working correctly for all possible
inputs, is what is required to refute the Halting Problem, nothing more, and nothing
less.
You have supposedly taken the ability to
construct that source away by making trivial modifications to the analyzer
and claiming that removing them causes the contradiction to not hold, as if
it were necessary for the input to contain a verbatim copy of the analyzer's
source code to show the contradiction.
This method still works even if the hardware specific devices are not
used. It still works even within the context of the original proof on
an unmodified Turing Machine. In this case the Halt function merely
refrains from returning any result to the function that uses this result
to change its behavior, and thus change the result of the analysis. It
returns its result in every other instance, even if applied to the program
that uses its result to change its behavior. Two different invocations
derive two different results.
Since it gets to see all of the relevant source code, it can easily distinguish
between the return of a value to the program being analyzed, that changes
its behavior based on this return value, and all other invocations. Because
there is a difference that it can see, it can provide different results based on
this difference. Because it can see the difference, the Halting Problem
ceases to be a problem.
In other words, nobody in their right mind would claim that the transition
from
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 // This code never gets executed if the solution is properly
implemented
SecureOutput("Security Has Been Breached, Take Corrective Action");
}
to
int WillHalt(string SourceCode, string InputData)
{
if (TheProgramWillHalt(SourceCode, InputData)) {
SecureOutput("The Program Will Halt");
return TRUE;
}
else if (TheProgramWillNotHalt(SourceCode, InputData)) {
SecureOutput("The Program Will Not Halt");
return FALSE;
}
else { // This code never gets executed if the solution is properly
implemented
SecureOutput("Security Has Been Breached, Take Corrective Action");
return UNKNOWN;
}
}
somehow adds an error into the analyzer that causes the return values to not
correlate with the output statements from the previous version.
Your sledgehammer analogy is flawed because the modification does not cause
your analyzer to malfunction.
BTW, the answer to (3) on halting-problem.com makes little sense to me.
Perhaps supplying an introduction and using two different names for the
bool-returning and void-returning method would be better.
--
David Hilsee
Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
"Stewart Gordon" <sm*******@yahoo.com> wrote in message news:ce**********@sun-cc204.lut.ac.uk...
> Peter Olcott wrote:
>
> <snip>
> > That can't work because WillHalt() does not reurn a value to the calling
> > function.
>
> I'm still waiting to see your example of a function that can't possibly
> be modified to return its result.
>
> Stewart.
>
> --
> My e-mail is valid but not my primary mailbox. Please keep replies on
> the 'group where everyone may benefit.
I can't see why everyone continues to bring up this same point.
It is not any form a valid refutation. It is exactly and precisely
like saying that since it is possible to smash a computer with a
sledge hammer, therefore no computer can be said to ever run
any programs.
Not at all.
The exact equivalent is:
Claim: All computers will run all programs
Disproov: It is possible to smash a computer with a hammer, thus
not all computers can run all programs. At least smashed
computers won't do that.
But the claim that the Halt function will work under all possible conditions
(including smashing its computer) is not the relevant claim. The relevant
claims is simply will the halt function work for every possible input? If it
fails this claim then the Halting Problem continues to exist. If it passes this
claim, then the Halting Problem ceases to exist. It does pass this claim.
It does not! For the simple reason that the Halting problem will not simply
'cease to exist'. The Halting Problem is a question and as such has 2 possible
answers: Yes or no.
The Halting problem is the question: Is there an algorithm which can correctly
and in a deterministic way determine if all algorithms ever come to an halt.
That is the question. There are 2 possible outcomes:
* yes
* no
Since the first one seems to be the answer which is harder to proof, Turing
showed that the second answer is the correct one. The proof is to construct
an algorithm (and the clever part is to use the testing function as part of it)
where this testing function is bound to fail. Thus the answer to the Halting
Problem is: No, there is no such algorithm. Even if we assume that there is
one, it turns out that it is possible to cleverly construct an algorithm which
cannot be correctly analyzed by this assumed algorithm.
You constantly mix up the claim with the proof. The function assumption
of WillHalt() and the construction of LoopIfHalts() is *not* the claim.
They are part of the proof!
Even if you modify the proof in such a way that you circumvent the way this
proof works, it does not mean, that the original proof is no longer valid.
It is still there and serves as a perfect example of why the answer to the
Halting problem is still: 'No, there is no such algorithm'.
--
Karl Heinz Buchegger kb******@gascad.at
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote: You constantly mix up the Halting Problem theorem with its proof.
The Halting Problem is directly derived from its proof.
If the proof is shown to be in error, then the Halting Problem
(which is only derived from the proof) ceases to exist.
The proof is where the loop construction takes place. So even if you
are right, then it would be this specific proof that vanishes into
air. But this does not mean that the theorem itself vanishes.
When the Proof of the Halting Problem fails to prove that the Halting Problem
is a problem, then it ceases to be a problem.
You are not an expert in logic, are you?
Read again what you wrote. In the meantime you got so blind that you
don't even see the simplest logic failures in your argumentation.
--
Karl Heinz Buchegger
kb******@gascad.at
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
Karl Heinz Buchegger
kb******@gascad.at
Purely mathematical proofs can fail to prove their claims specifically
because these purely mathematical proofs abstract away (remove)
details that change the outcome.
Example?
If the solution to a problem requires a separate memory space,
and the mathematical proof disregards a separate memory space
as irrelevant, then the math proof errs.
--
Karl Heinz Buchegger
kb******@gascad.at
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
> I can't see why everyone continues to bring up this same point.
> It is not any form a valid refutation. It is exactly and precisely
> like saying that since it is possible to smash a computer with a
> sledge hammer, therefore no computer can be said to ever run
> any programs.
Not at all.
The exact equivalent is:
Claim: All computers will run all programs
Disproov: It is possible to smash a computer with a hammer, thus
not all computers can run all programs. At least smashed
computers won't do that.
But the claim that the Halt function will work under all possible conditions
(including smashing its computer) is not the relevant claim. The relevant
claims is simply will the halt function work for every possible input? If it
fails this claim then the Halting Problem continues to exist. If it passes this
claim, then the Halting Problem ceases to exist. It does pass this claim.
It does not! For the simple reason that the Halting problem will not simply
'cease to exist'. The Halting Problem is a question and as such has 2 possible
answers: Yes or no.
Nope. The Halting Problem is the problem of not being able to correctly determine
if every program halts. As soon as a method is determined to circumvent the
particular restriction, then the Halting Problem is not a problem. A problem that is
not a problem is a problem no more.
The Halting problem is the question: Is there an algorithm which can correctly
and in a deterministic way determine if all algorithms ever come to an halt.
That is not what has been historically referred to as the Halting Problem.
THE Halting Problem is a much more specific case. It is the case of
specifically showing why this is "impossible".
That is the question. There are 2 possible outcomes:
* yes
* no
Since the first one seems to be the answer which is harder to proof, Turing
showed that the second answer is the correct one. The proof is to construct
an algorithm (and the clever part is to use the testing function as part of it)
where this testing function is bound to fail. Thus the answer to the Halting
Problem is: No, there is no such algorithm. Even if we assume that there is
one, it turns out that it is possible to cleverly construct an algorithm which
cannot be correctly analyzed by this assumed algorithm.
Except that I have just now (in another newsgroup) shown that this is not true.
The Halt analyzer can correctly determine whether or not this cleverly
constructed algorithm halts. Also with my latest method, it can do this
directly within the basic capabilities of a typical Turing Machine. It needs
no special hardware. Since the whole Halting Problem depends on this
proof providing this clever algorithm, and the halt analyzer failing
to correctly process this algorithm, therefore I only need to show how
it can be correctly processed, for the proof, and therefore the Halting Problem
itself, to evaporate. I did this.
You constantly mix up the claim with the proof. The function assumption
of WillHalt() and the construction of LoopIfHalts() is *not* the claim.
They are part of the proof!
Even if you modify the proof in such a way that you circumvent the way this
I don't need to modify the proof, I merely show that it is in error.
proof works, it does not mean, that the original proof is no longer valid.
It is still there and serves as a perfect example of why the answer to the
Halting problem is still: 'No, there is no such algorithm'.
--
Karl Heinz Buchegger
kb******@gascad.at
"Peter Olcott" <ol****@worldnet.att.net> wrote in message
news:wn********************@bgtnsc05-news.ops.worldnet.att.net... Everyone keeps bring up that point because your last assertion is
bollocks. To produce the contradictory input source, one can take the logic from
the source code of the analyzer and use it to construct input that will
cause it to contradict its own logic.
First of all it will not contradict its own logic, it will merely fail to
return a result that would otherwise cause a contradiction.
Yes, it will contradict its own logic. I don't even know what you mean by
"fail to return a result". If you're talking about returning that UNKNOWN
value/displaying "security problem", then forget it, because that is not an
acceptable answer from the analyzer because it means that the analyzer has
failed to process the input correctly. If you do not see how the analyzer
can be forced to contradict its own logic, then you do not understand the
proof. I have posted a URL ( http://www.cgl.uwaterloo.ca/~csk/halt/) that
explains the problem very well, so please read that page as many times as is
necessary for you to understand why it can contradict itself.
The contradiction is very simple:
If the analyzer says the "trick" input program will halt, then, because of
the stolen, embedded logic, that conclusion will imply that it would have
said the program will not halt.
If the analyzer says the "trick" input program will not halt, then, because
of the stolen, embedded logic, that conclusion will imply that it would have
said the program will halt.
The analyzer cannot reach a conclusion that avoids an obvious contradiction.
To be considered a solution, the analyzer is required to determine if any
input halts or does not halt. Therefore, it is not a solution to the halting
problem.
You cannot address this "trick" program by embedding output statements or
making absurd statements about potential errors introduced by return codes.
Also, you cannot address this "trick" program by claiming that the analyzer
will detect if it is analyzing a modified copy of itself and change its
answer accordingly, because that same "answer changing" logic will be
embedded inside the input, which will cause the contradiction once again.
--
David Hilsee
Peter Olcott wrote:
Good luck in your attempt to make a complete fool
of yourself.
I did a quick glance into comp.theory and saw that
you have a really hard time there. Compared to that
group, comp.lang.c++ is a piece of cake.
Karl Heinz Buchegger kb******@gascad.at
Peter Olcott wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message news:41***************@gascad.at... Peter Olcott wrote:
> > I can't see why everyone continues to bring up this same point.
> > It is not any form a valid refutation. It is exactly and precisely
> > like saying that since it is possible to smash a computer with a
> > sledge hammer, therefore no computer can be said to ever run
> > any programs.
>
> Not at all.
> The exact equivalent is:
>
> Claim: All computers will run all programs
> Disproov: It is possible to smash a computer with a hammer, thus
> not all computers can run all programs. At least smashed
> computers won't do that.
But the claim that the Halt function will work under all possible conditions
(including smashing its computer) is not the relevant claim. The relevant
claims is simply will the halt function work for every possible input? If it
fails this claim then the Halting Problem continues to exist. If it passes this
claim, then the Halting Problem ceases to exist. It does pass this claim.
It does not! For the simple reason that the Halting problem will not simply
'cease to exist'. The Halting Problem is a question and as such has 2 possible
answers: Yes or no.
Nope. The Halting Problem is the problem of not being able to correctly determine
if every program halts. As soon as a method is determined to circumvent the
particular restriction, then the Halting Problem is not a problem. A problem that is
not a problem is a problem no more.
You might want to first educate yourself what you are talking about. That is:
What is the question, commonly referred to as the 'Halting Problem', before
continuing to spread nonsense.
--
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: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
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: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
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: 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: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
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: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
| |
