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

On 04/05/2025 07:25, Richard Heathfield wrote:

On 04/05/2025 01:20, Mike Terry wrote:

On 03/05/2025 20:45, Richard Heathfield wrote:

 <snip>
 

>
I am conscious that you have already explained to me (twice!) that Mr O's approach is aimed not at overturning the overarching indecidability proof but a mere detail of Linz's proof. Unfortunately, your explanations have not managed to establish a firm root in what passes for my brain.

 Third time's a charm, I think, or at least I'm further forward. (See question about a mile VVVVVsouthVVVVV of here.)
 In case I ever bail again, you have my full permission to remind me of <~/alldata/usenet/M_Terry_explains_olcott_reasoning.eml> where I have saved your reply for future re-enlightenment.
 

This may be because I'm too dense to grok them, or possibly it's because your explanations are TOAST (see above).

 Turned out to be 50/50.
 

I generally think I post way too much,

 I think Usenauts are best measured by their S/N ratio. That is, it's what you post rather than how much there is of it.
 

and tend to wander off topic with unnecessary background and so on,

 Isaac Asimov was always at his happiest when starting an essay with the magic words "The Ancient Greeks..." In 1965 he wrote a book to be called "The Neutrino". He spent the first three quarters or so of the book on what he considered to be /necessary/ background, and Chapter 500-or-so is called "Enter The Neutrino". When he got the proofs back for checking, he saw that his copy editor had pencilled into the margin "AT LAST!"
 

and probably I write too much from a "maths" perspective, because that's my background.  Not sure if I can change any of that! :)  Just ask if I use obscure notation or let me know if I'm going too fast/slow.  Part of the problem is I don't know your background and what things you're super familiar with.

 ISTR that I have recently gone on record as claiming (when asked if I have ever done any programming) to be a professional potato painter. The claim is rather less accurate than I generally try to be, and whilst it is true that I am super familiar (and perhaps too familiar) with potatoes, I haven't actually painted one since infants' school.
 My background? Unfortunately my potato-painting career never really took off, so I decided instead to earn my corn writing computer programs for a living.
 Any good?

Sure.  I expect everyone here has done more than enough programming to .  It was more how much maths background you have + familiarity with HP proof you have.
<..snip..>

 

BTW, when I refer to "the Linz proof" it is purely because the Linz book is apparently the one that PO has access to, and when he started posting here he claimed to have refuted the "Linz" proof that appears in that book.  As you suspect, the proof is nothing to do with Linz other than appearing in his book!

 I am reminded of Hellin's Law, which documents the as yet unexplained fact that for n>1, n-tuple births occur once in 89^{n-1} pregnancies. In 1895, Hellin wrote down what biologists and demographers had already known for years. This penmanship appears to be his only contribution to the matter, and yet... Hellin's Law.

Well, Linz doesn't get "Linz's proof", except here in PO thread land.  He's just one of dozens of authors covering the proof, not the first or last, but simply the one PO talks about...

 

  It also appears I expect in some form in most computer science books covering computation theory, because it's so well known.  Hmm, not sure who discovered it, but it would be one of the big guys like Turing, Church, Kleene,... all doing related work in the early days of the field.

 Turing, I think., in 1936.
 ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO
THE ENTSCHEIDUNGSPROBLEM
 I have a 2MB PDF copy. I can't remember where I found it but, if you want it, drop me an email and I'll send it by return.

Thanks, but I have a PDF tucked away.  You may be right that it is where the halting problem first gets covered, or at least HP for TMs.

 

So to say what PO's code would refute, I need to explain exactly how the Linz proof works.  Sorry if you already perfectly clear on that!

 I'm fine with the general idea of the proof. If we have a universal decider U we can (easily!) use it to make a program that it can't decide, and we have reductio QED.
 <snipped but not skipped>
 

This next bit might be a missing key for you...    Looking at the above, we started by me giving you a "halt decider" H.  What if I only gave you a lesser achievement: a "partial halt decider" that correctly decides halting for certain (P,I) inputs, but fails to halt for all the rest?

 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!  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 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.
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]
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.]

4) always make the same decision when given the same input (clearly desirable);
5) be trivial to write;
6) would step around all the simulation nonsense and puncture about 99% of the current quarrel.
7) It could obviously be arranged if need be to interpret the hash mod 2 so that when fed itself as input it gets itself (a) right or (b) wrong.

Yes PHDs can be trivial, even given they are not allowed to give wrong answers.  A PHD could examine its input and check whether the starting state is a halt state.  If it is, it returns HALTS otherwise it just loops (or return DONT+KNOW if we allow that).  That's not very useful to anyone, but more functional PHDs may be of genuine use to developers.
Or a PHD could simulate its input and examine the computation steps for tight loops.  If it spots one it decides NEVER_HALTS, and if the simulation halts it decides HALTS.  That is a valid PHD which would sometimes decide halting correctly, and never decide incorrectly.  It is a bit like PO's H, except that PO's H has further tests beyond the simple tight loop test.  One of those tests is unsound, in that it is intended to detect non-halting behaviour but it can also match inputs that halt.  [That's what happens with his HHH/DD pair]

 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.  [Hmm, I think that was Malcolm McLean who hasn't posted for a couple of years.]
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.
His H could just return NEVER_HALTS straight away, which it is going to do later on anyway for input (<H^>,<H^>).  The logic of how it gets that decision doesn't really matter!  The H^ built from that H will internally run its embedded_H code which will similarly "decide" DOESNT_HALT and H^ will then halt.  That's all the same as in PO's actual code, HHH/DD but without all the faffing around with simulations!!  :)  Yes, coding H like that means it will get other inputs completely wrong - but so what?  We are just interested in what happens with that one input case.
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/.  His simulation loop watches for a particular (unsound) "non-halting" pattern, and it sees it when simulating H^(<H^>), which is one of PO's justifications for saying that H^(<H^>) "really" never halts, even though it does.  If he just had stub routines that returned NEVER_HALTS without seeing the "non-halting" pattern, the big picture outcome would be exactly the same, but he'd lose his justification that maintains his intuition that H^ never halts.
Mike.