Re: Proficient C Programmers seem to get this right away

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;
}