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 <richard@damon-family.org>
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: <a59d9972692e9ae05bcabfdee72d6d10c46c913d@i2pn2.org>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <vuti3c$jq57$1@dont-email.me> <vutmr6$nvbg$2@dont-email.me>
 <vutv7r$v5pn$4@dont-email.me> <vuu73m$151a8$3@dont-email.me>
 <vuuej8$1cqp7$1@dont-email.me> <vuur2n$1qe3m$2@dont-email.me>
 <vv0352$2ur4q$1@dont-email.me> <vv0kpi$3djh5$1@dont-email.me>
 <vv13ro$3r3ei$1@dont-email.me> <vv160a$3smj7$1@dont-email.me>
 <vv18s7$3uer0$1@dont-email.me> <vv1b03$4a4k$2@dont-email.me>
 <vv1bav$3ra6l$7@dont-email.me> <vv1frt$97hp$1@dont-email.me>
 <vv1gfu$3ra6l$8@dont-email.me> <vv1js4$d4ik$1@dont-email.me>
 <-GOdnZvgEPn-84j1nZ2dnZfqn_SdnZ2d@brightview.co.uk>
 <vv4alu$2t388$1@dont-email.me>
 <K2ednc0OY5rg-Iv1nZ2dnZfqnPednZ2d@brightview.co.uk>
 <vv5rpm$8mnn$1@dont-email.me>
 <YxOdnZxmBe9xL4v1nZ2dnZfqn_SdnZ2d@brightview.co.uk>
 <vv7198$1cr7l$1@dont-email.me>
 <LtOcnfIMycoTJYr1nZ2dnZfqn_GdnZ2d@brightview.co.uk>
 <vv8lj5$2rjp5$1@dont-email.me>
 <ANKdnT6cMpBtqoX1nZ2dnZfqnPSdnZ2d@brightview.co.uk>
 <vv9dld$3ifj7$6@dont-email.me>
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: <vv9dld$3ifj7$6@dont-email.me>

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:
>>>
>>> <snip>
>>>
>>>> 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.
>>>
>>> <snip>
>>>
>>>>> 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;
> }
>