Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Correcting the definition of the halting problem --- Computable functions Date: Tue, 25 Mar 2025 13:04:10 -0400 Organization: A noiseless patient Spider Lines: 112 Message-ID: References: <30c2beae6c191f2502e93972a69c85ff227bfd03@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 25 Mar 2025 18:04:10 +0100 (CET) Injection-Info: dont-email.me; posting-host="558cb3f1e92ebc1bf3f45b6c0d288267"; logging-data="3724739"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/hjAY39jiKvZwP2nBdTI3s" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:CFzCg48N1RUN6Zk2aeDZcq1lHyE= Content-Language: en-US In-Reply-To: On 3/25/2025 12:56 PM, olcott wrote: > On 3/25/2025 11:46 AM, dbush wrote: >> On 3/25/2025 12:40 PM, olcott wrote: >>> On 3/25/2025 10:17 AM, dbush wrote: >>>> 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. >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> 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 >>> >>> and the fact that EEE >> >> Is called by III makes the code of EEE part of the fixed input, as >> well as everything that EEE calls down to the OS level. >> > > Which is not relevant to whether or not III emulated > by EEE reaches its own final halt state. > Which is why III emulated by EEE is not relevant. Remember, we want to know whether an algorithm exists that can do this: Given any algorithm (i.e. a fixed immutable sequence of instructions) X described as with input Y: A solution to the halting problem is an algorithm H that computes the following 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