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: <bCFwc.13980$Gx4.2537@bgtnsc04-news.ops.worldnet.att.net> <tbPOL.341876$Lfzc.136663@fx36.iad> <174b353d5d09da3b$406$270558$3aa16cab@news.newsdemon.com> <IuQOL.1529797$9sn9.846929@fx17.iad> <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> <xl2PL.1001389$MVg8.976709@fx12.iad> <174b6dedaf4ee6ec$88$1053351$3aa16cbb@news.newsdemon.com> <YK3PL.152076$OD18.68463@fx08.iad> <174b7559f43ebeb6$1$746483$baa1ecb3@news.newsdemon.com> <Zv5PL.1871149$GNG9.230884@fx18.iad> <174b79e259f67d70$18$588642$faa1aca7@news.newsdemon.com> <z07PL.197927$0dpc.19263@fx33.iad> <df6a4138-1a15-47b3-a102-197b32ef7938n@googlegroups.com> <8883230b-cfed-4806-9dbf-646fb013b049n@googlegroups.com> <161fb284-f5d2-4a7b-91ba-10f006a257den@googlegroups.com> <tv4lvl$2hutc$1@dont-email.me>
Content-Language: en-US
From: Mr Flibble <flibble2@reddwarf.jmc.corp>
In-Reply-To: <tv4lvl$2hutc$1@dont-email.me>
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:
>>>>>>>>>>>>>>>>>>>>>>> <bCFwc.13980$Gx4....@bgtnsc04-news.ops.worldnet.att.net>
>>>>>>>>>>>>>>>>>>>>>>> [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 ==========