Deutsch English Français Italiano |
<vs09ib$188ig$1@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: Mikko <mikko.levanto@iki.fi> Newsgroups: comp.theory Subject: Re: Correcting the definition of the halting problem --- Computable functions Date: Wed, 26 Mar 2025 09:15:23 +0200 Organization: - Lines: 67 Message-ID: <vs09ib$188ig$1@dont-email.me> References: <vr1shq$1qopn$1@dont-email.me> <vrkdij$25f9f$3@dont-email.me> <vrlt36$3haib$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> <vrtska$30tvk$1@dont-email.me> <vrufq8$3gia2$4@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Wed, 26 Mar 2025 08:15:24 +0100 (CET) Injection-Info: dont-email.me; posting-host="f5d176a35312dcf4617a2b35e821f8a8"; logging-data="1319504"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18B+JitiVzWJXCZcKmahGa+" User-Agent: Unison/2.2 Cancel-Lock: sha1:Q0b6l2nRU08wszkI29XboUHniU4= Bytes: 4463 On 2025-03-25 14:49:44 +0000, olcott said: > On 3/25/2025 4:22 AM, Mikko wrote: >> On 2025-03-25 03:29:06 +0000, olcott said: >> >>> 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> >> >> There are computable functions that take Turing machines as arguments. >> For example, the number of states of a Turing machine. >> >> The computability of a function requires that the domain can be mapped >> to finite strings. > > IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION SPECIFIES > BEHAVIOR IDENTICAL TO THE DIRECTLY EXECUTED MACHINE. Nothing counter-factual there. From the meanings of the words follows that a machine description does not specify any other behaviour than the behaviour of the directly executed machine. A specification of any other behaviour is not a part of the description of the machine. -- Mikko