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: Mon, 24 Mar 2025 16:18:58 -0400 Organization: A noiseless patient Spider Lines: 95 Message-ID: References: <30c2beae6c191f2502e93972a69c85ff227bfd03@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Mon, 24 Mar 2025 21:18:57 +0100 (CET) Injection-Info: dont-email.me; posting-host="2bba31d9db6d1ce3dfa332732cba05ab"; logging-data="1476354"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18L8D+QC+NUy09E8gKbO256" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:J7fGqNP4RwJXE1MOufJo00hQXmU= In-Reply-To: Content-Language: en-US On 3/24/2025 4:11 PM, olcott wrote: > On 3/24/2025 12:35 PM, dbush wrote: >> On 3/24/2025 12:44 PM, olcott wrote: >>> On 3/24/2025 10:14 AM, dbush wrote: >>>> On 3/24/2025 11:03 AM, olcott wrote: >>>>> On 3/24/2025 6:23 AM, Richard Damon wrote: >>>>>> On 3/23/25 11:09 PM, olcott wrote: >>>>>>> It is impossible for HHH compute the function from the direct >>>>>>> execution of DDD because DDD is not the finite string input >>>>>>> basis from which all computations must begin. >>>>>>> https://en.wikipedia.org/wiki/Computable_function >>>>>> >>>>>> WHy isn't DDD made into the correct finite string?i >>>>>> >>>>> >>>>> DDD is a semantically and syntactically correct finite >>>>> stirng of the x86 machine language. >>>> >>>> Which includes the machine code of DDD, the machine code of HHH, and >>>> the machine code of everything it calls down to the OS level. >>>> >>>>> >>>>>> That seems to be your own fault. >>>>>> >>>>>> The problem has always been that you want to use the wrong string >>>>>> for DDD by excluding the code for HHH from it. >>>>>> >>>>> >>>>> DDD emulated by HHH directly causes recursive emulation >>>>> because it calls HHH(DDD) to emulate itself again. HHH >>>>> complies until HHH determines that this cycle cannot >>>>> possibly reach the final halt state of DDD. >>>>> >>>> >>>> Which is another way of saying that HHH can't determine that DDD >>>> halts when executed directly. >>>> >>> >>> given an input of the function domain it can >>> return the corresponding output. >>> https://en.wikipedia.org/wiki/Computable_function >>> >>> Computable functions are only allowed to compute the >>> mapping from their input finite strings to an output. >>> >> >> >> The HHH you implemented is computing *a* computable function, but it's >> not computing the halting function: >> > > The whole point of this post is to prove that > no Turing machine ever reports on the behavior > of the direct execution of another Turing machine. > Sure it can. Any that takes a description of a turning machine that halt when executed directly is correct to return 1, regardless of the logic used to do so. >> >> 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 > > Cannot possibly be a computable function In other words, you explicitly agree with the Linz proof that the halting function is not a computable function, i.e. no algorithm H can compute it. > because computable > functions cannot possibly have directly executing Turing > machines as their inputs. But any mathematical function, computable or not, can take a description of that turning machine that specifies the exact behavior when executed directly, for example source code or binaries. And any turning machine / algorithm by definition gives the exact same results for the same input when executed directly. > > >> (,Y) maps to 0 if and only if X(Y) does not halt when executed >> directly >> >> >