Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Halting Problem: What Constitutes Pathological Input
Date: Fri, 9 May 2025 10:10:37 +0300
Organization: -
Lines: 128
Message-ID: <vvk9pd$2l843$1@dont-email.me>
References: <GE4SP.47558$VBab.42930@fx08.ams4> <vvbcb3$1b6l1$2@dont-email.me> <vvbe0j$1av94$8@dont-email.me> <vvbecc$1b6l1$6@dont-email.me> <vvbhk0$1ijna$1@dont-email.me> <vvbjjg$1kegb$1@dont-email.me> <vvbk93$1l4cf$1@dont-email.me> <vvbkft$1kegb$4@dont-email.me> <vvbl71$1ljaj$1@dont-email.me> <vvbma3$1kegb$5@dont-email.me> <vvbmp0$1ljaj$2@dont-email.me> <vvbqd5$1tr5o$1@dont-email.me> <vvbrha$1us1f$1@dont-email.me> <b5dffdb99fdbfe0cd74914de4d51abe0aa439e7d@i2pn2.org> <vvdj0r$3cbpq$9@dont-email.me> <db8999eda88b9152608e58380b8ef7d00862dbaa@i2pn2.org> <vvdrtn$3n3t4$3@dont-email.me> <897025cb9afe82ccb07aeec07105405542f10188@i2pn2.org> <vvefcn$89u0$4@dont-email.me> <c94910051b25e3c6273bba53e703c04600e0b0d3@i2pn2.org> <vvfubk$130t3$5@dont-email.me> <cd3367aa9864ea7dee44b18efd9d5782c2fe779e@i2pn2.org> <vvh7kc$1gq2p$5@dont-email.me> <c9361ccaf55319adc65763c3d729100a6cd10d1b@i2pn2.org> <vvhdtp$1hom3$5@dont-email.me> <871bf3296f9314f3992eb252f28f188e321e6408@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 09 May 2025 09:10:38 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="424ca06bfa5b0c461a2474ae9cc59d00";
	logging-data="2793603"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/EO/mAHEBMm084QIjDKB93"
User-Agent: Unison/2.2
Cancel-Lock: sha1:5srNGSPoIuFQPs+NAcBGRHDrumM=
Bytes: 7441

On 2025-05-08 10:49:40 +0000, Richard Damon said:

> On 5/8/25 1:02 AM, olcott wrote:
>> On 5/7/2025 10:48 PM, Richard Damon wrote:
>>> On 5/7/25 11:15 PM, olcott wrote:
>>>> On 5/7/2025 9:09 PM, Richard Damon wrote:
>>>>> On 5/7/25 11:31 AM, olcott wrote:
>>>>>> On 5/7/2025 5:55 AM, Richard Damon wrote:
>>>>>>> On 5/6/25 10:09 PM, olcott wrote:
>>>>>>>> On 5/6/2025 5:52 PM, Richard Damon wrote:
>>>>>>>>> On 5/6/25 4:37 PM, olcott wrote:
>>>>>>>>>> On 5/6/2025 3:22 PM, joes wrote:
>>>>>>>>>>> Am Tue, 06 May 2025 13:05:15 -0500 schrieb olcott:
>>>>>>>>>>>> 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:
>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>> What does it violate?
>>>>>>>>>>> 
>>>>>>>>>>>>>>> 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.
>>>>>>>>>> 
>>>>>>>>>>> You are very confused. An algorithm or program computes a function.
>>>>>>>>>>> 
>>>>>>>>>> 
>>>>>>>>>> Nothing computes a function unless it applies a specific
>>>>>>>>>> set of rules to its actual input to derive its output.
>>>>>>>>>> Anything that ignores its input is not computing a function.
>>>>>>>>>> 
>>>>>>>>> 
>>>>>>>>> Right, so HHH needs to apply the rules that it was designed with.
>>>>>>>>> 
>>>>>>>>> And that means it breaks the criteria that you say it needs to do to 
>>>>>>>>> get the right answer,
>>>>>>>>> 
>>>>>>>>> And thus it gets the wrong answer.
>>>>>>>>> 
>>>>>>>> 
>>>>>>>> It needs to emulate DD according to the rules of
>>>>>>>> the x86 language. This includes emulating itself
>>>>>>>> emulating DD until it recognizes that if it kept
>>>>>>>> doing this that DD would never halt.
>>>>>>> 
>>>>>>> No, to be a correct emulator it needs to continue until it reaches the end,
>>>>>>> 
>>>>>>> It can get the right answer if it emulates the input to the point that 
>>>>>>> it can show that a
>>>>>>> 
>>>>>>> 
>>>>>>>> 
>>>>>>>> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>>>>>>>>      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
>>>>>>> 
>>>>>>> Right, that UTM(D) would never halt.
>>>>>>> 
>>>>>>>> 
>>>>>>>> *would never stop running unless aborted*
>>>>>>>> Is the hypothetical HHH/DD pair where HHH does not abort.
>>>>>>> 
>>>>>>> 
>>>>>>> Nope, can't change DD, it is your hypothetical HHH, which has become 
>>>>>>> UTM, when given the ORIGINAL DD, which calls the ORIGINAL HHH, as that 
>>>>>>> code was part of the definition of DD.
>>>>>> 
>>>>>> HHH bases its decision on what the behavior of DD
>>>>>> would be if a hypothetical version of its own self
>>>>>> never aborted.
>>>>>> 
>>>>> 
>>>>> In other words, it bases it decision on a LIE.
>>>>> 
>>>> 
>>>> It bases its decision on exactly what Professor Sipser agreed to.
>>> 
>>> Nope
>>> 
>>>> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>>>>      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
>>>> 
>>>>      H can abort its simulation of D and correctly report that D
>>>>      *specifies a non-halting sequence of configurations*.
>>>> </MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>>>> 
>>>>      *simulated D would never stop running unless aborted* then
>>>>      *H can abort its simulation of D*
>>>>      *D specifies a non-halting sequence of configurations*
>>>> 
>>>> One hypothetical HHH that never aborts and
>>>> another different HHH that does abort.
>>>> 
>>> 
>>> But your Hypothetical HHH wasn't given the right input, because you 
>>> never had one since you have admitted that D isn't a program as 
>>> required and assumed by Professor Sipser.
>>> 
>> Termination analyzers can be and have been applied to C functions.
> 
> But only C functions that represent PROGRAMS, i.e. that include all the 
> code they will use.

A termination analyser could report that termination cannot be proven if
it detects that an undefined function is called or if it cannot determine
that that function is never called. Detection of dead code is useful but
not in the scope of the primary purpose of terminatin analysis.

-- 
Mikko