Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Turing Machine computable functions apply finite string transformations to inputs Date: Tue, 6 May 2025 10:03:52 -0500 Organization: A noiseless patient Spider Lines: 139 Message-ID: References: <87cyd5182l.fsf@nosuchdomain.example.com> <5YRRP.109778$_Npd.21893@fx01.ams4> <018f45d4807ba7b0092370889153d51d798e112e@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 06 May 2025 17:03:52 +0200 (CEST) Injection-Info: dont-email.me; posting-host="4d3877b25e07ae675aebb853b858fd37"; logging-data="3298612"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/utGBl5+acAVJ/omZHpgJz" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:S2SZv61F4WN3T/VoQxcFG8C+174= X-Antivirus-Status: Clean In-Reply-To: X-Antivirus: Norton (VPS 250506-2, 5/6/2025), Outbound message Content-Language: en-US On 5/6/2025 3:24 AM, Mikko wrote: > On 2025-05-06 02:32:01 +0000, olcott said: > >> On 5/5/2025 8:19 PM, Richard Damon wrote: >>> On 5/4/25 8:35 PM, olcott wrote: >>>> On 5/4/2025 5:34 PM, Mr Flibble wrote: >>>>> On Sun, 04 May 2025 23:30:54 +0100, Richard Heathfield wrote: >>>>> >>>>>> On 04/05/2025 23:15, olcott wrote: >>>>>>> On 5/4/2025 2:21 PM, Richard Heathfield wrote: >>>>>>>> On 04/05/2025 18:55, olcott wrote: >>>>>>>>> Changing my words then rebutting these changed words is dishonest. >>>>>>>>> >>>>>>>>> Functions computed by Turing Machines require INPUTS and produce >>>>>>>>> OUTPUTS DERIVED FROM THESE INPUTS. >>>>>>>> >>>>>>>> Counter-example: a Turing Machine can calculate pi without any >>>>>>>> input >>>>>>>> whatsoever. >>>>>>>> >>>>>>>> As Mikko rightly said: a Turing machine does not need to require an >>>>>>>> input. >>>>>>>> >>>>>>>> >>>>>>> IT IS NOT COMPUTING FUNCTION THEN >>>>>> >>>>>> Quoth Alan Turing: >>>>>> >>>>>> (viii) The limit of a computably convergent sequence is computable. >>>>>> >>>>>>   From (viii) and TT— 4(1—i-|--i—...) we deduce that TT is >>>>>> computable. >>>>>> >>>>>> No input required. >>>>>> >>>>>>> IT IS NOT COMPUTING FUNCTION THEN IT IS NOT COMPUTING FUNCTION >>>>>>> THEN IT >>>>>>> IS NOT COMPUTING FUNCTION THEN >>>>>>> >>>>>>> Computable functions are the basic objects of study in computability >>>>>>> theory. 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 >>>>>> >>>>>> That's a very second-rate summary of computability. Turing was far >>>>>> more >>>>>> interested in whether a computation was possible than whether it >>>>>> needed >>>>>> inputs. Do most computations need inputs? Most useful ones that we >>>>>> care >>>>>> about, sure. But all? By no means. >>>>>> >>>>>>> *Computer science is ONLY concerned with computable functions* >>>>>> >>>>>> Computer science is concerned with the Halting Problem. >>>>>> The Halting Problem is concerned with an incomputable function. >>>>>> Therefore computer science is concerned with at least one >>>>>> incomputable >>>>>> function. >>>>> >>>>> The function is neither computable nor incomputable because there >>>>> is no >>>>> function at all, just a category error. >>>>> >>>>> /Flibble >>>> >>>> You can look at it that way or you can look >>>> at it as simulating termination analyzer HHH(DD) >>>> does correctly determine that DD cannot possibly >>>> reach its own final state, thus is correctly >>>> rejected as non-halting. >>>> >>> >>> Except that isn't the question that is being asked. >>> >>> In fact, that question has a trivial answer, as we can make an H0 >>> that just aborts its emulation and returns 0 and it is correct by >>> your definition, >> >> No that is stupidly wrong as I have said at least 100 times recently. >> The termination analyzer must compute the mapping from the input >> on the basis of the behavior that this input actually specifies. > > You often say so and you often say otherwise. More specifically, you > have said that is correct to call the actual input non-halting if a > hypothetical non-decider would correctly decide that a hypthetical > input would not halt. > If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D *would never stop running unless aborted* then H can abort its simulation of D and correctly report that D specifies a non-halting sequence of configurations. *would never stop running unless aborted* looks at the actual input D and reports on the basis of a hypothetical H/D pair where H does not abort. int DD() { int Halt_Status = HHH(DD); if (Halt_Status) HERE: goto HERE; return Halt_Status; } _DD() [00002133] 55 push ebp ; housekeeping [00002134] 8bec mov ebp,esp ; housekeeping [00002136] 51 push ecx ; make space for local [00002137] 6833210000 push 00002133 ; push DD [0000213c] e882f4ffff call 000015c3 ; call HHH(DD) [00002141] 83c404 add esp,+04 [00002144] 8945fc mov [ebp-04],eax [00002147] 837dfc00 cmp dword [ebp-04],+00 [0000214b] 7402 jz 0000214f [0000214d] ebfe jmp 0000214d [0000214f] 8b45fc mov eax,[ebp-04] [00002152] 8be5 mov esp,ebp [00002154] 5d pop ebp [00002155] c3 ret Size in bytes:(0035) [00002155] DD emulated by HHH according to the rules of the x86 language cannot possibly reach past its own machine address [0000213c]. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer