Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #24477

Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ]

From André G. Isaak <agisaak@gm.invalid>
Newsgroups comp.theory, comp.lang.prolog, comp.lang.c, comp.lang.c++
Subject Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ]
Date 2020-10-26 12:12 -0600
Organization Christians and Atheists United Against Creeping Agnosticism
Message-ID <rn73i6$29o$1@dont-email.me> (permalink)
References <4-idnf07o54augvCnZ2dnUU7-f_NnZ2d@giganews.com> <rn6lsl$r3h$1@dont-email.me> <UqmdneUnQPBLkQrCnZ2dnUU7-enNnZ2d@giganews.com>

Cross-posted to 4 groups.

Show all headers | View raw


On 2020-10-26 11:52, olcott wrote:
> On 10/26/2020 9:18 AM, André G. Isaak wrote:
>> On 2020-10-25 19:33, olcott wrote:
>>
>>> main() executes H() and
>>> Aborted_Because_Non_Halting_Behavior_Detected(M, M)) in the process 
>>> context of x86utm. Aborted_Because_Non_Halting_Behavior_Detected(M, 
>>> M)) creates a whole new process context to execute H_Hat() in a 
>>> DebugTrace() DebugStep() mode. All of this is fully operational.
>>>
>>>
>>> // M has the machine address of H_Hat()
>>> void H_Hat(u32 M)
>>> {
>>>    if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
>>>      MOV_EAX_0  // Execution of M(N) has been aborted
>>>    else
>>>    {
>>>      MOV_EAX_1  // M(N) has halted
>>>      HERE: goto HERE;
>>>    }
>>>    HALT
>>> }
>>>
>>> // M and N have the machine address of H_Hat()
>>> void H(u32 M, u32 N)
>>> {
>>>    if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
>>>      MOV_EAX_0  // Execution of M(N) has been aborted
>>>    else
>>>      MOV_EAX_1  // M(N) has halted
>>>    HALT
>>> }
>>>
>>> int main()
>>> {
>>>    u32 M = (u32)H_Hat;
>>>    H(M, M);   // MOV_EAX_0
>>>    HALT
>>> }
>>>
>>> Continuing from above: H_Hat() executes another instance of
>>> Aborted_Because_Non_Halting_Behavior_Detected(M, M) in its own 
>>> process context which creates another process context to execute a 
>>> second instance of H_Hat().
>>>
>>> As soon as the second H_Hat() would execute
>>> Aborted_Because_Non_Halting_Behavior_Detected(M, M) a second time 
>>> from the same machine address the first instance of
>>> Aborted_Because_Non_Halting_Behavior_Detected(M, M) recognizes that 
>>> H_Hat() is infinitely recursive. // 2018-12-13 @7:00 PM solution
>>
>> Just to clarify, you are claiming that when the 
>> Aborted_Because_Non_Halting_Behavior_Detected inside H decides it has 
>> to abort H_Hat, the 'non-halting behaviour' it detects is occurring 
>> during the execution of Aborted_Because_Non_Halting_Behavior_Detected 
>> inside H_Hat, and not in the infinite loop present in H_Hat
> 
> Yes.
> 
> Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) detects that 
> H_Hat() specifies infinite recursion and must be terminated before any 
> H_Hat() ever reaches their undecidable state transitions.

H_Hat doesn't specify any sort of recursion, so I don't know why you 
keep claiming that. Even in an implementation where your H actually 
'executes' H_Hat in some sort of modified environment, it is not recursive.

In Linz's proof, H_Hat is a modified version of H. It contains its own 
*copy* of Aborted_Because_Non_Halting_Behavior_Detected, so the 
Aborted_Because_Non_Halting_Behavior_Detected in H is not calling 
itself, it is calling a separate function within H_Hat that just happens 
to be identical to the one in H (similarly, the inner H_Hat has its own, 
separate, copy of Aborted_Because_Non_Halting_Behavior_Detected)

And, as pointed out in an earlier post which you ignored, there is 
nothing in Linz's definition which states that H must execute anything. 
H is given an input consisting of the description of a TM and an initial 
tape configuration about which it answers the question 'will this halt'? 
There's nothing in that requiring that anything 'calls' anything, 
recursively or otherwise.

>>
>> {
>>    if (ABNHBD(M, M))      // <-- the non-halting behaviour is HERE
>>      MOV_EAX_0  // Execution of M(N) has been aborted
>>    else
>>    {
>>      MOV_EAX_1  // M(N) has halted
>>      HERE: goto HERE;  // <-- the non-halting behaviour is NOT here.
>>    }
>>    HALT
>> }
>>
>> Is that correct?
> 
> Yes.
> 
>> If so, you have just admitted that your 
>> Aborted_Because_Non_Halting_Behavior_Detected) function is NOT 
>> guaranteed to halt. If that is the case, 
> 
> No, not at all. not in the least little bit.
> bool Aborted_Because_Non_Halting_Behavior_Detected(M, M)

> is what guarantees that the halt decider always halts.

But if the copy of Aborted_Because_Non_Halting_Behavior_Detected within 
H_Hat doesn't always halt, then you cannot claim that this function is 
guaranteed to halt in H either. If this function isn't guaranteed to 
halt, then H isn't guaranteed to halt. If the the function within H_Hat 
is not identical to the one in H, then you aren't constructing the 
proper relation between H and H_Hat.

André


-- 
To email remove 'invalid' & replace 'gm' with well known Google mail 
service.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] olcott <NoOne@NoWhere.com> - 2020-10-25 20:33 -0500
  Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-26 03:10 +0000
  Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] André G. Isaak <agisaak@gm.invalid> - 2020-10-26 08:18 -0600
    Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] olcott <NoOne@NoWhere.com> - 2020-10-26 12:52 -0500
      Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] André G. Isaak <agisaak@gm.invalid> - 2020-10-26 12:12 -0600
        Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] olcott <NoOne@NoWhere.com> - 2020-10-26 14:05 -0500

csiph-web