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.

Proficient C programmers seem to get this right away.

int DD()
{
int Halt_Status = HHH(DD);
if (Halt_Status)
HERE: goto HERE;
return Halt_Status;
}

--
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

--- MBSE BBS v1.1.1 (Linux-x86_64)
* Origin: A noiseless patient Spider (3:633/280.2@fidonet)