Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory Subject: Re: Proficient C Programmers seem to get this right away Date: Mon, 5 May 2025 07:05:39 -0400 Organization: i2pn2 (i2pn.org) Message-ID: References:

<-GOdnZvgEPn-84j1nZ2dnZfqn_SdnZ2d@brightview.co.uk>

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 5 May 2025 11:32:10 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="3229673"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird Content-Language: en-US X-Spam-Checker-Version: SpamAssassin 4.0.0 In-Reply-To: On 5/5/25 12:09 AM, olcott wrote: > On 5/4/2025 11:00 PM, Mike Terry wrote: >> On 04/05/2025 22:18, Richard Heathfield wrote: >>> On 04/05/2025 19:57, Mike Terry wrote: >>> >>> >>> >>>> It was more how much maths background you have >>>> + familiarity with HP proof you have. >>> >>> Sorry for the noise, then. >>> >>> Very little. I rattled through the first ten years easily enough, but >>> I hit a hard wall (integration by parts) and never really recovered. >>> Such mathematics as I have picked up since has mostly been through >>> popularisers such as Martin Gardner, Ian Stewart, and Douglas >>> Hofstadter. I think it was in Hofstadter that I first learned of the >>> Halting Problem. >>> >>> >>> >>>>> What's to stop the partial decider from deciding pseudorandomly? >>>>> For example: hashing the input tapes and deciding according to the >>>>> hash modulo 2? This would: >>>>> >>>>> 1) always decide (as required); >>>>> 2) sometimes get it right (as required); >>>>> 3) sometimes get it wrong (as required if it's to be only 'partial'); >>>> >>>> No, partial halt deciders [*PHD*s] aren't supposed to get it wrong! >>> >>> We must distinguish carefully between PHDs and PhDs (although, come >>> to think of it, PhDs aren't supposed to get it wrong either). >>> >>> But... okay, I'll read on... >>> >>>> If they don't know the answer they're supposed to never answer, but >>>> if they do answer [i.e. HALTS or NEVER_HALTS] it must be right. We >>>> could define PHDs so that they have a 3rd answer DONT_KNOW, but >>>> assuming we still allow them to never answer I don't see that the >>>> DONT_KNOW answer adds much. [the new PHDs would be equivalent to my >>>> definition] >>> >>> If they never answer, how long do we wait for nothing to happen? >> >> How much time do you have to invest in getting an answer? You could >> wait 1 day, and if there's no answer count it as a don't know. >> >> You could upgrade from a PHD to one of those new-fangled HDs that are >> "guaranteed to answer". But then how long do we wait for our >> guaranteed answer? Again it depends how much time we're willing to >> invest - in real life we have to set a timeout - e.g. 1 day - and if >> it's not answered by then we move, accepting that we still don't >> know! Is the HD really worth the upgrade cost? :) >> >> These sorts of Computation Theory concepts are theoretical in nature. >> We already have concepts like TM "Language Accepters" which accept the >> precisely the strings of a given Language. That is, the TM starts >> with the test string on its input tape, and halts in a final state >> precisely when the string belongs to the language. Strings not in the >> language may result in the TM never halting [or, it may be allowed to >> halt in a / non-final/ state]. >> >>> >>>> If we add a DONT_KNOW answer, and then insist the PHD must halt with >>>> one of the 3 answers, I think that would be a different concept, >>>> because a PHD might be searching for a particular test condition and >>>> never find it. That would be an infinite loop, which I consider >>>> reasonable, but if it is forced instead to decide DONT_KNOW in >>>> finite time, then such a potentially unending search would be >>>> excluded. So I think we have a different concept of PHD now. >>> >>> I've got my wallet in my hand, but I'm not quite ready yet to buy a >>> PHD that doesn't answer. DONT_KNOW is conceptually easier to swallow >>> (even though the mileage doesn't look all that great). >>> >>>> Actually, while I've talked about PHDs which are not allowed to >>>> decide incorrectly, in fact for PO's purposes it wouldn't matter if >>>> we allowed PHDs to decide inputs incorrectly like you're imagining. >>>> We could be talking about a new type of TM, maybe call it a >>>> "Putative PHD" [*PPHD*] which takes the (P,I) input, and may decide >>>> HALTS/ NEVER_HALTS or never decide, and PPHDs have no requirement to >>>> answer correctly. [PO's HHH is really a PPHD, not a PHD as it >>>> sometimes answers incorrectly] >>> >>> Which raises the question of why he bothers. >> >> PO does not acknowledge that his HHH gives the wrong answer! >> > > It is very difficult for me to understand how anyone > as bright as you cannot understand that the FINITE > STRING INPUT TO HHH is correctly simulated so that > HHH also simulates itself simulating DD. Why don't you understand that your HHH doesn't correctly simulate its input, as it stops before it gets to the end? > > Proficient C programmers seem to get this right away.\ No Proficient C programmers know the meaning of correct. > > int DD() > { > int Halt_Status = HHH(DD); > if (Halt_Status) > HERE: goto HERE; > return Halt_Status; > } >