Re: Functions computed by Turing Machines MUST apply finite string transformations to inputs --- MT

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

>
In other words if embedded_H was a UTM would cause
Ĥ applied to ⟨Ĥ⟩ to never halt then embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
is correctly ruled to never halt.

>
No, that's all wrong.  You are trying to apply the Sipser quote to justify embedded_H deciding never_halt ?  That's not what the quote says.  From above:
>
 >> 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.
>
And we have
>
(c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩
>
Sipser's H is your embedded_H, and his D is your ⟨Ĥ⟩ ⟨Ĥ⟩, so the correct interpretation is:
>
 >>      if embedded_H is given input ⟨Ĥ⟩ ⟨Ĥ⟩, and while simulating Ĥ gathers enough
 >>      information to deduce that UTM(⟨Ĥ⟩ ⟨Ĥ⟩) would never halt, then
 >>      embedded_H can abort its simulation and decide Ĥ [run with input Ĥ]
 >>      never halts.
>
As explained above, UTM(⟨Ĥ⟩ ⟨Ĥ⟩) simulates Ĥ run with input Ĥ (having the same halting behaviour) and Ĥ run with input Ĥ HALTS.  So embedded_H does not "gather enough information to deduce that UTM(⟨Ĥ⟩ ⟨Ĥ⟩) would never halt".  THAT IS JUST A FANTASY THAT YOU HAVE.
>
UTM(⟨Ĥ⟩ ⟨Ĥ⟩) DOES halt, so embedded_H can't possibly gather information that genuinely implies it DOESN'T halt.  The explanation is obvious: embedded_H gathers information that *YOU* believe implies that UTM(⟨Ĥ⟩ ⟨Ĥ⟩) would never halt, but *YOU ARE SIMPLY WRONG*.
>

  When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy
   or
Ĥ.q0 ⟨Ĥ⟩ ⊢* UTM ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
 If the above wouldn't halt then embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

False, as Ĥ contains a copy of embedded_H, not UTM

 

I know you'll not understand what I've just said,

 My understanding is provably deeper than yours.
A halt decider / termination analyzer must

By definition, map the halting function:
Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as <X> with input Y:
A solution to the halting problem is an algorithm H that computes the following mapping:
(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly
  apply

finite string transformation rules TO ITS INPUT
to derive its OUTPUT.
 Ĥ  Is NOT an input to embedded_H
⟨Ĥ⟩ IS an input to embedded_H
 When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
   or
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
 ⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by embedded_H cannot
possibly reach its own final state ⟨Ĥ.qn⟩ no
matter what embedded_H does.
 Even though many theory of computation authors have
stated that halt deciders must report on the behavior
of the direct execution of their input

Because that is what they're stipulated to do.

 THEY NEVER NOTICED THAT THE BEHAVIOR THAT IS ACTUALLY
SPECIFIED BY THIS INPUT IS SOMETIMES NOT THE SAME AS
THE BEHAVIOR OF THE DIRECT EXECUTION.

In other words, if you assume a halt decider exists, you reach a contradiction.  This proves the assumption that a halt decider exists is false, as proven by Linz and other and as you have *explicitly* agreed with.

 THE PATHOLOGICAL RELATIONSHIP BETWEEN DD AND HHH CANNOT BE IGNORED
THE PATHOLOGICAL RELATIONSHIP BETWEEN DD AND HHH CANNOT BE IGNORED
THE PATHOLOGICAL RELATIONSHIP BETWEEN DD AND HHH CANNOT BE IGNORED

Which means we can't ignore that HHH(DD) will return 0 and cause DD to halt when executed directly.

BECAUSE IT DOES CHANGE THE  BEHAVIOR OF DD

Only if you change the input, as you're doing.

 int sum(int x, int y) { return x + y; }
when we expect sum(2,3) to return the sum of 5 + 6 WE ARE WRONG!

Not when we want an algorithm that computes (x+3) + (y+3)

When we expect HHH(DD) to examine the behavior of the directly
executed DD(DD) WE ARE WRONG.

Not when we want an algorithm that will tell us if DD will halt when executed directly

 Functions computed by Turing Machines compute the mapping
FROM INPUTS TO OUTPUTS via finite string transformation rules.
 

And the halting function is not such a function, as proven by Linz and other and as you have *explictly* agreed is correct.