Re: Functions computed by Turing Machines MUST apply finite string transformations to inputs

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?

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.

Everything I've said about PHD's in relation to PO's claims to refute Linz, would work equally well with PPHDs!  That's because all that really matters for PO is that the ONE SPECIFIC INPUT (<H^>,<H^>) must be decided correctly.  It's still the case, even for PPHDs, that the reasoning used in the Linz proof implies that if H is a PPHD, H will NOT decide input (<H^>,<H^>) correctly.  So if PO could provides even a PPHD H that decides (<H^>,<H^>) /correctly/ that shows a problem with the Linz proof logic.  [Of course, PO cannot provide such an H.]

Well, it's not hard. Scaffolding first (not for publication):
1) he writes H(P,D), which hashes P and D (md5 hash, say? Or even just add up the bits!) and returns mod 2 of the result, interpreting 0 as 'loops' and 1 as 'halts'
2) he waves Turing's magic wand and sees whether he gets the result he needs for (<H^><H^>).
3) if so, great! But if not, he reverses the meanings of 0 and 1.
4) remove from the docs all signs of fiddling the mod 2 meanings.
Having 'tuned' his PPHD, he can now publish and claim his place in history.
<snip>

Clearly this won't do, because surely /somebody/ would have pointed it out by now, but... /why/ won't it do?
>

 That's a good question!
 Given that PO's /only aim/ is to deliver an H which works for ONE SPECIFIC INPUT (<H^>,<H^>), why can't he just assume in his code for H that that is the input, and simply give whatever answer he needs for his argument to work?  Someone else pointed this out a few years ago - PO could just write a trivial stub that works in this one input scenario.

I would have been surprised to learn that it hadn't already come up.

  [Hmm, I think that was Malcolm McLean who hasn't posted for a couple of years.]

I hope he's okay. (Malcolm and I have crossed many swords and we rarely agreed, but I recall him being a most well-mannered and personable fellow.

Logically that makes perfect sense.  But for PO I suppose the answer is that if he just did that, it would be too obvious that it Just Doesn't Work.  In fact it would be obvious that it /can't/ work due to the way H^ relates to H, together with the reasoning in the Linz proof.

It's already obvious that his HHH doesn't work, but... well, perhaps one man's obvious is another man's Turing Award.
<snip>

In the end the answer to your question is that PO /needs/ all the faffing with simulation to maintain his faulty intuitions /in his own mind/.

Yes, I think there's something in that. And he has to retain the illusion that he's achieved something difficult.
<snip>
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within