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

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!

 

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.

Ah, that's not what I thought you were thinking.
What you're suggesting doesn't work!  Remember the order - first H is fixed, then H^ is created based on H.  H will fail when deciding halting for input (<H^>,<H^>).
So now you want to edit the code of H to make a new TM which we'll call H2, so that H2 gives the opposite answer to H for any input.  That's great - H2 will correctly decide input (<H^>,<H^>).  You see - there's nothing "undecidable" or "paradoxical" about input (<H^>,<H^>) per se.  H^(<H^>) has an unambiguous behaviour; either it halts or it never halts and either way that dictates the answer that a halt-decider must give.  H gives the wrong answer, but your H2 gets it right.
As I said, that's great, except... the HP proof doesn't claim that H2 will decide (<H^>,<H^>) incorrectly!  What it says is that H2 will decide (<H2^>,<H2^>) incorrectly.  To build H2^ we need to follow the Linz recipe again, but starting from H2 instead of H, so H2^ is different from H^.
And what do you know?  When we ask H2 whether H2^(<H2^>) halts, it will give the wrong answer.  With a little thought we see that the original H will give the right answer for input (<H2^>,<H2^>), but again that's not contradicting anything in the HP proof, so no help to PO.
PO likes to imagine that there's something Wrong with H^ or H2^ which warrants them being excluded from HP or treated differently re. definition of halting etc..  Normally he does that by pretending that H and H1 are "one machine", and "whichever decision that machine makes it will be wrong!!", so we have Pathelogical Self Refernce or some kind of paradox or what not.  Thinking clearly as above (and giving distinct names for distinct objects helps) makes it clear he's just muddling things up.
Mike.