Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@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 12:49:17 -0400
Organization: A noiseless patient Spider
Lines: 295
Message-ID: <vv85qc$2cska$1@dont-email.me>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <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>
 <vv81sl$29nkb$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 04 May 2025 18:49:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="766bf062aa37d03efbb568a26a566bf9";
	logging-data="2519690"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/8aDdJtw5duZBM2Dyz4kbM"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:kCr2aH19Jjcy9Y8NHsWqYdUJiVw=
In-Reply-To: <vv81sl$29nkb$1@dont-email.me>
Content-Language: en-US

On 5/4/2025 11:42 AM, olcott wrote:
> 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 ==========