Path: csiph.com!weretis.net!feeder8.news.weretis.net!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: What I like about programming . . . Date: Wed, 08 Feb 2023 21:07:01 +0000 Organization: A noiseless patient Spider Lines: 97 Message-ID: <87cz6jlvd6.fsf@bsb.me.uk> References: <5m86fnftwotm.osdsbmw7kyzs.dlg@40tude.net> <4e8eb7d5-f3b4-46af-bd39-29f048714f7bn@googlegroups.com> MIME-Version: 1.0 Content-Type: text/plain Injection-Info: reader01.eternal-september.org; posting-host="e6c2d21a060000da0f1f780f5cd368fe"; logging-data="366770"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19v5INBFDzWacrI+sJOqTQt7ifCfu1sQF8=" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux) Cancel-Lock: sha1:zH9Cyk1LRoXoVENqqfN3C1tcHPE= sha1:2DoHBVfjdB3wLvGYzwrrDDCIxAE= X-BSB-Auth: 1.ad47312f6f254ba1420f.20230208210701GMT.87cz6jlvd6.fsf@bsb.me.uk Xref: csiph.com comp.programming:16382 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.