Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
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: <vv81sl$29nkb$1@dont-email.me>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <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>
 <vv5e46$3rtqo$1@dont-email.me>
 <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:
>>>>
>>>> <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.
>>>
>>
>> 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 ==========