Re: The halting problem is incorrect two different ways

From	Mikko <mikko.levanto@iki.fi>
Newsgroups	comp.theory
Subject	Re: The halting problem is incorrect two different ways
Date	2025-11-15 12:15 +0200
Organization	-
Message-ID	<10f9js7$3e65b$1@dont-email.me> (permalink)
References	(12 earlier) <10f201m$1ekh0$1@dont-email.me> <10f4604$21bpf$2@dont-email.me> <10f4uof$28hb9$1@dont-email.me> <10f6sb3$2o84l$1@dont-email.me> <10f7g5q$2tkbn$1@dont-email.me>

Show all headers | View raw

On 2025-11-14 15:00:09 +0000, olcott said:

> On 11/14/2025 3:21 AM, Mikko wrote:
>> On 2025-11-13 15:50:37 +0000, olcott said:
>> 
>>> On 11/13/2025 2:48 AM, Mikko wrote:
>>>> On 2025-11-12 12:54:12 +0000, olcott said:
>>>> 
>>>>> On 11/12/2025 1:09 AM, Mikko wrote:
>>>>>> On 2025-11-11 13:04:13 +0000, olcott said:
>>>>>> 
>>>>>>> On 11/11/2025 2:59 AM, Mikko wrote:
>>>>>>>> On 2025-11-10 14:48:00 +0000, olcott said:
>>>>>>>> 
>>>>>>>>> On 11/10/2025 3:43 AM, Mikko wrote:
>>>>>>>>>> On 2025-11-09 12:51:57 +0000, olcott said:
>>>>>>>>>> 
>>>>>>>>>>> On 11/9/2025 4:22 AM, Mikko wrote:
>>>>>>>>>>>> On 2025-11-08 13:36:06 +0000, olcott said:
>>>>>>>>>>>> 
>>>>>>>>>>>>> On 11/8/2025 2:05 AM, Mikko wrote:
>>>>>>>>>>>>>> On 2025-11-07 12:57:48 +0000, olcott said:
>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>> On 11/7/2025 2:05 AM, Mikko wrote:
>>>>>>>>>>>>>>>> On 2025-11-06 20:48:02 +0000, olcott said:
>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>> D simulated by H cannot possibly reach its own
>>>>>>>>>>>>>>>>> simulated final halt state.
>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>> That is merely a defect in H and irrelevanto to the semantic and other
>>>>>>>>>>>>>>>> properties of D.
>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>> That's a stupid statement.
>>>>>>>>>>>>>> 
>>>>>>>>>>>>>> Stupid is better than false.
>>>>>>>>>>>>> 
>>>>>>>>>>>>> It is stupidly false because you didn't bother
>>>>>>>>>>>>> to pay any attention at all.
>>>>>>>>>>>> 
>>>>>>>>>>>> A statement about me is off topic in comp.theory.
>>>>>>>>>>>> 
>>>>>>>>>>>>> H simulates D that calls H(D) that
>>>>>>>>>>>>> simulates D that calls H(D) that
>>>>>>>>>>>>> simulates D that calls H(D) that
>>>>>>>>>>>>> simulates D that calls H(D) that never reaches
>>>>>>>>>>>>> the simulated "return" statement final halt
>>>>>>>>>>>>> state of D because D calls H(D) in recursive
>>>>>>>>>>>>> simulation.
>>>>>>>>>>>>> 
>>>>>>>>>>>>> Have you ever done any actual programming?
>>>>>>>>>>>> 
>>>>>>>>>>>> A question about me is off topic in comp.theory. But yes, I did yesterday.
>>>>>>>>>>> 
>>>>>>>>>>> *This is my key foundational point*
>>>>>>>>>>> 
>>>>>>>>>>> int H(char* P);
>>>>>>>>>>> 
>>>>>>>>>>> int D()
>>>>>>>>>>> {
>>>>>>>>>>>    int Halt_Status = H(D);
>>>>>>>>>>>    if (Halt_Status)
>>>>>>>>>>>      HERE: goto HERE;
>>>>>>>>>>>    return Halt_Status;
>>>>>>>>>>> }
>>>>>>>>>>> 
>>>>>>>>>>> The above is in test.c
>>>>>>>>>>> 
>>>>>>>>>>> simulate.exe implements a C interpreter.
>>>>>>>>>>> 
>>>>>>>>>>> simulate test.c
>>>>>>>>>>> 
>>>>>>>>>>> runs the interpreter on the above source file
>>>>>>>>>>> from the command prompt.
>>>>>>>>>> 
>>>>>>>>>> Any program that does not correctly tell whether test.c halts is not
>>>>>>>>>> a halt decider. A program that gives an incorrect answer is not even
>>>>>>>>>> a partial halt decider.
>>>>>>>>>> 
>>>>>>>>>>> When this interpreter sees the call to H(D)
>>>>>>>>>>> it calls itself with the text body of D.
>>>>>>>>>> 
>>>>>>>>>> According to C semanttics it should simulate H(D), either simultating
>>>>>>>>>> instructions of H or simulating the return from H(D) with the same
>>>>>>>>>> returned value as H(D) would return if executed, or do whatever H would
>>>>>>>>>> do if H would not not return.
>>>>>>>>> 
>>>>>>>>> That is not the behavior that the input to H(D) specifies.
>>>>>>>>> simulator.exe simulates Test.c. This simulates D that
>>>>>>>>> calls H(D) that the simulator recognizes as itself.
>>>>>>>> 
>>>>>>>> It is the behavour C semantics specifies. According to C semantics
>>>>>>>> any other behavour that produces the same result is equally valid.
>>>>>>>> 
>>>>>>>>> So D remains stuck in recursive simulation never being
>>>>>>>>> able to complete its first statement before calling H(D)
>>>>>>>>> again and again.
>>>>>>>> 
>>>>>>>> If that happens then H does not return and therefore is not a decider.
>>>>>>> 
>>>>>>> Maybe my work is over your head.
>>>>>> 
>>>>>> Maybe the definition of "decider" is over your head.
>>>>> 
>>>>> typedef int (*ptr)();
>>>>> int HHH(ptr P);
>>>>> 
>>>>> int DD()
>>>>> {
>>>>>    int Halt_Status = HHH(DD);
>>>>>    if (Halt_Status)
>>>>>      HERE: goto HERE;
>>>>>    return Halt_Status;
>>>>> }
>>>>> 
>>>>> int main()
>>>>> {
>>>>>    HHH(DD);
>>>>> }
>>>>> 
>>>>> People here have consistently lied about
>>>>> DD simulated by HHH reaching its own "return"
>>>>> statement final halt state for three years.
>>>>> 
>>>>> You yourself have not told the truth about
>>>>> this even once.
>>>> 
>>>> That seems to confirm that the definition of "decider" is over your head.
>>> 
>>> I am just talking at the level of the execution
>>> trace of C functions. D does specify non-halting
>>> behavior to its termination analyzer.
>> 
>> The termination problem is not about specifying "to its termination
>> analyzer". Instead the termination problem is to determine whether
>> a program terminates every time when used as it was designed to be
>> used.
> 
> The halting problem requires that a halt decider
> correctly report on the behavior of its caller
> and no halt decider can even see its actual caller.

Every halt decider is required to report on the behaviour asked about.
Whether the halt decider itself is a part of question does not affect
the requirement. A solution of the halting problem must include rules
of encoding of the input that ensure a sufficient description is given
to the decider. Obviously the description is sufficient if there is a
universal Turing machine that simulates that behaviour when given the
same input.

-- 
Mikko

Thread

(Thread has 637 articles, showing 500 — browse group in flat view)

csiph-web