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

[olcott]

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

[André G. Isaak]

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.

[olcott]

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

[André G. Isaak]

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.

[olcott]

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.