Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Functions computed by Turing Machines MUST apply finite string
 transformations to inputs
Date: Sun, 4 May 2025 20:12:03 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <e3ece82ea5adf453173b19e4d80e02aae0dd231c@i2pn2.org>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <vuivtb$2lf64$3@dont-email.me> <vungtl$2v2kr$1@dont-email.me>
 <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>
 <vv82kc$29nkb$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 5 May 2025 00:28:27 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3165240"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <vv82kc$29nkb$2@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0

On 5/4/25 11:54 AM, olcott wrote:
> On 5/3/2025 7:20 PM, Mike Terry wrote:
>> On 03/05/2025 20:45, Richard Heathfield wrote:
>>> On 03/05/2025 19:50, Mike Terry wrote:
>>>> On 03/05/2025 06:47, Richard Heathfield wrote:
>>>>
>>>
>>> <snip>
>>>
>>>>> In passing, when I nailed down "TL;DR" I felt mildly guilty for 
>>>>> scoring so few tersinosity points, but in return I must accuse you 
>>>>> of undue obscurity.
>>>>>
>>>>> TL;DR appears to have attracted a certain currency, so okay, but... 
>>>>> NTLFM? Really? "Seek and ye shall find", so I sought but shall 
>>>>> findethed not. Most of my best guesses started 'Now The' and ended 
>>>>> rhyming with RTFM, but none of those guesses jumped out as being 
>>>>> self-evidently right. Would you care to translate?
>>>>
>>>> I admit to making it up, but all these (usenet?) abbreviations have 
>>>> to start somewhere, so I thought I would start a much needed new one!
>>>>
>>>> TL;DR = too long, didn't read,
>>>
>>> Yes, that chimes with my research, but...
>>>
>>>> introducing a short summary for someone who hasn't the inclination/ 
>>>> time to read a long (probably overly) verbose explanation.  At least 
>>>> that's how I've seen it used.  But then, how to introduce the 
>>>> verbose explanation?  I couldn't find anything for that, so I 
>>>> invented NTLFM; which means "Not Too Long For Me" !
>>>
>>> Ach! Of course.
>>>
>>>> I'm looking forward to being a footnote in history when it catches 
>>>> on...
>>>
>>> In a footnote to the footnote for NTLFM I would add TOAST --- Too 
>>> Obscure And Startlingly Terse.
>>>
>>>>>> I kind of disagree with your mild denigration of the Linz (and 
>>>>>> similar) proofs.
>>>>>
>>>>> I wish to clarify that denigration was most certainly not my 
>>>>> intent. There is, however, no doubt in my mind that while Linz is 
>>>>> undoubtedly a worthy and indeed admirable computer scientist, his 
>>>>> proof stands on giant shoulders. All I meant to say was that, were 
>>>>> Linz's proof to lose its balance and take a tumble, it would not be 
>>>>> the fault of the shoulders.
>>>>
>>>> Yeah, denigration was really the wrong word, as I know there was no 
>>>> bad intent anywhere.  Perhaps "downplaying" would have been what I 
>>>> was looking for.
>>>
>>> <nod />
>>>
>>>> Ben pointed out there was confusion in the Linz proof with the 
>>>> labelling of states, and when I looked closely at the proof I a few 
>>>> years ago I recall thinking Linz had munged the conversion of 
>>>> (general) TM tape inputs to "H inputs" (which in Linz are binary 
>>>> representations of those tapes) when duplicating D's input.  Now I'm 
>>>> not sure about that, but can't motivate myself to get to the bottom 
>>>> of it, since either way, if it is a problem it's clear how it should 
>>>> be fixed, and the basis for the proof is not affected.
>>>>
>>>> The proof is both "very easy" conceptually [as witnessed by how many 
>>>> people join in here, quickly understanding how it works if they've 
>>>> not come across it before], and slightly fiddly due to the TM H 
>>>> needing to have a fixed tape alphabet which must be able to 
>>>> represent any TM as well as any tape input for that TM.  So there 
>>>> are certainly opportunities to miss details especially with a book 
>>>> aimed at those with a minimal maths background.  Really, the only 
>>>> aspect of the proof requiring careful thought is convincing yourself 
>>>> that the fiddliness has been handled ok, along with understanding 
>>>> the notation used...
>>>>
>>>> I don't see any scope for the proof actually being invalid, and PO 
>>>> certainly does not present any argument for it being invalid. He 
>>>> simply believes his H can give the right answer for his D, and 
>>>> that's the beginning and end of it all.  When he developed his 
>>>> x96utm, it became possible to actually run his code, and it became / 
>>>> manifestly/ clear his H gets the wrong answer for D.  But PO just 
>>>> doubles down and comes up with bizarre explanations for why he still 
>>>> thinks it is right when it is obviously wrong.
>>>
>>> As I re-read Linz /again/, two points stick out:
>>>
>>> "We cannot find the answer by simulating the action of M on w, say by 
>>> performing it on a universal Turing machine, because there is no 
>>> limit on the length of the computation. If M enters an infinite loop, 
>>> then no matter how long we wait, we can never be sure that M is in 
>>> fact in a loop. It may simply be a case of a very long computation. 
>>> What we need is an algorithm that can determine the correct answer 
>>> for any M and w by performing some
>>> analysis on the machine's description and the input. But as we
>>> now show, no such algorithm exists."
>>>
>>> "It is important to keep in mind what Theorem 12.1 says. It does not 
>>> preclude solving the halting problem for specific cases; often we can 
>>> tell by an analysis of M and w whether or not the Turing machine will 
>>> halt. What the theorem says is that this cannot always be done; there 
>>> is no algorithm that can make a correct decision for all WM and w."
>>>
>>>
>>> Both of these statements are self-evidently true, and both would 
>>> appear to knock Mr O's HHH completely out of the water.
>>>
>>> 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. This may be because I'm too dense 
>>> to grok them, or possibly it's because your explanations are TOAST 
>>> (see above).
>>
>> I generally think I post way too much, and tend to wander off topic 
>> with unnecessary background and so on, 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.
>>
>>>
>>> You have said, I think, that Olcott doesn't need a universal decider 
>>> in order to prove his point. But a less ambitious decider doesn't 
>>> contradict Linz's proof, surely? So once more for luck, what exactly 
>>> would PO be establishing with his non-universal and impatient 
>>> simulator if he could only get it to work?
>>
>> Yes.  PO is aiming to refute the /proof method/ that Linz (and 
>> similar) proofs use, i.e. to attack the /reasoning/ behind the proof.  
>> In effect, he is saying that his HHH/DD provide a counter-example to 
>> that reasoning.  His HHH/DD are not full halt deciders - they're / 
>> partial/ halt deciders but that would be enough.  I cover what a 
>> partial HD is below, and why it is enough for his argument [..if HHH/ 
>> DD worked as originally claimed..]
>>
>> If he was successful with his HHH/DD programs, it would mean the Linz 
>> proof contained some logical error, and so the conclusion of the proof 
>> (the HP theorem) would not be warranted /by that proof/, We would have 
>> to cross that proof out of our Master Book Of Mathematical Theorems 
>> And Their Proofs! As there are other proofs of the theorem, the 
>> theorem itself could remain.
>>
>> It would be like the following scenario:  there are many alternative 
>> proofs of Pythagorus' Theorem, but let's imagine that one of them - 
>> the "MikeT" proof - is the first one taught to all school children 
>> across the world, and it's been that way for the last 50 years.  
>> Suddenly PO finds a flaw in that proof!  Sure, there are other proofs 
>> without that flaw so we still trust Pythagorus' Theorem, but we're not 
>> going to continue teaching children an incorrect proof of it, right.  
>> So finding such a flaw would force many changes on our education 
>> system and be highly interesting in its own right.
>>
>> This doesn't explain exactly how PO's HHH/DD would "refute" the Linz 
>> proof, so that's what the rest of the post tries to do.
>>
> 
> The two proofs are isomorphic to each other.
> DD correctly emulated by HHH cannot possibly reach its own
> emulated "return instruction" final halt state.
========== REMAINDER OF ARTICLE TRUNCATED ==========