Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #24444 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2020-10-25 20:33 -0500 |
| Last post | 2020-10-26 14:05 -0500 |
| Articles | 6 — 3 participants |
Back to article view | Back to comp.theory
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
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-10-25 20:33 -0500 |
| Subject | Making 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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2020-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]
| From | André G. Isaak <agisaak@gm.invalid> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | André G. Isaak <agisaak@gm.invalid> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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