Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Functions computed by Turing Machines MUST apply finite string
 transformations to inputs
Date: Fri, 2 May 2025 06:06:11 +0100
Organization: Fix this later
Lines: 86
Message-ID: <vv1js4$d4ik$1@dont-email.me>
References: <TuuNP.2706011$nb1.2053729@fx01.ams4>
 <87cyd5182l.fsf@nosuchdomain.example.com> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 02 May 2025 07:06:18 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3a1c0b2ab3dc637eeb67dc4cd879a061";
	logging-data="430676"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+lHOp5gX+r12hjedkzSU/NRn6xTT7HX9uqG5qTjxezwg=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:kbUd59RKZIMYc9QZAhZrQNwrC1w=
Content-Language: en-GB
In-Reply-To: <vv1gfu$3ra6l$8@dont-email.me>

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?

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').

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).

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.

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. 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.

<snip>

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within