Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: "Fred. Zwarts" Newsgroups: comp.theory Subject: Re: Correcting the definition of the halting problem --- Computable functions Date: Tue, 25 Mar 2025 10:13:25 +0100 Organization: A noiseless patient Spider Lines: 75 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: Tue, 25 Mar 2025 10:13:25 +0100 (CET) Injection-Info: dont-email.me; posting-host="6b3cf09831cef1bf798d729835c81b21"; logging-data="3094849"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18lpsVCdMgG9TmHiWlFhC1m" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:QHpacisajFzzPTvCmUOnWwYaZp4= In-Reply-To: Content-Language: nl, en-GB Bytes: 4777 Op 24.mrt.2025 om 21:11 schreef olcott: > 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. > >> >> 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 because computable > functions cannot possibly have directly executing Turing > machines as their inputs. > > So we agree that the answer on the question: 'Is there an algorithm that can determine for all possible inputs whether the input specifies a program that (according to the semantics of the machine language) halts when directly executed?' is 'no'. Correct?