Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!border-3.nntp.ord.giganews.com!nntp.giganews.com!Xl.tags.giganews.com!local-3.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 03 May 2025 18:50:37 +0000
Subject: Re: Functions computed by Turing Machines MUST apply finite string
 transformations to inputs
Newsgroups: comp.theory
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <87cyd5182l.fsf@nosuchdomain.example.com> <vu6lnf$39fls$2@dont-email.me>
 <vugddv$b21g$2@dont-email.me> <vui4uf$20dpc$1@dont-email.me>
 <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>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Sat, 3 May 2025 19:50:40 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
MIME-Version: 1.0
In-Reply-To: <vv4alu$2t388$1@dont-email.me>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <K2ednc0OY5rg-Iv1nZ2dnZfqnPednZ2d@brightview.co.uk>
Lines: 68
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-cP25JwoqP0eodXaAwPqUBmmMmVv1CXjaO+WRJCvpzVZ2kY5U//OKUCrhjAGtn2Y/d2Z6yKZgIttIJ/u!4GgUX1GDi4YUeQkBRLyJsmYJA+ST6AO/RqywTZ4crGys9Od9bSFFCJe3/GAEuVb1gpqx/Y2nFa4S!cScChSB9xx9Kaly5uFzfR9u7LuY=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40

On 03/05/2025 06:47, Richard Heathfield wrote:
> On 03/05/2025 02:16, Mike Terry wrote:
>> For your point of view I could probably just have said "It's bleedin' obvious that the input D 
>> can't be changed to D' (or anything else) half way through interpreting Sipser's words".
> 
> Yes, that would cover it.

:)

> 
>> Also probably that would be enough for you to get that your interpretation of "changing the input" 
>> went down the wrong road...
> 
> More than enough.
> 
> 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, 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" !  I'm looking forward to being a 
footnote in history when it catches on...

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

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.


Mike.