Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Turing Machine computable functions apply finite string transformations to inputs +++ Date: Mon, 28 Apr 2025 16:09:08 -0400 Organization: A noiseless patient Spider Lines: 139 Message-ID: References:

<4818688e0354f32267e3a5f3c60846ae7956bed2@i2pn2.org>

<65dddfad4c862e6593392eaf27876759b1ed0e69@i2pn2.org>

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 28 Apr 2025 22:09:07 +0200 (CEST) Injection-Info: dont-email.me; posting-host="67af223ffcc413f8c29b457017b45374"; logging-data="3585230"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19spwY+/9mLDiem1+SW/GXM" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:K9FWE5OGzh0jLaqz7Nm06gyhdcM= Content-Language: en-US In-Reply-To: Bytes: 7194 On 4/28/2025 4:03 PM, olcott wrote: > On 4/28/2025 2:58 PM, dbush wrote: >> On 4/28/2025 3:45 PM, olcott wrote: >>> On 4/28/2025 2:07 PM, dbush wrote: >>>> On 4/28/2025 2:58 PM, olcott wrote: >>>>> On 4/28/2025 1:46 PM, dbush wrote: >>>>>> On 4/28/2025 2:30 PM, 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. >>>>>>> >>>>>> >>>>>> >>>>>> And no turing machine exists that can derive the following mapping >>>>>> (i.e. the mapping is not a computable function), as proven by Linz >>>>>> and others: >>>>>> >>>>> >>>>> Because the theory of computation was never previously >>>>> elaborated to make it clear that Turing computable >>>>> functions are required to derive their output by applying >>>>> finite string transformations to their input finite strings. >>>>> >>>> >>>> And no such algorithm can derive this mapping: >>>> >>>> (,Y) maps to 1 if and only if X(Y) halts when executed directly >>>> (,Y) maps to 0 if and only if X(Y) does not halt when executed >>>> directly >>>> >>>> >>>>> *When we do this then a mapping suddenly appears* >>>> >>>> And that mapping is not the halting mapping, therefore the algorithm >>>> is not a halt decider. >>>> >>>>> DD emulated by HHH according to the finite string >>>>> transformation rules of the x86 language DOES NOT HALT. >>>> >>>> In other words, HHH doesn't map the halting function. >>>> >>>>> >>>>> *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 >>>> >>>> And the halting function is not a computable function: >>>> >>> >>> Maybe you have ADD like Richard and can only >>> pay attention to a point when it is repeated many times >>> >>> I just proved that your halting function is incorrect. >>> >> >> Category error. The halting function below is fully defined, and this >> mapping is not computable *as you have explicitly admitted*. >> > > Neither is the square root of an actual onion computable. Category error. There is no correct answer to "the square root of an onion", but there is a correct answer to whether any arbitrary algorithm X with input Y will halt when executed directly. It's just that there's no algorithm that can tell us that, as Linz show and you have *explicitly* agreed is correct. > > Turing Computable Functions i.e. mathematical mappings for which an algorithm exists which can compute them. > are required to apply finite > string transformations to their inputs. Category error. Mathematical mappings don't have behavior. They are simply pairings from an input domain to an output domain. > The function defined > below ignores that requirement PROVING THAT IT IS INCORRECT. Category error, as mathematical mappings don't have behavior. > >> >> Given any algorithm (i.e. a fixed immutable sequence of instructions) >> X described as with input Y: >> >> (,Y) maps to 1 if and only if X(Y) halts when executed directly >> (,Y) maps to 0 if and only if X(Y) does not halt when executed >> directly >> >> >> > >