Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Functions computed by Turing Machines MUST apply finite string transformations to inputs --- MT Date: Sun, 4 May 2025 10:42:11 -0500 Organization: A noiseless patient Spider Lines: 255 Message-ID: References:

<991dde3a60e1485815b789520c7149e7842d18f2@i2pn2.org>

<-GOdnZvgEPn-84j1nZ2dnZfqn_SdnZ2d@brightview.co.uk> <2qydnbbWA6CAGIv1nZ2dnZfqn_SdnZ2d@brightview.co.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 04 May 2025 17:42:14 +0200 (CEST) Injection-Info: dont-email.me; posting-host="aea1556d39118926a514fd6c040038a9"; logging-data="2416267"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18eUM0ZIDvhDrsKhuHyWlRH" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:5ipd6XWsFCQP202vyePJtwbSz50= X-Antivirus-Status: Clean Content-Language: en-US In-Reply-To: <2qydnbbWA6CAGIv1nZ2dnZfqn_SdnZ2d@brightview.co.uk> X-Antivirus: Norton (VPS 250504-2, 5/4/2025), Outbound message Bytes: 12316 On 5/3/2025 4:05 PM, Mike Terry wrote: > On 03/05/2025 16:52, olcott wrote: >> On 5/2/2025 8:16 PM, Mike Terry wrote: >>> 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: >>>> >>>> >>>> >>>>>>> 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. >>> >> >> When Ĥ is applied to ⟨Ĥ⟩ >> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ > ..if H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy > >> Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn > ..if H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qn > > Both the above cannot be correct as you wrote them! (You don't > understand the Linz notation, and "no" you haven't "enhanced it" or > whatever you think you've done) > >> >> (a) Ĥ copies its input ⟨Ĥ⟩ >> (b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ >> (c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ >> (d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩ >> (e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ >> (f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ >> (g) goto (d) with one more level of simulation > > But this does not continue indefinitely. You forget that when you say > > (c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ > > embedded_H does not just stop running until the simulation returns. > embedded_H is still running throughout the simulation and is monitoring > progress to decide whether of not to abort. At some point it /does/ > decide to abort, and steps (d)(e)(f)(g) become moot. Truth is they were > always just an explanation for what is happening in (c), and (c) is the > actual TM code running. > > So to continue, (c) aborts at some point, and > > embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn // one of the options you listed above > > Ĥ.qn is a halt state for Ĥ, IN OTHER WORDS When Ĥ is applied to ⟨Ĥ⟩, Ĥ > HALTS.⟩ ========== REMAINDER OF ARTICLE TRUNCATED ==========