Warning: mysqli::__construct(): (HY000/1203): User howardkn already has more than 'max_user_connections' active connections in D:\Inetpub\vhosts\howardknight.net\al.howardknight.net\includes\artfuncs.php on line 21
Failed to connect to MySQL: (1203) User howardkn already has more than 'max_user_connections' active connectionsPath: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory Subject: Re: Turing Machine computable functions apply finite string transformations to inputs Date: Tue, 6 May 2025 22:22:21 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <11708e0b9aa41a925fb73343f4752fb15087ceee@i2pn2.org> 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: Wed, 7 May 2025 02:26:20 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="3455903"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird X-Spam-Checker-Version: SpamAssassin 4.0.0 Content-Language: en-US In-Reply-To: On 5/6/25 11:03 AM, olcott wrote: > 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]. > > The problem is HHH doesn't do that, and you are caught in a lie. DD emulated by a correct emulator according to those rules DOES halt, as your HHH(DD) returns 0.