Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse 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: <65dddfad4c862e6593392eaf27876759b1ed0e69@i2pn2.org> 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 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. 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.