Deutsch English Français Italiano |
<vruhf1$3hle3$4@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: dbush <dbush.mobile@gmail.com> Newsgroups: comp.theory Subject: Re: Correcting the definition of the halting problem --- Computable functions Date: Tue, 25 Mar 2025 11:17:53 -0400 Organization: A noiseless patient Spider Lines: 84 Message-ID: <vruhf1$3hle3$4@dont-email.me> References: <vr1shq$1qopn$1@dont-email.me> <vrn237$im1e$1@dont-email.me> <vrn67b$md49$1@dont-email.me> <cb974817db8e02049daa5604d725300154e33ad1@i2pn2.org> <vrps14$35a4m$2@dont-email.me> <eab11e8806c669d296bff986870bdc6abdbb2fef@i2pn2.org> <vrqicu$3s258$1@dont-email.me> <30c2beae6c191f2502e93972a69c85ff227bfd03@i2pn2.org> <vrrs79$11a56$7@dont-email.me> <vrrsta$tdm5$1@dont-email.me> <vrs264$1a43i$1@dont-email.me> <vrs54q$1d1o2$1@dont-email.me> <vrse90$1jr8u$1@dont-email.me> <vrsk13$1q39o$1@dont-email.me> <vrsn62$1rblu$2@dont-email.me> <vrsnhu$1q39o$2@dont-email.me> <vrsodl$1rblu$3@dont-email.me> <vrsogj$1q39o$3@dont-email.me> <vrsqlq$1rblu$4@dont-email.me> <vrsrmr$1q39o$4@dont-email.me> <vrt14i$264jb$1@dont-email.me> <vrt1tu$257a2$1@dont-email.me> <vrt357$264jb$2@dont-email.me> <vrt6va$22073$1@dont-email.me> <vrt7u2$2au0q$1@dont-email.me> <vrufj5$3hle3$1@dont-email.me> <vrug1b$3gia2$5@dont-email.me> <vrugj2$3hle3$3@dont-email.me> <vruh6d$3j3me$2@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 25 Mar 2025 16:17:53 +0100 (CET) Injection-Info: dont-email.me; posting-host="558cb3f1e92ebc1bf3f45b6c0d288267"; logging-data="3724739"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+drcPVF5v2t5y0HjrhbTGT" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:6UsEqdJ8Jsi1yTUkvE2t4hueMFI= In-Reply-To: <vruh6d$3j3me$2@dont-email.me> Content-Language: en-US Bytes: 5454 On 3/25/2025 11:13 AM, olcott wrote: > On 3/25/2025 10:02 AM, dbush wrote: >> On 3/25/2025 10:53 AM, olcott wrote: >>> On 3/25/2025 9:45 AM, dbush wrote: >>>> On 3/24/2025 11:29 PM, olcott wrote: >>>>> On 3/24/2025 10:12 PM, dbush wrote: >>>>>> On 3/24/2025 10:07 PM, olcott wrote: >>>>>>> On 3/24/2025 8:46 PM, André G. Isaak wrote: >>>>>>>> On 2025-03-24 19:33, olcott wrote: >>>>>>>>> On 3/24/2025 7:00 PM, André G. Isaak wrote: >>>>>>>> >>>>>>>>>> In the post you were responding to I pointed out that >>>>>>>>>> computable functions are mathematical objects. >>>>>>>>> >>>>>>>>> https://en.wikipedia.org/wiki/Computable_function >>>>>>>>> >>>>>>>>> Computable functions implemented using models of computation >>>>>>>>> would seem to be more concrete than pure math functions. >>>>>>>> >>>>>>>> Those are called computations or algorithms, not computable >>>>>>>> functions. >>>>>>>> >>>>>>> >>>>>>> https://en.wikipedia.org/wiki/Pure_function >>>>>>> Is another way to look at computable functions implemented >>>>>>> by some concrete model of computation. >>>>>>> >>>>>> >>>>>> And not all mathematical functions are computable, such as the >>>>>> halting function. >>>>>> >>>>>>>> The halting problems asks whether there *is* an algorithm which >>>>>>>> can compute the halting function, but the halting function >>>>>>>> itself is a purely mathematical object which exists prior to, >>>>>>>> and independent of, any such algorithm (if one existed). >>>>>>>> >>>>>>> >>>>>>> None-the-less it only has specific elements of its domain >>>>>>> as its entire basis. For Turing machines this always means >>>>>>> a finite string that (for example) encodes a specific >>>>>>> sequence of moves. >>>>>> >>>>>> False. *All* turing machine are the domain of the halting >>>>>> function, and the existence of UTMs show that all turning machines >>>>>> can be described by a finite string. >>>>>> >>>>> >>>>> You just aren't paying enough attention. Turing machines >>>>> are never in the domain of any computable function. >>>>> <snip> >>>>> >>>> >>>> False. The mathematical function that counts the number of >>>> instructions in a turing machine is computable. >>>> >>> >>> It is impossible for an actual Turing machine to >>> be input to any other TM. >>> >> >> But a description of a turing machine can be, for example in the form >> of source code or a binary. And a turing machine by definition >> *always* behaves the same for a given input when executing directly. > > IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION ALWAYS > SPECIFIES > BEHAVIOR IDENTICAL TO THE DIRECTLY EXECUTED MACHINE. > > _III() > [00002172] 55 push ebp ; housekeeping > [00002173] 8bec mov ebp,esp ; housekeeping > [00002175] 6872210000 push 00002172 ; push III > [0000217a] e853f4ffff call 000015d2 ; call EEE(III) > [0000217f] 83c404 add esp,+04 > [00002182] 5d pop ebp > [00002183] c3 ret > Size in bytes:(0018) [00002183] That is not the complete description. The complete description consists of the code of III, the code of EEE, and the code of everything that EEE calls down to the OS level. *THAT* is the input finite string. If you disagree, explain why. Failure to do so in your next message will be taken as your on-the-record agreement that the above is correct.