Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Turing Machine computable functions apply finite string
 transformations to inputs VERIFIED FACT
Date: Thu, 1 May 2025 08:51:47 +0100
Organization: Fix this later
Lines: 91
Message-ID: <vuv96l$27hsa$1@dont-email.me>
References: <vu6lnf$39fls$2@dont-email.me>
 <65dddfad4c862e6593392eaf27876759b1ed0e69@i2pn2.org>
 <vujlj0$3a526$1@dont-email.me> <vujln7$32om9$8@dont-email.me>
 <vujmmm$3a526$2@dont-email.me> <vujmrj$32om9$9@dont-email.me>
 <vujtcb$3gsgr$1@dont-email.me> <vuju44$3hnda$1@dont-email.me>
 <vuk47o$3qkbb$1@dont-email.me> <vuk6b6$3l184$1@dont-email.me>
 <vuls34$1bf1j$4@dont-email.me> <vun87k$2m24h$2@dont-email.me>
 <vunb06$2fjjl$5@dont-email.me> <vuo57j$3h5l9$2@dont-email.me>
 <vuoath$3ljma$1@dont-email.me> <vuohgi$3td7u$1@dont-email.me>
 <vuonh6$2g74$2@dont-email.me> <vupeor$qf60$1@dont-email.me>
 <vupu0r$18vrc$1@dont-email.me> <vuqj5u$1rljg$1@dont-email.me>
 <vuql8e$1svmd$1@dont-email.me> <vur7vd$2dvvs$1@dont-email.me>
 <vur9t9$2gjif$1@dont-email.me> <vurasr$2hkih$1@dont-email.me>
 <vurbgd$2gjif$2@dont-email.me> <vurgt8$2n355$1@dont-email.me>
 <vuric8$2gjif$3@dont-email.me> <vutepm$gmbi$4@dont-email.me>
 <vutgjt$hkal$3@dont-email.me>
 <djSdneHlvK3B8Y_1nZ2dnZfqnPqdnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 01 May 2025 09:51:53 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="83704e13d49c1d6790a9eb90f14197c2";
	logging-data="2344842"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+mxUB7RlMaLpA1QiMJEZMoMSchAemN+Xu0qDCAEEhWYA=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:dVo4oEekP8SvZl5XM84U86ORCzo=
In-Reply-To: <djSdneHlvK3B8Y_1nZ2dnZfqnPqdnZ2d@brightview.co.uk>
Content-Language: en-GB

On 30/04/2025 19:30, Mike Terry wrote:
> On 30/04/2025 16:46, Richard Heathfield wrote:
>> On 30/04/2025 16:15, olcott wrote:
>>> On 4/29/2025 5:03 PM, Richard Heathfield wrote:
>>>> On 29/04/2025 22:38, olcott wrote:
>>>>
>>>> <snip>
>>>>
>>>>>
>>>>> int DD()
>>>>> {
>>>>>    int Halt_Status = HHH(DD);
>>>>>    if (Halt_Status)
>>>>>      HERE: goto HERE;
>>>>>    return Halt_Status;
>>>>> }
>>>>>
>>>>> HHH is correct DD as non-halting BECAUSE THAT IS
>>>>> WHAT THE INPUT TO HHH(DD) SPECIFIES.
>>>>
>>>> You're going round the same loop again.
>>>>
>>>> Either your HHH() is a universal termination analyser or it 
>>>> isn't. 
>>>
>>> The domain of HHH is DD.
>>
>> Then it is attacking not the Halting Problem but the Olcott 
>> Problem, which is of interest to nobody but you.
> 
> It would be (if correct) attacking the common proof for HP 
> theorem as it occurs for instance in the Linz book which PO links 
> to from time to time.

Yes. That's what I call the Olcott Problem.

De gustibus non est disputandum, but I venture to suggest that 
(correctly) overturning Turing's proof would be of cosmos-rocking 
interest to the world of computer science, compared to which 
pointing out a minor flaw in a minor[1] proof would, even if 
correct, have no more effect on our field than lobbing a pebble 
into the swash at high tide.

I suspect that the only reason we bother to argue with Mr Olcott 
so much is because (even if he does so unwittingly) he manages to 
convey the appearance of attacking the Halting Problem, and 
arguing about the Halting Problem is a lot more fun than arguing 
about the Olcott Problem.

To be of any interest, solving the Olcott Problem would have to 
have important consequences. But does it? Let's see.

Dr Linz Theorem 12.1 (Halting Problem is Undecidable): There does 
not exist any Turing machine H that behaves as required by Linz 
Definition 12.1. Thus the halting problem is undecidable.

Dr Linz has a proof for this claim, which can be found here: 
<https://john.cs.olemiss.edu/~hcc/csci311/notes/chap12/ch12.pdf>

If the proof is flawless, the conclusion stands and Mr Olcott is 
simply wrong.

If the proof is flawed through some error of reasoning, *either* 
it merely fails to correctly support its conclusion *or* a duly 
corrected proof /overturns/ the conclusion.

The latter would be /extremely/ interesting, but it would also 
mean that we have two proofs proving opposite things, and so it 
would effectively be a cataclysmic sideways attack on Turing's 
reasoning.

If Mr Olcott claims that he's not attacking Turing's proof, he is 
not attacking Dr Linz's conclusion, and his attack on the Linz 
proof can /at worst/ point out a minor error, which might be of 
interest to Mr Olcott and possibly even to Dr Linz if he ever got 
to hear about it, but it's hard to see what wider interest it 
holds, because what matters is Dr Linz's /conclusion/, and the 
conclusion is that the Halting Problem is undecidable. Unless Mr 
Olcott can overturn /that/ (which of course he can't), he has 
nothing worth wasting a lifetime over.

[1] If by some strange chance Dr Linz ever reads this, I hope he 
won't be too upset by 'minor' when I compare his proof to 
Turing's ground-breaker.

-- 
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