Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Correcting the definition of the halting problem --- Computable functions ---HHH(DD) Date: Tue, 25 Mar 2025 12:18:07 -0500 Organization: A noiseless patient Spider Lines: 125 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:18:10 +0100 (CET) Injection-Info: dont-email.me; posting-host="28b8eab6d237e557af892b2ab104f6c1"; logging-data="3907206"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19MtsRSFXtGpmvZQNvypUNk" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:WNU5B5Z5Obg8r7duN3UQIljbWss= X-Antivirus: Norton (VPS 250325-18, 3/25/2025), Outbound message In-Reply-To: X-Antivirus-Status: Clean Content-Language: en-US Bytes: 7027 On 3/25/2025 12:04 PM, dbush wrote: > 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. > When the question is: Does III emulated by EEE reach its final halt state when III defines a pathological relationship with its emulator? This relevant because DD emulated by HHH is isomorphic to III emulated by HHH. int DD() { int Halt_Status = HHH(DD); if (Halt_Status) HERE: goto HERE; return Halt_Status; } Then the question becomes does the DD input to HHH specify behavior that reaches the final halt state of DD? Here the program-under-test is what is examined and the test program's behavior is irrelevant. -- Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer