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


Groups > comp.theory > #24444 > unrolled thread

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

Started byolcott <NoOne@NoWhere.com>
First post2020-10-25 20:33 -0500
Last post2020-10-26 14:05 -0500
Articles 6 — 3 participants

Back to article view | Back to comp.theory


Contents

  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

#24444 — Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ]

Fromolcott <NoOne@NoWhere.com>
Date2020-10-25 20:33 -0500
SubjectMaking the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ]
Message-ID<4-idnf07o54augvCnZ2dnUU7-f_NnZ2d@giganews.com>
Generic system to overcome the halting problem proofs

We can ask the halt deciding question in a way that allows the input 
program to do the opposite of whatever the halt decider decides:
"Does this input program halt on its input (yes or no)?"

Or we can ask the halt deciding question in such a way where it is 
impossible for the input program to do the opposite of what the halt 
decider decides:

Did the UTM halt decider have to stop executing its subordinate UTM to 
prevent its own infinite execution?

The UTM halt decider executes its subordinate UTM one state transition 
at a time until it decides that it must stop the execution of its 
subordinate UTM or its subordinate UTM has terminated normally.

The halt decider UTM transitions to one of two final states
((qn)) or ((qy)) indicating its decision.

Here is the same thing as a conventional software function:
bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)







Specific details of overcoming the Peter Linz Halting problem proof
The following code is based on the Peter Linz H and Ĥ
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

I created the x86utm operating system on the basis of a very excellent 
x86 emulator. The x86 emulator is written in "C" and has been adapted to
run on Linux and Windows.

x86 language ≡ von Neumann architecture ≡ UTM

x86utm operating system is written in C++ and provides a way to 
functions written in "C" to be converted into virtual machines that are 
executed in their own process context. The x86 machine language is the 
the description language of these UTM equivalents and can be directly 
executed in x86utm.

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

This first instance stops executing H_Hat() which has invoked the second 
instance of Aborted_Because_Non_Halting_Behavior_Detected(M, M) which is 
executing the second instance of H_Hat().

The outer Aborted_Because_Non_Halting_Behavior_Detected(M, M) has 
terminated the whole process tree (or hierarchy of UTMs executing other 
UTMs) before the second instance has returned a value.

Although I have this complete detailed description of exactly how H() 
correctly decides halting on H_Hat() the code for this has not been 
written. It will be written shortly. Creating the x86utm operating 
system took about a man-year working almost all the time. I am reducing 
my coding time to less the 40 hours per week.


-- 
Copyright 2020 Pete Olcott

[toc] | [next] | [standalone]


#24447

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2020-10-26 03:10 +0000
Message-ID<877drd4r85.fsf@bsb.me.uk>
In reply to#24444
olcott <NoOne@NoWhere.com> writes:

> Generic system to overcome the halting problem proofs
>
> We can ask the halt deciding question in a way that allows the input
> program to do the opposite of whatever the halt decider decides:
> "Does this input program halt on its input (yes or no)?"
>
> Or we can ask the halt deciding question in such a way where it is
> impossible for the input program to do the opposite of what the halt
> decider decides:
>
> Did the UTM halt decider have to stop executing its subordinate UTM to
> prevent its own infinite execution?

This either gives the same result as the above (in which case the same
example defeats it) or it does not give the same result and thus does
not address the halting problem at all.  (Or, I should say, both -- it
can be wrong in both ways).

> The UTM halt decider executes its subordinate UTM one state transition
> at a time until it decides that it must stop the execution of its
> subordinate UTM or its subordinate UTM has terminated normally.
>
> The halt decider UTM transitions to one of two final states
> ((qn)) or ((qy)) indicating its decision.

Reader beware.  Peter Olcott either does not know what a UTM is or he
wilfully misuses the term as often as he can.  This is an example: the
final state of a UTM has nothing to do with the final state of the TM
being interpreted.

> Here is the same thing as a conventional software function:
> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>
> Specific details of overcoming the Peter Linz Halting problem proof
> The following code is based on the Peter Linz H and Ĥ
> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>
> I created the x86utm operating system on the basis of a very excellent x86 emulator. The x86 emulator is written in "C" and has been adapted to
> run on Linux and Windows.
>
> x86 language ≡ von Neumann architecture ≡ UTM

And there's another misuse of the term.

> x86utm operating system is written in C++ and provides a way to
> functions written in "C" to be converted into virtual machines that
> are executed in their own process context. The x86 machine language is
> the the description language of these UTM equivalents and can be
> directly executed in x86utm.

And another three.

> 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.

but mysteriously hidden!

> // 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

This comment is wrong.

>   else
>   {
>     MOV_EAX_1  // M(N) has halted

And this one too.

>     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))

And this function call is wrong in general, but since you call H with
both M and N the same, you can get away with it.

>     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
>
> This first instance stops executing H_Hat() which has invoked the
> second instance of Aborted_Because_Non_Halting_Behavior_Detected(M, M)
> which is executing the second instance of H_Hat().
>
> The outer Aborted_Because_Non_Halting_Behavior_Detected(M, M) has
> terminated the whole process tree (or hierarchy of UTMs executing
> other UTMs) before the second instance has returned a value.
>
> Although I have this complete detailed description of exactly how H()
> correctly decides halting on H_Hat()

This description makes no mention of H and, in fact, H gets the answer
wrong.  Why?

First, for the result of H(H_Hat, H_Hat) to be correct it must indicate
the halting status of the computation.  H can be wrong about every other
computation but not about this one.  Indeed, H can even indicate
different things for various different computations -- "took too many
step to halt", "executed more than 42 instructions", "jumped back more
times than forwards", "aborted", whatever.  The only requirement is that
it indicate halting in the case of H(H_Hat, H_Hat).  (I'm labouring this
point because Pater Olcott has refused to be 100^ clear about the
meaning of H's result.)

So what really happens?  Well, no matter how complicated Peter Olcott
tries to make the action of
Aborted_Because_Non_Halting_Behavior_Detected appear, the expressions

  Aborted_Because_Non_Halting_Behavior_Detected(M, M)

in H_Hat, and, if corrected, (though it does not matter in this case)

  Aborted_Because_Non_Halting_Behavior_Detected(M, N)

in H must have the same value.

Now, if that value is true, then H(H_Hat, H_Hat) is just

    MOV_EAX_0
    HALT

indicating that H_Hat(H_Hat) is a non halting computation (that's the
0).  But H_Hat(H_Hat) is in fact just

     MOV_EAX_0
     HALT

And when Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) is
false, H(H_Hat, H_Hat) is just

    MOV_EAX_1
    HALT

indicating that H_Hat(H_Hat) is a halting computation when in fact it is

    MOV_EAX_1
    HERE: goto HERE;

> the code for this has not been written.

No surprise there.  Sadly, Peter Olcott can't post the version he
claimed to have fully encoded as actual Turing machines almost two years
because it doesn't exist.  I suspect this version will never exist
either.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#24457

FromAndré G. Isaak <agisaak@gm.invalid>
Date2020-10-26 08:18 -0600
Message-ID<rn6lsl$r3h$1@dont-email.me>
In reply to#24444
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

{
   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?

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, 
Aborted_Because_Non_Halting_Behavior_Detected() cannot possibly form the 
basis of ANY decider. Certainly not of a halt (or forced-to-abort) decider.

André

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

[toc] | [prev] | [next] | [standalone]


#24475

Fromolcott <NoOne@NoWhere.com>
Date2020-10-26 12:52 -0500
Message-ID<UqmdneUnQPBLkQrCnZ2dnUU7-enNnZ2d@giganews.com>
In reply to#24457
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.

> 
> {
>    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.

> Aborted_Because_Non_Halting_Behavior_Detected() cannot possibly form the 
> basis of ANY decider. Certainly not of a halt (or forced-to-abort) decider.
> 
> André
> 


-- 
Copyright 2020 Pete Olcott

[toc] | [prev] | [next] | [standalone]


#24477

FromAndré G. Isaak <agisaak@gm.invalid>
Date2020-10-26 12:12 -0600
Message-ID<rn73i6$29o$1@dont-email.me>
In reply to#24475
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.

[toc] | [prev] | [next] | [standalone]


#24480

Fromolcott <NoOne@NoWhere.com>
Date2020-10-26 14:05 -0500
Message-ID<8_ednRGsopyOgwrCnZ2dnUU7-V_NnZ2d@giganews.com>
In reply to#24477
On 10/26/2020 1:12 PM, André G. Isaak wrote:
> 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.

When Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
is executed in the x86utm process context it creates a new process 
context and executes H_Hat() in DebugStep() mode within this new H_Hat() 
process context.

This DebugStep() mode reaches
Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
in _Hat() and creates another process context in the _Hat() process 
context.

Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
executes this other instance of H_Hat() in the process context of the 
prior H_Hat(). As soon as it reaches
Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
in the second H_Hat() instance the outer
Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
that has been watching all of the execution steps in all of the process 
contexts sees that H_Hat() is invoking
Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
from the same machine address a second time without encountering any 
conditional branch instructions in H_Hat() that would terminate its 
otherwise infinite recursion. At this point
Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)
stops executing the first instance of H_Hat() (which also stops 
everything else in this process tree) and returns TRUE.

> 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)


On 10/23/2020 5:51 PM, Mike Terry wrote:
 > int H_Hat(u32 M)
 > {
 > if (Was_Its_Execution_Aborted(M, M))

The above simplified H_Hat() provided by Mike has been applied to the 
Peter Linz H_Hat() to make it conform to the model of the conventional 
self-referential halting problem counter-examples:

void H_Hat(u32 M)
{
   if (!Halts(M, M))
     MOV_EAX_0 // Input Loops
   else
   {
     MOV_EAX_1 // Input Halts
     HERE: goto HERE;
   }
HALT
}


> 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.

As you continue to keep ignoring I show how a halt decider can be 
defined that avoids the conventional halting problem trick.

That Peter Linz showed one way that a halt decider will not always work 
does not show that the halting problem is undecidable.

>>>
>>> {
>>>    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é

When-so-ever it detects non-halting behavior the halt decider UTM stops 
executing its subordinate UTM in one state transition at a time mode and 
transitions to its own final state of: ABORTED_NON_TERMINATING_BEHAVIOR.


-- 
Copyright 2020 Pete Olcott

[toc] | [prev] | [standalone]


Back to top | Article view | comp.theory


csiph-web