Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Richard Heathfield Newsgroups: comp.theory Subject: Re: Turing Machine computable functions apply finite string transformations to inputs VERIFIED FACT Date: Tue, 29 Apr 2025 08:10:17 +0100 Organization: Fix this later Lines: 147 Message-ID: References:

<0a2eeee6cb4b6a737f6391c963386745a09c8a01@i2pn2.org> <4818688e0354f32267e3a5f3c60846ae7956bed2@i2pn2.org>

<65dddfad4c862e6593392eaf27876759b1ed0e69@i2pn2.org>

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Tue, 29 Apr 2025 09:10:19 +0200 (CEST) Injection-Info: dont-email.me; posting-host="a99ce2d194518084f1e3236eb6fd133d"; logging-data="1343340"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19aEeie/UCiqOC4LgYnV7xrYGPxclcu7EXiqR0ktaKDJw==" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:oBNrV+GfDNeTOHYdb/j4EqXU7jc= Content-Language: en-GB In-Reply-To: Bytes: 7951 On 29/04/2025 03:50, olcott wrote: > On 4/28/2025 3:13 PM, Richard Heathfield wrote: >> On 28/04/2025 19:30, olcott wrote: >>> On 4/28/2025 11:38 AM, Richard Heathfield wrote: >>>> On 28/04/2025 16:01, olcott wrote: >>>>> On 4/28/2025 2:33 AM, Richard Heathfield wrote: >>>>>> On 28/04/2025 07:46, Fred. Zwarts wrote: >>>>>> >>>>>> >>>>>> >>>>>>> So we agree that no algorithm exists that can determine >>>>>>> for all possible inputs whether the input specifies a >>>>>>> program that (according to the semantics of the machine >>>>>>> language) halts when directly executed. >>>>>>> Correct? >>>>>> >>>>>> Correct. We can, however, construct such an algorithm just >>>>>> as long as we can ignore any input we don't like the look of. >>>>>> >>>>> >>>>> The behavior of the direct execution of DD cannot be derived >>>>> by applying the finite string transformation rules specified >>>>> by the x86 language to the input to HHH(DD). This proves that >>>>> this is the wrong behavior to measure. >>>>> >>>>> It is the behavior THAT IS derived by applying the finite >>>>> string transformation rules specified by the x86 language >>>>> to the input to HHH(DD) proves that THE EMULATED DD NEVER >>>>> HALTS. >>>> >>>> The x86 language is neither here nor there. >>> >>> Computable functions are the formalized analogue >>> of the intuitive notion of algorithms, in the sense >>> that a function is computable if there exists an >>> algorithm that can do the job of the function, i.e. >>> *given an input of the function domain it* >>> *can return the corresponding output* >>> https://en.wikipedia.org/wiki/Computable_function >>> >>> *Outputs must correspond to inputs* >>> >>> *This stipulates how outputs must be derived* >>> Every Turing Machine computable function is >>> only allowed to derive outputs by applying >>> finite string transformation rules to its inputs. >> >> In your reply to my article, you forgot to address what I >> actually wrote. I'm not sure you understand what 'reply' means. >> >> Still, I'm prepared to give you another crack at it. Here's >> what I wrote before: >> >> 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. Nothing /has/ to be measured. P's behaviour (halts, doesn't halt) when given D as input must be /established/. If you can do that by measuring the tape, great! But if you can do it by parsing the program's symbols and analysing the parse tree, that's great too. /How/ you do it doesn't matter as long as you express it as a Turing Machine that can handle any P and any D and produce a result of either 'halts' or 'doesn't halt'. > 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. Computer science is way ahead of you, as the proof long pre-dates the x86 chip family. > Even calling the Turing Machine language the Turing > Machine description language make this confusing. I've never called it that. > *This is a verified fact* > When DD is emulated by HHH according to the finite > string transformation rules of the x86 language > DD cannot possibly reach its own final state no > matter what HHH does. Your claim is that DD never halts? Fine. You could have proved that by rewriting DD to have a while(1); at the end of main().. >> Whatever you think you've proved, you haven't solved the >> Halting Problem. There are *no* solutions. We know this because >> there is a simple well-known proof. So the only way to devise a >> solution is to re- define the problem. > > It ultimately is only a confused view because key > details about how outputs are made to conform to > inputs: How outputs are made to conform to inputs is neither here nor there. What matters is whether incomputable functions exist. When you wrote this: "Computing the actual behavior the direct execution of any input is ALWAYS IMPOSSIBLE" you conceded the point by admitting the existence of computations that cannot be performed. > You aren't paying enough attention because you > are too sure that I am wrong. I proved my point > above. Word salad is not a proof. You can talk till you're blue in the face, but you can't (correctly) prove that 2 + 2 = 5. Yes, I'm sure you're wrong. So are you, it seems. Turing's proof proved that incomputable functions exist. "Computing the actual behavior the direct execution of any input is ALWAYS IMPOSSIBLE" concedes the point by admitting the existence of computations that cannot be performed. Now, let me paint that in some more. Turing's proof is about as rigorous as Pythagoras, and it is difficult to imagine any way in which a flaw could have lasted through 90-odd years of computer science, but I suppose we must accept that it took us 300+ years to confirm FLT, so it's /not/ inconceivable that one day someone might show a minor error in the proof. What /is/ inconceivable, however, is that Turing's conclusion - 'not all functions are computable' - is flawed. You yourself conceded the point when you wrote: "Computing the actual behavior the direct execution of any input is ALWAYS IMPOSSIBLE." If there is anything to overturn it's his conclusion, but you have already accepted the conclusion. Game over. -- 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