Deutsch English Français Italiano |
<vutsig$tpnd$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Richard Heathfield <rjh@cpax.org.uk> Newsgroups: comp.theory Subject: Re: Turing Machine computable functions apply finite string transformations to inputs VERIFIED FACT Date: Wed, 30 Apr 2025 20:10:06 +0100 Organization: Fix this later Lines: 61 Message-ID: <vutsig$tpnd$1@dont-email.me> References: <vu6lnf$39fls$2@dont-email.me> <vugddv$b21g$2@dont-email.me> <0a2eeee6cb4b6a737f6391c963386745a09c8a01@i2pn2.org> <vugvr3$pke9$8@dont-email.me> <4818688e0354f32267e3a5f3c60846ae7956bed2@i2pn2.org> <vuj18i$2lf64$6@dont-email.me> <f0d3f2e87d9a4e0b0f445f60a33d529f41a4fcf7@i2pn2.org> <vuj55m$2lf64$10@dont-email.me> <vuj8h3$2uahf$3@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> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Wed, 30 Apr 2025 21:10:08 +0200 (CEST) Injection-Info: dont-email.me; posting-host="37e133e97ee7719e4a93228f44d9117b"; logging-data="976621"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18cvVTyT04+Eef+zuNHQkhP7kRtQ8BqKFyyzjHIhvypmQ==" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:k2lxi6aM4QnV1y/8lUt3yTWsIUc= In-Reply-To: <ab48c34e4d8c04dadc62a6c70f0ef48e1a8bbaba@i2pn2.org> Content-Language: en-GB Bytes: 4626 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. U(V,V) cannot correctly resolve this paradox to give a correct report. It is this contradiction that demonstrates that some functions are incomputable. Note the nature of the contradiction. We assumed the existence of a perfect U and deduced from it a program that U cannot correctly decide upon. That is, no universal decider can exist. To overturn the proof would require the construction of a perfect U. (Don't hold your breath.) <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