Path: 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 13:57:18 -0500 Organization: A noiseless patient Spider Lines: 187 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 25 Mar 2025 19:57:19 +0100 (CET) Injection-Info: dont-email.me; posting-host="28b8eab6d237e557af892b2ab104f6c1"; logging-data="4106956"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ddsLvhZIOyt4LHr2qBAX2" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:ESZoeggof69s+ZJvl7xvhb1u11g= X-Antivirus-Status: Clean X-Antivirus: Norton (VPS 250325-18, 3/25/2025), Outbound message Content-Language: en-US In-Reply-To: On 3/25/2025 1:37 PM, dbush wrote: > On 3/25/2025 2:27 PM, olcott wrote: >> On 3/25/2025 12:24 PM, dbush wrote: >>> On 3/25/2025 1:18 PM, olcott wrote: >>>> 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? >>>> >>> >>> >>> But that's not the question.  The question is whether or not an H >>> exists that behaves as described below: >>> >> >> Did you ever bother to notice the title of this thread? >> >> Turing machines are only capable operating on input >> finite strings. > > And those finite strings can be a complete description of a turing machine > The input to a Turing machine cannot possibly be the actual behavior of any executing process. A Turing machine can only port on the behavior that a finite string input specifies. >> Turing machine computable functions cannot >> compute anything that their input doesn't specify. > > Translation: algorithms only compute what they're programed to compute. > NO WRONG. Turing machine computable functions cannot compute any mapping from anything that their input DOES NOT SAY. THEIR INPUT CANNOT POSSIBLY SAY THE ACTUAL BEHAVIOR OF ANY EXECUTING PROCESS > And the algorithm your EEE is computing is not the mathematical halting > function, which has proven to not be computable: > When HHH rejects DD as specifying a computation that does not reach its final halt state HHH IS CORRECT. > > 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 > > >> >> THEIR INPUT NEVER SPECIFIES THE ACTUAL BEHAVIOR OF ANY >> OTHER TURING MACHINE ========== REMAINDER OF ARTICLE TRUNCATED ==========