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

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.