Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben@bsb.me.uk>
Newsgroups: comp.theory
Subject: Re: Turing Machine computable functions apply finite string transformations to inputs VERIFIED FACT
Date: Thu, 01 May 2025 01:53:15 +0100
Organization: A noiseless patient Spider
Lines: 77
Message-ID: <87tt65gnic.fsf@bsb.me.uk>
References: <vu6lnf$39fls$2@dont-email.me> <vujfuu$35hcg$1@dont-email.me>
	<65dddfad4c862e6593392eaf27876759b1ed0e69@i2pn2.org>
	<vujlj0$3a526$1@dont-email.me> <vujln7$32om9$8@dont-email.me>
	<vujmmm$3a526$2@dont-email.me> <vujmrj$32om9$9@dont-email.me>
	<vujtcb$3gsgr$1@dont-email.me> <vuju44$3hnda$1@dont-email.me>
	<vuk47o$3qkbb$1@dont-email.me> <vuk6b6$3l184$1@dont-email.me>
	<vuls34$1bf1j$4@dont-email.me> <vun87k$2m24h$2@dont-email.me>
	<vunb06$2fjjl$5@dont-email.me> <vuo57j$3h5l9$2@dont-email.me>
	<vuoath$3ljma$1@dont-email.me> <vuohgi$3td7u$1@dont-email.me>
	<vuonh6$2g74$2@dont-email.me> <vupeor$qf60$1@dont-email.me>
	<ab48c34e4d8c04dadc62a6c70f0ef48e1a8bbaba@i2pn2.org>
	<vutsig$tpnd$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Thu, 01 May 2025 02:53:18 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="a8099b0826b5d47abfff67a02eab0ba3";
	logging-data="1546817"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18z1+mnCA8O7lwhMPlhtf9MkRQBnht48IU="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:sC+DLqPYqp43ojldR7NbERzzjLQ=
	sha1:5iQDMcjb8kxWHXQ+US6yxDCSlso=
X-BSB-Auth: 1.2f4d90b54329af58bf81.20250501015315BST.87tt65gnic.fsf@bsb.me.uk

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 29/04/2025 11:00, joes wrote:
>> Am Mon, 28 Apr 2025 21:50:03 -0500 schrieb olcott:
>>> On 4/28/2025 3:13 PM, Richard Heathfield wrote:
>> 
>>>> What matters is whether a TM can be constructed that can accept an
>>>> arbitrary TM tape P and an arbitrary input tape D and correctly
>>>> calculate whether, given D as input, P would halt. Turing proved that
>>>> such a TM cannot be constructed.
>>>> This is what we call the Halting Problem.
>>>>
>>> Yet it is H(P,D) and NOT P(D) that must be measured. Computer science
>>> has been wrong about this all of these years. When I provide the 100%
>>> concrete example of the x86 language there is zero vagueness to slip
>>> through the cracks of understanding.
>> No, H gets P(D) as input, not itself. H is the "measurer", not being
>> measured.
>
> Mr Olcott has contradicted you, and even though he's wrong about almost
> everything else I don't think he's wrong about this.
>
> Let's drop HHH and DD and so on, and stick to:
>
> U is a universal termination analysis program, taking two tapes, P and
> D. If P(D) would halt, U(P,D) returns true; else false. No matter what
> program P is, U always reports either true or false, and never makes a
> mistake.
>
> P is an arbitrary (but syntactically correct) program.
>
> If we can write U, it's easy enough to write V, which differs from U only
> in that instead of reporting, V reacts to an unending program by halting
> and to a halting program by looping forever.
>
> Then we make two copies of the V tape and ask V about itself. What would
> U(V, V) tell us?
>
> U (my universal analogue of Mr Olcott's H^3) doesn't get V(V) as its input,
> but V and V. U(V(V)) would suggest that V(V) is executed and the result
> passed to U, but in fact there is no need to execute V if the analysis can
> be performed statically.
>
> Whether it's executed or not, however, the answer is that V(V) halts only
> if it doesn't and loops forever only if it doesn't.

You've added a problem that should not be there. Your U is a two-tape TM
and so therefore is V.  U(P,D) reports on the halting of P(D) but U(V,V)
is ill-defined because V(V) is not a two-tape computation.  Even P(D) is
not well-formed because what does it mean to apply a tape to a tape?
(Yes, I know P(D) means the execution of the TM encoded on the tape P
when run on tape D but this should be spelled out.)

The proof is simpler to get right if all the models are the same: U is a
one-tape TM decider of one-tape computations.  And we should clearly
distinguish between TMs, encodings of TMs and encodings of TM/data
pairs.  Many years ago I urged PO is use a notation such as:

  P     A Turing machine with some alphabet Sigma.
  P(i)  The computation that results from P running with initial tape i.
  [P]   the encoding of a TM in the alphabet Sigma.
  <x,y> the encoding of a pair of strings over Sigma using only symbols
        in Sigma.

A halt decider, H, would then be a TM (over Sigma) that accepts all
inputs of the form <[P],d> where P(d) halts and that rejects all other
inputs.

But then PO never really understood TMs and soon ditched them altogether
in favour of a model of computation that, ironically, has decidable
halting!  Mind you, despite his IO-free x86 model having decidable
halting, he has not demonstrated halt decider for it.  (Aside: I don't
mean that a halt decider is possible in the model, just that halting in
his model is TM-decidable.)

-- 
Ben.