Date: Sat, 18 Mar 2023 16:39:34 +0000 Mime-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101 Thunderbird/102.9.0 Subject: Re: Alan Turing's Halting Problem is incorrectly formed Newsgroups: comp.theory References: <174b353d5d09da3b$406$270558$3aa16cab@news.newsdemon.com> <174b596b08aa95a4$1$406094$7aa12cbf@news.newsdemon.com> <62_OL.1393502$iS99.555018@fx16.iad> <174b639810e2e28c$1$4071890$faa1aca7@news.newsdemon.com> <2m0PL.1393505$iS99.664715@fx16.iad> <174b650d9771285d$1$1853841$7aa12caf@news.newsdemon.com> <174b6dedaf4ee6ec$88$1053351$3aa16cbb@news.newsdemon.com> <174b7559f43ebeb6$1$746483$baa1ecb3@news.newsdemon.com> <174b79e259f67d70$18$588642$faa1aca7@news.newsdemon.com> <8883230b-cfed-4806-9dbf-646fb013b049n@googlegroups.com> <161fb284-f5d2-4a7b-91ba-10f006a257den@googlegroups.com> Content-Language: en-US From: Mr Flibble In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Lines: 394 Path: ...!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!news.newsdemon.com!not-for-mail Nntp-Posting-Date: Sat, 18 Mar 2023 16:39:34 +0000 X-Received-Bytes: 18936 Organization: NewsDemon - www.newsdemon.com X-Complaints-To: abuse@newsdemon.com Message-Id: <174d90eaddb1107e$1$270558$3aa16cab@news.newsdemon.com> Bytes: 19212 On 18/03/2023 15:39, olcott wrote: > On 3/18/2023 10:19 AM, Jeffrey Rubard wrote: >> On Tuesday, March 14, 2023 at 2:09:26 PM UTC-7, Jeffrey Rubard wrote: >>> On Tuesday, March 14, 2023 at 2:08:44 PM UTC-7, Jeffrey Rubard wrote: >>>> On Saturday, March 11, 2023 at 2:11:46 PM UTC-8, Richard Damon wrote: >>>>> On 3/11/23 4:14 PM, Mr Flibble wrote: >>>>>> On 11/03/2023 20:28, Richard Damon wrote: >>>>>>> On 3/11/23 2:51 PM, Mr Flibble wrote: >>>>>>>> On 11/03/2023 18:28, Richard Damon wrote: >>>>>>>>> On 3/11/23 12:35 PM, Mr Flibble wrote: >>>>>>>>>> On 11/03/2023 16:52, Richard Damon wrote: >>>>>>>>>>> On 3/11/23 9:53 AM, Mr Flibble wrote: >>>>>>>>>>>> On 11/03/2023 14:36, Richard Damon wrote: >>>>>>>>>>>>> On 3/11/23 9:26 AM, Mr Flibble wrote: >>>>>>>>>>>>>> On 11/03/2023 11:58, Richard Damon wrote: >>>>>>>>>>>>>>> On 3/11/23 6:20 AM, Mr Flibble wrote: >>>>>>>>>>>>>>>> On 11/03/2023 01:06, Richard Damon wrote: >>>>>>>>>>>>>>>>> On 3/10/23 7:17 PM, Mr Flibble wrote: >>>>>>>>>>>>>>>>>> On 10/03/2023 23:38, Richard Damon wrote: >>>>>>>>>>>>>>>>>>> On 3/10/23 6:26 PM, Mr Flibble wrote: >>>>>>>>>>>>>>>>>>>> On 10/03/2023 22:38, olcott wrote: >>>>>>>>>>>>>>>>>>>>> On 3/10/2023 4:17 PM, Mr Flibble wrote: >>>>>>>>>>>>>>>>>>>>>> On 10/03/2023 21:45, olcott wrote: >>>>>>>>>>>>>>>>>>>>>>> On 6/6/2004 9:11 AM, Olcott wrote: >>>>>>>>>>>>>>>>>>>>>>>> One very simple transformation of the problem >>>>>>>>>>>>>>>>>>>>>>>> into a >>>>>>>>>>>>>>>>>>>>>>>> solvable problem >>>>>>>>>>>>>>>>>>>>>>>> is to convert the Boolean function DoesItHalt() >>>>>>>>>>>>>>>>>>>>>>>> into >>>>>>>>>>>>>>>>>>>>>>>> a tertiary response: >>>>>>>>>>>>>>>>>>>>>>>> True, False, Neither. >>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>> if (DoesItHalt() == True) >>>>>>>>>>>>>>>>>>>>>>>> while(True) // loop forever >>>>>>>>>>>>>>>>>>>>>>>> ; >>>>>>>>>>>>>>>>>>>>>>>> else if (DoesItHalt() == False) >>>>>>>>>>>>>>>>>>>>>>>> return False; >>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>> else if (DoesItHalt() == NeitherTrueNorFalse) >>>>>>>>>>>>>>>>>>>>>>>> return NeitherTrueNorFalse; >>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>>> So the original Halting Problem was incorrectly >>>>>>>>>>>>>>>>>>>>>>>> formed specifically >>>>>>>>>>>>>>>>>>>>>>>> because it was framed as a Boolean function, thus >>>>>>>>>>>>>>>>>>>>>>>> failing to account >>>>>>>>>>>>>>>>>>>>>>>> for possible inputs that result in a reply other >>>>>>>>>>>>>>>>>>>>>>>> than >>>>>>>>>>>>>>>>>>>>>>>> True or False. >>>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> Message-ID: >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> [Alan Turing's Halting Problem is incorrectly >>>>>>>>>>>>>>>>>>>>>>> formed] >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> This is my very first USENET post about the Halting >>>>>>>>>>>>>>>>>>>>>>> Problem >>>>>>>>>>>>>>>>>>>>>>> back On 6/6/2004 9:11 AM >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> And yet you have reversed your position and >>>>>>>>>>>>>>>>>>>>>> instead of >>>>>>>>>>>>>>>>>>>>>> creating a decider with a ternary result you have >>>>>>>>>>>>>>>>>>>>>> gone >>>>>>>>>>>>>>>>>>>>>> back to returning a binary result. This was your >>>>>>>>>>>>>>>>>>>>>> fatal >>>>>>>>>>>>>>>>>>>>>> mistake, a mistake you probably made due to you >>>>>>>>>>>>>>>>>>>>>> naively >>>>>>>>>>>>>>>>>>>>>> being convinced by the received (but erroneous) >>>>>>>>>>>>>>>>>>>>>> wisdom >>>>>>>>>>>>>>>>>>>>>> of others. >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> /Flibble >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> 01 int D(int (*x)()) >>>>>>>>>>>>>>>>>>>>> 02 { >>>>>>>>>>>>>>>>>>>>> 03 int Halt_Status = H(x, x); >>>>>>>>>>>>>>>>>>>>> 04 if (Halt_Status) >>>>>>>>>>>>>>>>>>>>> 05 HERE: goto HERE; >>>>>>>>>>>>>>>>>>>>> 06 return Halt_Status; >>>>>>>>>>>>>>>>>>>>> 07 } >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> Since D correctly simulated by H cannot possibly reach >>>>>>>>>>>>>>>>>>>>> its own final >>>>>>>>>>>>>>>>>>>>> state "return" instruction in any finite number is >>>>>>>>>>>>>>>>>>>>> simulated steps H is >>>>>>>>>>>>>>>>>>>>> necessarily correct to reject its input D as >>>>>>>>>>>>>>>>>>>>> non-halting. >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> *The simulated D cannot possibly get past its own >>>>>>>>>>>>>>>>>>>>> line 03* >>>>>>>>>>>>>>>>>>>>> H(D,D) simulates D(D) that calls H(D,D) to simulate >>>>>>>>>>>>>>>>>>>>> itself again... >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> An invalid program neither halts nor doesn't halt. >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> /Flibble >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> So D can't be an invalid program as it will always >>>>>>>>>>>>>>>>>>> either >>>>>>>>>>>>>>>>>>> Halt or Not depending on the definiton of H. The only >>>>>>>>>>>>>>>>>>> way >>>>>>>>>>>>>>>>>>> for D to not be a valid program is if H isn't a valid >>>>>>>>>>>>>>>>>>> program, and then H can't be a correct halt decider. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> WRONG. The reason is subtle. It isn't that D is invalid, >>>>>>>>>>>>>>>>>> or that H isn't a correct halt decider, what is >>>>>>>>>>>>>>>>>> invalid is >>>>>>>>>>>>>>>>>> the COMBINATION of D and H. The combination is the >>>>>>>>>>>>>>>>>> category error (the Impossible Program of [Strachey >>>>>>>>>>>>>>>>>> 1965]). >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> /Flibble >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> Not possible. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> Either D is or is not a program. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> If it is, then ALL Halt decider need to be able to decide >>>>>>>>>>>>>>>>> it, even H. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> That comes from the meaning of **ALL** >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> D is not a program as it references H which references D >>>>>>>>>>>>>>>> which references H .. ad infinitum. This recursion is a >>>>>>>>>>>>>>>> manifestation of the category error present in the problem >>>>>>>>>>>>>>>> definition and is only present if the halt decider is of >>>>>>>>>>>>>>>> the >>>>>>>>>>>>>>>> simulating type (only SHDs can detect and report on the >>>>>>>>>>>>>>>> pathology via a third result); so: >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> 1) Only SHDs can solve the halting problem; >>>>>>>>>>>>>>>> 2) SHDs must have a ternary result as invalid programs >>>>>>>>>>>>>>>> neither halt nor don't halt. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> This unique insight is attributable to Mr Flibble who is >>>>>>>>>>>>>>>> the >>>>>>>>>>>>>>>> only person to have solved the halting problem. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> /Flibble >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> So, you don;t understand how it is setup at all. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Yes, D is a program, built off the code of H, which needs to >>>>>>>>>>>>>>> be program to meet the specifications. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> By specifications, program H is considered as a >>>>>>>>>>>>>>> fundamental unit. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> D is given as an input, a finite string representation of >>>>>>>>>>>>>>> this >>>>>>>>>>>>>>> program D. All programs have a finite string repesentation. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Thus, D references a copy of H, and is given a copy of the >>>>>>>>>>>>>>> finite string representation of itself. Thus no >>>>>>>>>>>>>>> "recursion of >>>>>>>>>>>>>>> references" in the definition of the program or the input. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> The program D makes a simple copy of its input, which is a >>>>>>>>>>>>>>> finite operation and then goes into its copy of the >>>>>>>>>>>>>>> program H. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Program H, to be a decider, must return an answer in a >>>>>>>>>>>>>>> finite >>>>>>>>>>>>>>> amount of time. >>>>>>>>>>>>>> >>>>>>>>>>>>>> A valid SHD with sufficient resources will return an >>>>>>>>>>>>>> answer in >>>>>>>>>>>>>> a finite amount of time. >>>>>>>>>>>>> >>>>>>>>>>>>> Then so will D (unless the answer H gives is Halting, then for >>>>>>>>>>>>> the Linz "D", D will just loop to show H wrong. For Sipser, D >>>>>>>>>>>>> will just return 0 to make H wrong. >>>>>>>>>>>>> >>>>>>>>>>>>> You can't argue that D doesn't return due to an infinite ========== REMAINDER OF ARTICLE TRUNCATED ==========