Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: Halting Problem: What Constitutes Pathological Input Date: Wed, 7 May 2025 16:56:02 -0400 Organization: A noiseless patient Spider Lines: 123 Message-ID: References:

MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Wed, 07 May 2025 22:56:02 +0200 (CEST) Injection-Info: dont-email.me; posting-host="3013d96e0ac4b7dd359f7afe652f4ce0"; logging-data="1231022"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18WuqlAwDZqw8EHTl8g3sYU" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:vJUW9qzbRkPFI5QVegono+jVPA0= In-Reply-To: Content-Language: en-US On 5/7/2025 4:47 PM, olcott wrote: > On 5/7/2025 1:27 PM, dbush wrote: >> On 5/7/2025 2:24 PM, olcott wrote: >>> On 5/7/2025 5:58 AM, Richard Damon wrote: >>>> On 5/6/25 10:00 PM, olcott wrote: >>>>> On 5/6/2025 5:49 PM, Richard Damon wrote: >>>>>> On 5/6/25 2:05 PM, olcott wrote: >>>>>>> On 5/6/2025 5:59 AM, Richard Damon wrote: >>>>>>>> On 5/5/25 10:18 PM, olcott wrote: >>>>>>>>> On 5/5/2025 8:59 PM, dbush wrote: >>>>>>>>>> On 5/5/2025 8:57 PM, olcott wrote: >>>>>>>>>>> On 5/5/2025 7:49 PM, dbush wrote: >>>>>>>>>>>> >>>>>>>>>>>> Which starts with the assumption that an algorithm exists >>>>>>>>>>>> that performs the following mapping: >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> 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 >>>>>>>>>>>> (,Y) maps to 0 if and only if X(Y) does not halt when >>>>>>>>>>>> executed directly >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>>> DO COMPUTE THAT THE INPUT IS NON-HALTING >>>>>>>>>>>>> IFF (if and only if) the mapping FROM INPUTS >>>>>>>>>>>>> IS COMPUTED. >>>>>>>>>>>> >>>>>>>>>>>> i.e. it is found to map something other than the above >>>>>>>>>>>> function which is a contradiction. >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> The above function VIOLATES COMPUTER SCIENCE. >>>>>>>>>>> You make no attempt to show how my claim >>>>>>>>>>> THAT IT VIOLATES COMPUTER SCIENCE IS INCORRECT >>>>>>>>>>> you simply take that same quote from a computer >>>>>>>>>>> science textbook as the infallible word-of-God. >>>>>>>>>> >>>>>>>>>> All you are doing is showing that you don't understand proof >>>>>>>>>> by contradiction, >>>>>>>>> >>>>>>>>> Not at all. The COMPUTER SCIENCE of your requirements IS WRONG! >>>>>>>>> >>>>>>>> >>>>>>>> No, YOU don't understand what Computer Science actually is >>>>>>>> talking about. >>>>>>>> >>>>>>> >>>>>>> Every function computed by a model of computation >>>>>>> must apply a specific sequence of steps that are >>>>>>> specified by the model to the actual finite string >>>>>>> input. >>>>>> >>>>>> Right, "Computed by a model of computation", that >>>>>> >>>>>>> >>>>>>> HHH(DD) must emulate DD according to the rules >>>>>>> of the x86 language. >>>>>> >>>>>> Right, which is doesn't do. >>>>>> >>>>>> Remember, your HHH stop processing at a CALL HHH instruction. >>>>>> >>>>> >>>>> >>>>> If simulating halt decider H correctly simulates its >>>>> *input D* until H correctly determines that its simulated D >>>>> *would never stop running unless aborted* then >>>>> >>>>> *input D* // the actual input >>>> >>>> Which calls the original H >>>> >>>>> >>>>> *would never stop running unless aborted* >>>>> // A hypothetical HHH/DD pair where HHH and DD are >>>>> // exactly the same except that this HHH does not abort. >>>>> >>>>> >>>> >>>> No, your hypothetical HHH (like your HHH1) paired with the originl >>>> DD which uses the original HHH. >>>> >>> >>> That is NOT what this means: >>> *simulated D would never stop running unless aborted* >>> >>> All simulating halt deciders must >>> PREDICT WHAT THE BEHAVIOR WOULD BE >> >> If the machine described by its input was executed directly, as per >> the requirements of a halt decider: >> >> >> 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 >> (,Y) maps to 0 if and only if X(Y) does not halt when executed >> directly >> > > I have proved that everyone has been wrong about this > for ninety years. You can't prove requirements or definitions wrong. I want to know if any arbitrary algorithm X with input Y will halt when executed directly. It would be *very* useful to me if I had an algorithm H that could tell me that in *all* possible cases. If so, I could solve the Goldbach conjecture, among many other unsolved problems. Does an algorithm H exist that can tell me that or not?