On 02/05/2025 06:06, Richard Heathfield wrote:
On 02/05/2025 05:08, dbush wrote:
On 5/1/2025 11:57 PM, olcott wrote:
On 5/1/2025 9:40 PM, dbush wrote:
<snip>
So you changed the input. Changing the input is not allowed.
>
>
I never changed the input.
>
Yes you did. You hypothesize changing the code of HHH, and HHH is part of the input. So you changed the input.
Agreed.
Changing the input is not allowed.
Wweellll...
I have a very minor objection to that view, an objection that I've wrapped up into a thought experiment.
Let us hypothesise the paradoxical existence of U, a universal decider. If we pass it an arbitrary P and an arbitrary D, it can defy Turing (we're just hypothesising, remember) and produce a correct result. Cool, right? The snag is that it's a black box. We can't see the code.
We set it to work, and for years we use it to prove all manner of questions - PvNP, Collatz, Goldbach, Riemann, the lot - and it turns out always to be right. That's good, right?
But then one fine day in 2038 we are finally allowed to see the source code for U, which is when we discover that the algorithm >>>changes the input<<< in some small way. Does that invalidate the answers it has been providing for over a decade, thousands of answers that have /all/ been verified?
Nobody would suggest that TMs aren't allowed to write to their tape! Of course, that's part of how they work, and is not what posters mean by PO "changing the input".
I would argue that it doesn't. Provided U(P,D) correctly reports on the behaviour a P(D) call would produce, I would argue that that's all that matters, and the fact that U twiddles with the P and D tapes and turns them into P' and D' is irrelevant, as long as the result we get is that of P(D), not P'(D').
Right. What you're describing is business as usual for TMs.
Let me show this graphically using a much simpler example - addition:
D: 1111111111+1111111
P: add 'em up
P(D)!
D': 11111111111111111
P has changed its input by changing the + to a 1 and erasing the last 1, and D' now holds the correct answer to the question originally posed on D.
I would argue that this is /perfectly fine/, and that there is nothing in Turing's problem statement to forbid it. But of course we must be careful that, even if U does change its inputs to P' and D', it must still correctly answer the question P(D).
Nothing wrong with that.
BTW all the stuff above about universal deciders turns out to be irrelevant to your argument! (It just seems a bit odd to choose a non-existant TM as an example when any other (existant) TM would do the job more clearly...)
Of course, Mr Olcott's change is rather different, because by changing his HHH he's actually changing the behaviour of his DD - i.e. specifying a new U - but I see no reason why he can't do that /provided/ he can show that he always gets the correct answer. He has so far failed to do this with the original HHH, and now he has doubled his workload by giving himself another HHH to defend.
Right - PO's H is free to rewrite the tape in whatever way it likes, provided in the end it gets the right answer.
The "you're not allowed to change the input" charge means something quite different.
TLDR: Your talking about TMs writing to their tape as part of their normal operation. Nothing wrong with that. PO is effectively talking about changing the meaning of D [the input to H] half way through the Sipser quote.
-----------------------------------------------------------------------------
NTLFM:
PO is trying to interpret Sipser's quote:
--- Start Sipser quote
If simulating halt decider H correctly simulates its input D
until H correctly determines that its simulated D would never
stop running unless aborted then
H can abort its simulation of D and correctly report that D
specifies a non-halting sequence of configurations.
--- End Sipser quote
The following interpretation is ok:
If H is given input D, and while simulating D gathers enough
information to deduce that UTM(D) would never halt, then
H can abort its simulation and decide D never halts.
I'd say it's obvious that this is what Sipser is saying, because it's natural, correct, and relevant to what was being discussed (valid strategy for a simulating halt decider). It is trivial to check that what my interpretation says is valid:
if UTM(D) would never halt, then D never halts, so if H(D) returns
never_halts then that is the correct answer for the input. QED :)
The key point is that throughout the quote, D is regarded as a fixed input being decided, and the quote provides a valid strategy that H might use *for that input*. It's also basic maths practice that they define symbols [like H,D] and then those symbols retain those meanings [values] thereafter. A programmer might say the definitions are (like) "immutable variables" I guess(?). Anyway having defined H,D in the Sipser quote, they don't suddenly change into something else half way through!
PO wants to interpret it as:
--- My interpretation of what PO is /effectively/ arguing
If H is given input D, and while simulating D gathers enough
information to deduce that UTM(D') would never halt, then
H can abort its simulation and decide D never halts, where
D' is D, but edited so that any code in D that looks similar
to H is replaced with the code for UTM.
---
Or something equivalent in effect. The point is that the above is no longer valid. Basically, in the obvious argument I gave above for /my/ Sipser quote interpretation, we can no longer argue that UTM(D') halting implies D halting, and so H returning non_halting is no longer warranted.
I've spelled everything out here with baby steps to give PO maximum chance of understanding what I'm saying, even though there is no way he is capable of understanding what I wrote. [In that regard I've completely wasted my time...]
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". Also probably that would be enough for you to get that your interpretation of "changing the input" went down the wrong road... so
Of course, PO would be incapable of expressing his interpretation as well as I did above, because he just lacks the intellect to analyse abstract problems, use notations and terms correctly etc.. So I expect him to disagree that I've given a correct summary of what he's thinking.
PO would say that H is replaced by UTM and that's it. Hopefully you realise, in PO's x86utm world H is also called directly from within D. (That's not possible with TMs.) So if you change H in any way, that changes D's behaviour - i.e. you've changed D as well.
In the TM world, the <D> in H(<D>) is the /text encoding/ of D, which contains somewhere within it a text encoding of the /embedded/ and /modified/ H. All just data... If we talked about hypothetically replacing H by a UTM in /this/ environment there are no traps to fall into.
H(<D>) is H with tape contents 011010100010001100111010100010111010101001111
(say, where I've used that binary string as <D>, the representation of TM D. In reality the string would be MUCH longer of course, but that would hinder understanding. In fact, to be definite lets say the 01011101010100 substring at offset 27 is the embedded logic of modified H) and
UTM(<D>) is UTM with tape contents 011010100010001100111010100010111010101001111
To save you checking the binary strings are the same, they are - the input has not changed. The input contains the same text encoding of the embedded/modified H as in H(<D>). We don't edit bits of that string at offset 27 to replace embedded-H functionality with UTM functionality. (Duh! but that is in effect what PO wants to do. He should pay more attention to the code/data distinction...)
In PO's x86utm, his C code has functions DD an HHH, and DD directly calls HHH (in its "embedded withing D" capacity), and also when HHH runs DD, it is called as HHH(DD) with the address of DD being passed rather than a full text string like 011010100010001100111010100010111010101001111 (which contains full description of D along with its embedded H copy...). You see that if PO did not conflate his code and data, it would be much harder for him to argue for his confusions!
For completeness, PO's equivalent for what he wants (UTM(<D'>) would be something like
UTM(<D'>): UTM with tape contents 0110101000100011001110101001001011101011111
(note binary string differs from above - "Input Changed!"
------------------------------------------------------------------------------
Whatever 'solution' he eventually settles on, it will be easy to construct a P and a D that it fails to decide correctly, because Turing.
Well, his 'solution' is is HHH, and the D you describe is his DD. HHH(DD) returns non-halting, and DD() halts, so you're right: His P fails with the "Linz" D.
Whether his 'solution' can invalidate Linz's proof is another matter; it's a mere technical question of little interest but, if push came to shove, my money would definitely be on Linz.
The Linz proof correctly predicts the behaviour of PO's HHH/DD, so the proof is not invalidated. And putting your money on Linz would be a good bet, although absolutely nobody would be offering such a bet!
I kind of disagree with your mild denigration of the Linz (and similar) proofs. Yes, there are other proofs, so the HP Theorem would still stand. But...
But /that/ proof is in hundreds of text books on the subject, and I would bet it is taught to tens of thousands of CS students every year, even if other (probably more abstract) proofs are also taught. If it turned out that proof was /fundamentally/ wrong, A LOT of people would be EXTREMELY interested. Lecture courses the world over would need to be corrected overnight, new editions of books issued (in principle, obviously that's not going to happen straight away), and PO as the discoverer would get some recognition, likely in the world press.
To offer some justification for my "world press" claim: the proof is so well known and "easy to explain" for TV reporters, at least in comparison to most maths results. Reporters love it when those "maths boffins" get their comeupance having got something "simple" like that wrong for so many years! :) ).
But that's all just a PO fantasy - one of his many delusions...
Of course, if PO has identified a flaw in Linz's /presentation/ of the proof he should just send an erratum note to Linz, and hopefully Linz would thank him in some way, and correct it in the next edition of his book. That's not what PO wants or claims.
Mike.
Re: Refutation of Turing’s 1936 Halting Problem Proof Based on Self-Referential Conflation as a Category (Type) Error
Re: Refutation of Turing’s 1936 Halting Problem Proof Based on Self-Referential Conflation as a Category (Type) Error
