From: ben.usenet@bsb.me.uk
Richard Heathfield writes:
> On 08/02/2023 3:03 pm, Paul N wrote:
>> On Tuesday, February 7, 2023 at 9:58:29 PM UTC, JJ wrote:
>>> If you go to any programming sub in Reddit, or any programming channel in
>>> Discord, you'll realize that some people aren't capable of realizing that
>>> they are wrong.
Yes, it's a rather quaint idea. Some subjects might make it easier for
people with open minds to discover their mistakes, but it's very far
from being universal!
>> This is even more obvious in comp.theory. There is a poster there who
>> claims to have refuted the Halting Problem proof,
>
> I refute it too. Bear with me.
OK...
>> and to have a system which can accurately determine whether a program
>> will halt or not.
>
> I, too, have such a system. Bear with me.
This is a rather different claim. The "Halting Problem proof" surely
refers to a proof of a specific mathematical theorem, so it's not clear
in what way any particular C program refutes it.
>> He has a demonstration program, which he claims does not halt
His claims change, but when I last checked in he (the loon in
comp.theory) was still being clear that the program in question halts.
He's posted code, he's posted traces of the simulation, he's stated it
in plain words.
> He is mistaken.
On this point, no.
>> and which his detector identifies as non-halting.
>
> His detector errs.
>
>> He does however accept that when said program is run, it halts.
Just to clear up the nonsense he spouts, he claims that "non-halting" is
the right answer because of what /would/ happen if the program were not
stopped -- that the program in question only halts because it is stopped
"by itself". Yes, it's bonkers, but he maintains he's right because
he's changed what "halting" means.
>> can't accept that his simulation is incorrect, however, and instead
>> argues that this is proof that a program can behave differently when
>> it is "directed executed" from when it is "correctly simulated". He
>> goes on to say that it is correct for his detector to determinate
>> what will happen when the program is correctly simulated, rather than
>> what happens when it is run, and so his detector is correct. Numerous
>> people have pointed the problems out to him, but he keeps posting to
>> say that no-one has ever posted a correct refutation.
>
> Here is my refutation. Feed it with any program you like via a pipe.
>
> #include
>
> int main(void)
> {
> int ch;
> while((ch = getchar()) != EOF)
> {
> continue;
> }
> puts("If executed, the specified program will halt.");
> return 0;
> }
The proof is of a theorem about Turing machines. More importantly, the
property in question -- halting -- is one which, in the context of
Rice's theorem, is often called an "interesting" property of program
behaviour, i.e. it is possessed by some programs and not others. No
universal property of program behaviour is "interesting" in this sense,
so it's clear that this program can't be about whatever it is the
theorem is about.
OK, /I/ know you are joking, but will everyone? Do we want any more
people confused about what the halting theorem is about?
I think the fact that the term "halting" is so open to interpretation
(as here) is what makes it a magnet for cranks. (I know you are not a
crank, you are just having a bit of fun). No crank has ever stated that
they have a program that can compute the busy-beaver function, solve
Post's correspondence program or determine if a given context-free
grammar is ambiguous or not. Those problems are far too clear. It's
always some take on halting. I suppose that's why I get a bit cranky
myself when it comes up like this.
--
Ben.
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
