Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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.
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
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