Path: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: The philosophy of computation reformulates existing ideas on a new basis Date: Mon, 11 Nov 2024 13:06:46 +0200 Organization: - Lines: 129 Message-ID: References: <086fc32f14bcc004466d3128b0fe585b27377399@i2pn2.org> <11408789ed30027f4bc9a743f353dfa9b4712109@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 11 Nov 2024 12:06:46 +0100 (CET) Injection-Info: dont-email.me; posting-host="88f660726df1b76a05d2b3eb8bbe5a8c"; logging-data="1014043"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+2tOzTaR7PAVBHsS2iyceb" User-Agent: Unison/2.2 Cancel-Lock: sha1:xS+TS9XpXW7GRaS6u99fzvjzcTU= Bytes: 6942 On 2024-11-09 14:56:14 +0000, olcott said: > On 11/9/2024 3:53 AM, Mikko wrote: >> On 2024-11-08 14:39:20 +0000, olcott said: >> >>> On 11/8/2024 6:39 AM, Mikko wrote: >>>> On 2024-11-07 16:39:57 +0000, olcott said: >>>> >>>>> On 11/7/2024 3:56 AM, Mikko wrote: >>>>>> On 2024-11-06 15:26:06 +0000, olcott said: >>>>>> >>>>>>> On 11/6/2024 8:39 AM, Mikko wrote: >>>>>>>> On 2024-11-05 13:18:43 +0000, olcott said: >>>>>>>> >>>>>>>>> On 11/5/2024 3:01 AM, Mikko wrote: >>>>>>>>>> On 2024-11-03 15:13:56 +0000, olcott said: >>>>>>>>>> >>>>>>>>>>> On 11/3/2024 7:04 AM, Mikko wrote: >>>>>>>>>>>> On 2024-11-02 12:24:29 +0000, olcott said: >>>>>>>>>>>> >>>>>>>>>>>>> HHH does compute the mapping from its input DDD >>>>>>>>>>>>> to the actual behavior that DDD specifies and this >>>>>>>>>>>>> DOES INCLUDE HHH emulating itself emulating DDD. >>>>>>>>>>>> >>>>>>>>>>>> Yes but not the particular mapping required by the halting problem. >>>>>>>>>>> >>>>>>>>>>> Yes it is the particular mapping required by the halting problem. >>>>>>>>>>> The exact same process occurs in the Linz proof. >>>>>>>>>> >>>>>>>>>> The halting probelm requires that every halt decider terminates. >>>>>>>>>> If HHH(DDD) terminates so does DDD. The halting problmen requires >>>>>>>>>> that if DDD terminates then HHH(DDD) accepts as halting. >>>>>>>>> >>>>>>>>> void Infinite_Loop() >>>>>>>>> { >>>>>>>>>    HERE: goto HERE; >>>>>>>>>    return; >>>>>>>>> } >>>>>>>>> >>>>>>>>> No that is false. >>>>>>>>> The measure is whether a C function can possibly >>>>>>>>> reach its "return" instruction final state. >>>>>>>> >>>>>>>> Not in the original problem but the question whether a particular strictly >>>>>>>> C function will ever reach its return instruction is equally hard. About >>>>>>> >>>>>>> It has always been about whether or not a finite string input >>>>>>> specifies a computation that reaches its final state. >>>>>> >>>>>> Not really. The original problem was not a halting problem but Turing's >>>>> >>>>> Exactly. The actual Halting Problem was called that by Davis >>>>> in 1952. Not the same as Turing proof. >>>> >>>> In early times there was variation in how things were presented and what >>>> words were used. Post had studied the halting problem of his tag system >>>> much earlier but didn't call it a machine. Many other problems were also >>>> studied and later found to be more or less related to the halting >>>> problem and its variants. >>>> >>>>> *So we are back to The Halting Problem itself* >>>>> >>>>> has always been about whether or not a finite string input >>>>> specifies a computation that reaches its final state. >>>> >>>> No, it has been a collection of related problems that includes that >>>> particular one. >>> >>> The halting problem has always been abuut halting >> >> Nevertheless Turing's solution to his circularity problem is usually >> regarded as the first solution to the halting problem. >> >>>> As the problems are related and equally hard it does >>>> not really matter which one you choose as long as you are clear >>>> about your choice. To argue about the meaning of words id a clear >>>> indcation of an intent to avoid an honest discussion. >> >>> It is not the meaning of words it is the semantic >>> property of the finite string pair HHH/DDD. >> >> Above you have argued about the meanings of the words and >> keep doing so below. > > It is the meaning of the bytes of x86 code and > bytes of code are not words. No, nothing you have said tells anuything about meanings of the bytes of x86 code. (A pair of such bytes is sometimes called a "word"). You were just arguing about the meanings the verb "halt" and other words. >>> The halting problem has always been about whether a finite >>> string input specifies a computation that will reach its >>> final halt state. >>> >>> If you disagree then you must provide a complete and coherent >>> counter-example conclusively proving otherwise not merely >>> some vague reference to some other things somewhere else. >> >> From https://www.tutorialspoint.com/automata_theory/ >> turing_machine_halting_problem.htm >> >>> Turing Machine Halting Problem >>> Input − A Turing machine and an input string w. >>> Problem − Does the Turing machine finish computing of the string w in a >>> finite number of steps? The answer must be either yes or no. > > The computation specified by the finite string DDD > emulated by HHH cannot possibly reach its "return" > instruction final halt state. It can and does if HHH is a decider and otherwise does not matter. > The computation specified by the finite string DDD > emulated by HHH1 IS NOT THE ACTUAL INPUT TO HHH. HHH1 can take same inputs as HHH. These inputs specify some behaviour. What they do with this input may differ. > HHH must compute the mapping FROM ITS INPUT TO THE > BEHAVIOR THAT THIS INPUT SPECIFIES. Not to full behaviour but to one feature of that behaviour. Doesn't HHH1 need to? -- Mikko