Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Functions computed by Turing Machines MUST apply finite string
 transformations to inputs
Date: Sun, 4 May 2025 22:18:27 +0100
Organization: Fix this later
Lines: 141
Message-ID: <vv8lj5$2rjp5$1@dont-email.me>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <vuoaac$3jn5n$5@dont-email.me> <vuq81v$1hjka$1@dont-email.me>
 <vutefq$gmbi$3@dont-email.me>
 <991dde3a60e1485815b789520c7149e7842d18f2@i2pn2.org>
 <vuti3c$jq57$1@dont-email.me> <vutmr6$nvbg$2@dont-email.me>
 <vutv7r$v5pn$4@dont-email.me> <vuu73m$151a8$3@dont-email.me>
 <vuuej8$1cqp7$1@dont-email.me> <vuur2n$1qe3m$2@dont-email.me>
 <vv0352$2ur4q$1@dont-email.me> <vv0kpi$3djh5$1@dont-email.me>
 <vv13ro$3r3ei$1@dont-email.me> <vv160a$3smj7$1@dont-email.me>
 <vv18s7$3uer0$1@dont-email.me> <vv1b03$4a4k$2@dont-email.me>
 <vv1bav$3ra6l$7@dont-email.me> <vv1frt$97hp$1@dont-email.me>
 <vv1gfu$3ra6l$8@dont-email.me> <vv1js4$d4ik$1@dont-email.me>
 <-GOdnZvgEPn-84j1nZ2dnZfqn_SdnZ2d@brightview.co.uk>
 <vv4alu$2t388$1@dont-email.me>
 <K2ednc0OY5rg-Iv1nZ2dnZfqnPednZ2d@brightview.co.uk>
 <vv5rpm$8mnn$1@dont-email.me>
 <YxOdnZxmBe9xL4v1nZ2dnZfqn_SdnZ2d@brightview.co.uk>
 <vv7198$1cr7l$1@dont-email.me>
 <LtOcnfIMycoTJYr1nZ2dnZfqn_GdnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 04 May 2025 23:18:30 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9ffacb51a2e5e1917b8e6e99f1b58e9a";
	logging-data="3002149"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18ucWFdyWvzxKs6v+L3NoY568XEq8OsytUfKrnaGeUxYA=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:koMH3pff6v4VCmKsaKNdMYvEKfc=
Content-Language: en-GB
In-Reply-To: <LtOcnfIMycoTJYr1nZ2dnZfqn_GdnZ2d@brightview.co.uk>

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