How do we know that H(P,P)==0 is correct?

7 views
Skip to first unread message

olcott

unread,
Jul 5, 2021, 12:29:03 PMJul 5
to
The x86utm operating system was created so that the halting problem
could be examined concretely in the high level language of C.
When examining the halting problem this way every detail can be
explicitly specified. UTM tape elements are 32-bit unsigned integers.

// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{
P((u32)P);
}

H analyzes the (currently updated) stored execution trace of its x86
emulation of P(P) after it simulates each instruction of input (P, P).
As soon as a non-halting behavior pattern is matched H aborts the
simulation of its input and decides that its input does not halt.

Every H only acts as a pure x86 emulator until some P has demonstrated
that it will never halt unless it is aborted. Because of this the
behavior of H can always be ignored in every execution trace.

The indices to H and P indicate the degree of nested simulation. It is
easily verified that the above computation never halts unless some H(n)
aborts some P(m).

If any H(n) must abort any P(m) then this H(n) does correctly decide
that this P(m) does not halt.

In the above computation (zero based addressing) H(1) aborts P(2).

Halting problem undecidability and infinitely nested simulation

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

olcott

unread,
Jul 5, 2021, 3:30:49 PMJul 5
to
On 7/5/2021 12:54 PM, Richard Damon wrote:
> On 7/5/21 1:17 PM, olcott wrote:
>> On 7/5/2021 12:06 PM, Richard Damon wrote:
>>> So, you now do indicate somewhat via the stack address that changes on
>>> calls.
>>>
>>> But you still have the unsound claim that H can ignore its own behavior.
>>
>> That a simulating halt decider only aborts its input after its input has
>> demonstrated non-halting behavior and acts as a pure simulator until
>> then seems to be above your capacity to comprehend.
>>
>
> That you need to actually PROVE your assertions seems to be beyond yours.
>
> H does NOT see actual PROOF of non-Halting behavior, because H ignores
> that fact that the H within P can and will abort the simulation and thus
> make P a Halting Computation.

This really really seems to be beyond your capacity to understand:

H never ever gets to the point in its own execution where it aborts the
simulation of its input until AFTER its input has already proven that it
will never halt unless aborted.

I have told that twenty times now and you still don't get it.
I have told that twenty times now and you still don't get it.
I have told that twenty times now and you still don't get it.
I have told that twenty times now and you still don't get it.
I have told that twenty times now and you still don't get it.

When H simulates inputs that halt H ONLY acts as a pure simulator until
these inputs halt on their own.

olcott

unread,
Jul 5, 2021, 5:40:52 PMJul 5
to
On 7/5/2021 4:34 PM, Ben Bacarisse wrote:
> For anyone interested, here's the answer to the question posed in the
> subject line: How do we know that H(P,P)==0 is correct?
>
> We know that H(M,I) == 0 (false) is correct if, and only if, M(I) is not
> a halting (finite) computation.
>
> But PO rejects the very definition of a halting decider: a TM that
> accepts exactly those strings that represent finite computations, and
> rejects all others.
>
> Instead, a PO "Other-Halting" decider also rejects some strings that
> represent finite computations, specifically P(P) where P is hat(H), a
> function defined in terms of H like this:
>
> def hat(h):
> def p(x):
> if h(x, x):
> while True: pass
> return p
>
> For a POOH decider, H(hat(H), hat(H)) = False is correct, despite
> hat(H)(hat(H)) being a halting computation. No one except PO is
> interested in the POOH problem.
>
> On the other hand, everyone is interested in halting, but the
> computation D(hat(D), hat(D)) shows that no D computes the halting
> function.
>

Try and get your double-talk around this:

void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{
P((u32)P);
}

Because the above computation must be aborted at some point or it never
halts the above computation is a non-halting computation.

olcott

unread,
Jul 5, 2021, 8:04:52 PMJul 5
to
On 7/5/2021 6:15 PM, Ben Bacarisse wrote:
> It is a halting computation because it halts. The fact that P(P) halts
> is not in dispute.
>
> Nor is it a matter of dispute that your POOH decider, H, returns H(P,P)
> == 0 and so P(P) is a non-POOH computation. The only dispute is that
> you think someone might be interested in the POOH problem.
>
> (For obvious reasons, you resist giving the property you claim H is
> deciding a proper name. I'm not entirely sold on "PO Other Halting" but
> you won't suggest a better alternative.)
>

In computability theory, the halting problem is the problem of
determining, from a description of an arbitrary computer program and an
input, whether the program will finish running, or continue to run
forever. https://en.wikipedia.org/wiki/Halting_problem

(1) At least one way to circumvent the pathological self-reference
(olcott 2004) of the halting problem counter-example templates is with a
simulating halt decider.

void Infinite_Loop()
{
HERE: goto HERE;
}

int main()
{
u32 Input_Would_Halt2 = H((u32)Infinite_Loop, (u32)Infinite_Loop);
Output("Input_Would_Halt2 = ", Input_Would_Halt2);
}

(2) Because every input to a simulating halt decider either halts on its
own or must have its simulation terminated: all simulations that must be
terminated are correctly construed as non-halting computations.

(3) This criterion measure defines the exact same halting / not halting
sets as the halting problem. Every element P(I) that was a halting
computation remains a halting computation. Every element P(I) that was a
non-halting computation remains a non-halting computation.

The only thing that has changed is that undecidable inputs can no longer
be defined. Every TM / input pair falls into exactly one of two sets:
(a) Halting
(b) Non-halting

olcott

unread,
Jul 5, 2021, 9:01:40 PMJul 5
to
On 7/5/2021 7:45 PM, Richard Damon wrote:
> On 7/5/21 8:04 PM, olcott wrote:
>
>> In computability theory, the halting problem is the problem of
>> determining, from a description of an arbitrary computer program and an
>> input, whether the program will finish running, or continue to run
>> forever. https://en.wikipedia.org/wiki/Halting_problem
>>
>> (1) At least one way to circumvent the pathological self-reference
>> (olcott 2004) of the halting problem counter-example templates is with a
>> simulating halt decider.
>>
>> void Infinite_Loop()
>> {
>>   HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>   u32 Input_Would_Halt2 = H((u32)Infinite_Loop, (u32)Infinite_Loop);
>>   Output("Input_Would_Halt2 = ", Input_Would_Halt2);
>> }
>>
>> (2) Because every input to a simulating halt decider either halts on its
>> own or must have its simulation terminated: all simulations that must be
>> terminated are correctly construed as non-halting computations.
>>
>> (3) This criterion measure defines the exact same halting / not halting
>> sets as the halting problem. Every element P(I) that was a halting
>> computation remains a halting computation. Every element P(I) that was a
>> non-halting computation remains a non-halting computation.
>>
>> The only thing that has changed is that undecidable inputs can no longer
>> be defined. Every TM / input pair falls into exactly one of two sets:
>> (a) Halting
>> (b) Non-halting
>>
>
> Problem is that this doesn't change the challenge of the ^ machine.
>
> The definition of Halting DOES NOT CHANGE.

Because every element of the set of computations that never halt unless
their simulation is aborted maps to every element of the set of
non-halting computations we know that it is an equivalent criterion
measure that defines the same set.

olcott

unread,
Jul 5, 2021, 10:38:08 PMJul 5
to
On 7/5/2021 8:22 PM, Richard Damon wrote:
> If it WAS an equivalnet set, then H^(H^) wouldn't be on different sides
> for the two divides.
>

The simulating halt decider has two crucial phases:
(1) It is only a simulator until its input proves that it will never
halt unless aborted.

At this point we have perfect certainty that the simulating halt decider
is correct.

(2) After its input proves that it will never halt unless its simulation
an aborted its input is aborted.

> It IS a computation that Halts, and thus NOT in the set of non-Halting
> computations. By your logic, it needs to be classified in the set of
> computations that never halt unless there simulation is aborted.
>
> Thus by your logic, they aren't equivalent sets.
>
> Ultimately the problem is you mis-define that later set, with the proper
> definition the equivalence does hold. The definition that does this is
> that it means that if the simulation would be unending unless the
> instance of the simulator that doing that simulation actually needs to
> abort the simulation, but replacing it with a pure non-aborting
> simulator would yield an infinite simulation. THAT definition works, not
> your crasy one the includes other copies of the algorithm aborting other
> copies of the machine.

olcott

unread,
Jul 5, 2021, 11:06:25 PMJul 5
to
>> In computability theory, the halting problem is the problem of
>> determining, from a description of an arbitrary computer program and
>> an input, whether the program will finish running, or continue to run
>> forever. https://en.wikipedia.org/wiki/Halting_problem
>
> Yes, that's why H(P,P) == 0 is wrong (as far as halting is concerned)
> when P(P) halts.

The simulating halt decider has two crucial phases:
(1) It is only a simulator until its input proves that it will never
halt unless aborted.

At this point we have perfect certainty that the simulating halt decider
is correct.

(2) After its input proves that it will never halt unless its simulation
an aborted its input is aborted.

>
>> (1) At least one way to circumvent the pathological self-reference
>> (olcott 2004) of the halting problem counter-example templates is with
>> a simulating halt decider.
>>
>> (2) Because every input to a simulating halt decider either halts on
>> its own or must have its simulation terminated: all simulations that
>> must be terminated are correctly construed as non-halting
>> computations.
>
> The only computations that should be construed as non-halting are the
> ones that don't halt. Why does this still need to be said? Have you
> simply lost the plot?
>

A simulating halt decider is only a simulator until its input proves
that it will never halt unless aborted.

We know that when UTM(P,I) never halts that P(I) never halts.
When a simulating halt decider determines that UTM(P,I) never halts then
and only then it switches modes from simulator to halt decider.

The significance of this crucial timing difference is beyond Richard's
capacity to understand.

If H is only a simulator until it makes its halt status decision then it
is impossible for the behavior of H to have any effect what-so-ever on
this halt status decision. Richard does not seem to have the capacity to
begin to understand that.

>> (3) This criterion measure defines the exact same halting / not
>> halting sets as the halting problem.
>
> Not according to you. P(P) halts but it's non-POOH because it halts in
> the way you decided is "special".
>
>> Every element P(I) that was a
>> halting computation remains a halting computation. Every element P(I)
>> that was a non-halting computation remains a non-halting computation.
>
> Not according to you. If they were the same, you'd agree that every
> instance of the halting problem has a correct yes/no answer and that yes
> is only correct for those strings that represent halting computations.

I still have no idea of what you mean by halting problem instances,
however every TM / input pair either halts on its input or not.

A non-halting computation is every computation that never halts unless
its simulation is aborted.

This maps to every element of the conventional halting problem set of
non-halting computations and a few more.

> But despite endlessly quoting Wikipedia and Linz you reject this
> definition in favour of POOH.
>
>> The only thing that has changed is that undecidable inputs can no
>> longer be defined. Every TM / input pair falls into exactly one of two
>> sets:
>> (a) Halting
>> (b) Non-halting
>
> Actually you can't do this even for the POOH problem, but since you
> don't engage with difficult topics, there's no way I can explain to you
> why.

olcott

unread,
Jul 6, 2021, 12:15:15 AMJul 6
to
On 7/5/2021 6:15 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
> It is a halting computation because it halts. The fact that P(P) halts
> is not in dispute.
>
> Nor is it a matter of dispute that your POOH decider, H, returns H(P,P)
> == 0 and so P(P) is a non-POOH computation. The only dispute is that
> you think someone might be interested in the POOH problem.
>
> (For obvious reasons, you resist giving the property you claim H is
> deciding a proper name. I'm not entirely sold on "PO Other Halting" but
> you won't suggest a better alternative.)
>

On the basis that we know that every UTM(P,I) never halts defines the
exact same set of computations that must be aborted by a simulating halt
decider which defines the exact same set of computations P(I) that never
halt we can know that any input to a simulating halt decider that never
halts unless its simulation is aborted is a non-halting computation.

Because we know that a simulating halt decider only simulates its input
until after it has made its halt status decision we can know that H can
ignore its own address range in its execution traces.

Because the x86 execution trace of P on input P provides no possible
escape from infinitely nested simulation and we can ignore the execution
trace of H then we can know that H must abort its simulation of P on the
basis of the sixteen lines of P:

_P()
[00000b25](01) 55 push ebp
[00000b26](02) 8bec mov ebp,esp
[00000b28](01) 51 push ecx
[00000b29](03) 8b4508 mov eax,[ebp+08]
[00000b2c](01) 50 push eax
[00000b2d](03) 8b4d08 mov ecx,[ebp+08]
[00000b30](01) 51 push ecx
[00000b31](05) e81ffeffff call 00000955 // call H

Begin Local Halt Decider Simulation at Machine Address:b25
...[00000b25][002116fe][00211702](01) 55 push ebp // P1
...[00000b26][002116fe][00211702](02) 8bec mov ebp,esp
...[00000b28][002116fa][002016ce](01) 51 push ecx
...[00000b29][002116fa][002016ce](03) 8b4508 mov eax,[ebp+08]
...[00000b2c][002116f6][00000b25](01) 50 push eax
...[00000b2d][002116f6][00000b25](03) 8b4d08 mov ecx,[ebp+08]
...[00000b30][002116f2][00000b25](01) 51 push ecx
...[00000b31][002116ee][00000b36](05) e81ffeffff call 00000955 // H1
...[00000b25][0025c126][0025c12a](01) 55 push ebp // P2
...[00000b26][0025c126][0025c12a](02) 8bec mov ebp,esp
...[00000b28][0025c122][0024c0f6](01) 51 push ecx
...[00000b29][0025c122][0024c0f6](03) 8b4508 mov eax,[ebp+08]
...[00000b2c][0025c11e][00000b25](01) 50 push eax
...[00000b2d][0025c11e][00000b25](03) 8b4d08 mov ecx,[ebp+08]
...[00000b30][0025c11a][00000b25](01) 51 push ecx
...[00000b31][0025c116][00000b36](05) e81ffeffff call 00000955 // H2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

olcott

unread,
Jul 6, 2021, 11:26:16 AMJul 6
to
On 7/6/2021 9:42 AM, wij wrote:
> On Tuesday, 6 July 2021 at 21:27:20 UTC+8, olcott wrote:
>>> That's a lot of waffle. The computations for which a halt decider
>>> should return 0 are those that don't halt. P(P) halts, so H(P,P) == 0
>>> is wrong.
>>>
>> The is a lot of double-talk. I provided a sequence of correct deductions
>> and you only provided your opinion that you don't like it.
>
> That is simply all it is, not an opinion (IMO), very simple.
> You made a simple thing very complicated for yourself, by redefining the HP,
> and build an 'x86utm' OS because you like it? or what?
>
>>> Any decision problem for which 0 is the correct answer for P(P) is
>>> something other than the halting problem. I'm calling it the PO
>>> "Other-Halting" problem until a better name is suggested.
>>>
>>>> Because the x86 execution trace of P on input P...
>>>
>>> ... shows that P(P) halts, we know that H(P,P) == 0 is wrong.
>>>
>> The criteria for non-halting is impossibly incorrect. If we have the DNA
>> of a black cat and this black cat barks we still have a black cat.
>
> Simple fact is that H can not pass a real test.
> There is no need for any real software engineer to talk about your reasoning
> and implement.

The criterion measure of every Turing Machine Description ⟨P⟩ of Turing
machine P that would never halt on its input I <is> the exact same set
as the set of simulations (P,I) that must be aborted to prevent their
infinite simulation <is> the exact same set as Turing machines that do
not halt on their input P(I) cannot be circumvented or bypassed.

There is no case where a black cat is not a cat that is black.


>
>> --
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
+

olcott

unread,
Jul 6, 2021, 11:59:57 AMJul 6
to
On 7/6/2021 7:39 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> I still have no idea of what you mean by halting problem instances,
>
> Yet you are prepared to pontificate about it.
>
>> however every TM / input pair either halts on its input or not.
>>
>> A non-halting computation is every computation that never halts unless
>> its simulation is aborted.
>
> A non-halting computation is simply a computation that never halts.
> Those that halt (for whatever reason) are halting computations. Here
> you appear to be defining (rather vaguely) non-POOH computations without
> the honesty of giving the property a clear name.
>

void Infinite_Loop()
{
HERE: goto HERE;
}

int main()
{
u32 Input_Would_Halt2 = H((u32)Infinite_Loop, (u32)Infinite_Loop);
Output("Input_Would_Halt2 = ", Input_Would_Halt2);
}

You keep dodging this.
When Infinite_Loop() is forced to halt its stops running.


void Infinite_Recursion(u32 N)
{
Infinite_Recursion(N);
}

int main()
{
u32 Input_Halts = H((u32)Infinite_Recursion, 3);
Output("Input_Halts = ", Input_Halts);
}

When Infinite_Recursion() is forced to halt its stops running.

// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{
u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}

When P() is forced to halt its stops running.

This proves that forced to halt does not count as halting.

All computations that must be forced to halt to prevent their infinite
simulation is the same set of simulations that never halt is the same
set as computation that never halt.

That a simulating halt decider later forced them to halt so that it
could report that they never halt does not ever count as halting.

>> This maps to every element of the conventional halting problem set of
>> non-halting computations and a few more.
>
> Yes. The halting problem and the POOH problem have different "yes" and
> "no" sets. You can choose to be potentially right talking about the
> POOH problem, or you can be certainly wrong by pretending that you are
> talking about the halting problem.

olcott

unread,
Jul 6, 2021, 12:33:46 PMJul 6
to
On 7/6/2021 7:39 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> I still have no idea of what you mean by halting problem instances,
>
> Yet you are prepared to pontificate about it.
>
>> however every TM / input pair either halts on its input or not.
>>
>> A non-halting computation is every computation that never halts unless
>> its simulation is aborted.
>
> A non-halting computation is simply a computation that never halts.
> Those that halt (for whatever reason) are halting computations. Here
> you appear to be defining (rather vaguely) non-POOH computations without
> the honesty of giving the property a clear name.
>
>> This maps to every element of the conventional halting problem set of
>> non-halting computations and a few more.
>
> Yes. The halting problem and the POOH problem have different "yes" and
> "no" sets. You can choose to be potentially right talking about the
> POOH problem, or you can be certainly wrong by pretending that you are
> talking about the halting problem.
>

When the simulation of a computation halts without ever being aborted
this is exactly the same as the set of halting problem computations that
halt.

Every element of the set of halting problem computations that never halt
map to an element of the set of simulations that must be aborted.

The set of halting problem TM / confounding inputs are no longer
confounding. They are no longer confounding because their erroneous
criterion measure that suffered from the pathological
self-reference(Olcott 2004) error has been transformed into a criterion
measure that does not have this error.

Mr Flibble

unread,
Jul 6, 2021, 4:18:17 PMJul 6
to
But this case is trivial and uninteresting: your decider needs to
analyse branching logic predicated on arbitrary input to be
non-trivial and interesting. You've still got nothing of value to show.

/Flibble


olcott

unread,
Jul 6, 2021, 4:41:17 PMJul 6
to
Once people comprehend that my halting criteria eliminates the
pathological self-reference(Olcott 2004) of the halting problem proof
counter-examples they will understand that the halting problem is not
undecidable. Then teams of hundreds of software developers can handle
details such as branching logic.

The reason that my C code analyzes x86 code is that x86 code provides a
complete directed graph of all control flow.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

Mr Flibble

unread,
Jul 6, 2021, 6:18:55 PMJul 6
to
On Tue, 6 Jul 2021 15:41:09 -0500
Nonsense:

mov eax,[ebp+08]

the memory at the address [ebp+08] might be
mapped to an I/O device so you don't know a priori what value it will
have.

More nonsense is of course that you have yet to show an example which
does involve control flow (with branching logic) and even if you did you
haven't responded to people posting non-trivial control flow examples.

/Flibble

olcott

unread,
Jul 6, 2021, 10:00:27 PMJul 6
to
On 7/6/2021 8:56 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
> No one is interested in the POOH problem. For the halting problem,
> H(P,P) is correct only when
>
> H(P,P) != 0 and P(P) halts, or
> H(P,P) == 0 and P(P) does not halt.
>
> Neither is the case. That H might be correct for some other decision
> problem is not relevant.
>

// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{
u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}

When the simulation of the Turing machine description ⟨P⟩ of a Turing
machine P on input I never halts we know that P(I) never halts.

Simulating halt deciders must abort their simulation of all inputs where
the pure simulation of this input would never halt.

Simulating halt deciders act as a pure simulators of their input until
this input demonstrates non-halting behavior.

This allows simulating halt deciders to totally ignore their own
behavior in making their halt status decision.

It is this feature of the adapted halt deciding criteria that eliminates
the pathological self-reference (polcott 2004) from the halting problem
counter-example templates.

Simulating halt deciders never have behavior that effects their halt
status decision because they only act as pure simulators until after
they have made this decision.

Using the above reasoning we can know that when the x86 execution trace
of P on input P shows that there is no code in P that escapes the
infinitely nested simulation of P on input P, then we know that P on
input P meets the definition of a computation that never halts: (a pure
simulation that never halts).

Don Stockbauer

unread,
Jul 7, 2021, 7:19:44 AMJul 7
to
Perhaps the true solution to the hoarding problem is the quote is to is for people to quit your heart for people to hold discussion about the whole thing problem.
> "Great spirits have always encountered violent opposition from mediocre
> minds." Einstein

Perhaps the true solution to the halting problem is to get people to halt discussion about the halting problem.

Bonita Montero

unread,
Jul 7, 2021, 8:18:34 AMJul 7
to
According to your posting-frequency you're manic.
But post only to comp.arch; this is the only appropriate NG.
You don't have any C/C++-specific issues and your thoguhts
aren't related to AI either.

olcott

unread,
Jul 7, 2021, 10:47:26 AMJul 7
to
On 7/7/2021 5:46 AM, Ben Bacarisse wrote:
> Richard Damon <Ric...@Damon-Family.org> writes:
>
>> On 7/5/21 7:15 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>>
>>>> Because the above computation must be aborted at some point or it
>>>> never halts the above computation is a non-halting computation.
>>>
>>> It is a halting computation because it halts. The fact that P(P) halts
>>> is not in dispute.
>>>
>>> Nor is it a matter of dispute that your POOH decider, H, returns H(P,P)
>>> == 0 and so P(P) is a non-POOH computation. The only dispute is that
>>> you think someone might be interested in the POOH problem.
>>>
>>> (For obvious reasons, you resist giving the property you claim H is
>>> deciding a proper name. I'm not entirely sold on "PO Other Halting" but
>>> you won't suggest a better alternative.)
>>>
>>
>> I think the name is wrong, his machines don't REALLY deal with Halting,
>> so it isn't other Halting, it really should be called Peter Olcott's
>> Other Problem.
>
> Good point. It's because, in the original description, the halting of
> one computation was reported as the halting of another that I went with
> that name, but it does, as you say, suggest the wrong meaning for
> other. Your name is better, but I don't want to confuse anyone by
> changing. Maybe PO can choose which he prefers?
>

H acts as a pure x86 simulator until its input demonstrates non-halting
behavior. It is common knowledge that when-so-ever the pure simulation
of the machine description of a machine never halts on its input that
this logically entails that this machine never halts on its input. This
proves that H uses the same halting criteria as the halting problem.

Because H acts as a pure simulator of its input until after it makes its
halt status decision we know that the behavior of H cannot possibly have
any effect on the behavior of P thus the behavior of H can be totally
ignored in any halt status decision.

olcott

unread,
Jul 7, 2021, 12:24:32 PMJul 7
to
On 7/7/2021 10:32 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/6/2021 8:56 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>> No one is interested in the POOH problem. For the halting problem,
>>> H(P,P) is correct only when
>>> H(P,P) != 0 and P(P) halts, or
>>> H(P,P) == 0 and P(P) does not halt.
>>> Neither is the case. That H might be correct for some other decision
>>> problem is not relevant.
>>>
>>
>> // Simplified Linz Ĥ (Linz:1990:319)
>> void P(u32 x)
>> {
>> u32 Input_Halts = H(x, x);
>> if (Input_Halts)
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> u32 Input_Halts = H((u32)P, (u32)P);
>> Output("Input_Halts = ", Input_Halts);
>> }
>>
>> When the simulation of the Turing machine description ⟨P⟩ of a Turing
>> machine P on input I never halts we know that P(I) never halts.
>
> P(P) halts. Any simulation of P(P) halts. H(P,P) == 0 is wrong about
> the halting of P(P).
>
>> Simulating halt deciders must abort their simulation of all inputs
>> where the pure simulation of this input would never halt.
>
> That is, indeed, one way in which they can be wrong. Every TM is wrong
> about some instances.

H acts as a pure x86 simulator until its input demonstrates non-halting
behavior. It is common knowledge that when-so-ever the pure simulation
of the machine description of a machine never halts on its input that
this logically entails that this machine never halts on its input. This
proves that H uses the same halting criteria as the halting problem.

Because H acts as a pure simulator of its input until after it makes its
halt status decision we know that the behavior of H cannot possibly have
any effect on the behavior of P thus the behavior of H can be totally
ignored in any halt status decision.

Every H in the entire nested simulation chain always only acts as a pure
c86 emulator until some H detects that some P will never halt.

We know that a black cat is a cat that is black even if the black cat
barks. We know that H(P,P)==0 even if P(P) halts. In both cases we know
this by logical necessity.

When the pure simulation of an input never halts then this is a
non-halting computation by logical necessity. You know that there are no
exceptions to this rule.

olcott

unread,
Jul 7, 2021, 2:10:59 PMJul 7
to
On 7/7/2021 12:53 PM, wij wrote:
> I do not want to go into theoretical details too much.
> If you admit H(P,P)==0 and P(P) halts, then H is no longer a halting decider
> by definition.
>

P(P) does specify infinitely nested simulation that a global halt
decider immediately catches and aborts, thus not allowing P(P) to halt.

When the local halt decider is used then H aborts its simulation (P,P)
as soon as (P,P) is an input to H.

> If H re-assign the T/F value of 'pathological input', H will still create another
> another set of undecidable input, H is doomed not a decisive function.
> [Hints]: H is function f:2^(2^|N|)->{0,1}, way beyond the capability of TM.
> Even if such a f is possible, the convention HP still true. H will still be an
> undecidable function.
>

Because H acts as a pure simulator of its input until after it makes its
halt status decision we know that the behavior of H cannot possibly have
any effect on the behavior of P thus the behavior of H can be totally
ignored in any halt status decision. This eliminates the pathological
self-reference of the halting problem proof counter-example templates
making them decidable.

olcott

unread,
Jul 7, 2021, 2:43:20 PMJul 7
to
On 7/7/2021 12:25 PM, Real Troll wrote:
> He wants to win a Nobel price in computing! He believes you can
> recommend him to the Nobel committee for his incessant trolling.

There is no Nobel prize in computing. It turns out that it would have
been impossible for me to make my views clear enough to be understood
without the feedback that I have received on comp.theory of USENET.

They are finally on the verge of being clear enough to be understood to
be correct...

H acts as a pure x86 simulator until its input demonstrates non-halting
behavior. It is common knowledge that when-so-ever the pure simulation
of the machine description of a machine never halts on its input that
this logically entails that this machine never halts on its input. This
proves that H uses the same halting criteria as the halting problem.

Because H acts as a pure simulator of its input until after it makes its
halt status decision we know that the behavior of H cannot possibly have
any effect on the behavior of P thus the behavior of H can be totally
ignored in any halt status decision. This eliminates the pathological
self-reference of the halting problem proof counter-example templates
making them decidable.

Scott Lurndal

unread,
Jul 7, 2021, 3:01:24 PMJul 7
to
olcott <No...@NoWhere.com> writes:
>On 7/7/2021 12:25 PM, Real Troll wrote:
>> On 07/07/2021 13:18, Bonita Montero wrote:
>>> According to your posting-frequency you're manic.
>>> But post only to comp.arch; this is the only appropriate NG.
>>> You don't have any C/C++-specific issues and your thoguhts
>>> aren't related to AI either.
>>
>> He wants to win a Nobel price in computing! He believes you can
>> recommend him to the Nobel committee for his incessant trolling.
>
>There is no Nobel prize in computing.

There is, of course, the Turing award.

But crossposting trolls aren't eligable.

olcott

unread,
Jul 7, 2021, 3:39:58 PMJul 7
to
I knew that and and also knew that Edsger Dijkstra won it four years
after he posted a mere letter to the editor to the CACM.

https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.pdf

https://en.wikipedia.org/wiki/Edsger_W._Dijkstra

olcott

unread,
Jul 7, 2021, 3:51:20 PMJul 7
to
On 7/7/2021 1:59 PM, wij wrote:
> I looked to me, you used two H's, one is local H, another is global H.
> If Local_H(P,P)!=Global_H(P,P), no need to discuss further.
>

No non-halting input can avoid being analyzed by the global (partial)
halt decider. Only programs that are input parameters to the local
(partial) halt decider H are analyzed by H.

>>> If H re-assign the T/F value of 'pathological input', H will still create another
>>> another set of undecidable input, H is doomed not a decisive function.
>>> [Hints]: H is function f:2^(2^|N|)->{0,1}, way beyond the capability of TM.
>>> Even if such a f is possible, the convention HP still true. H will still be an
>>> undecidable function.
>>>
>> Because H acts as a pure simulator of its input until after it makes its
>> halt status decision we know that the behavior of H cannot possibly have
>> any effect on the behavior of P thus the behavior of H can be totally
>> ignored in any halt status decision. This eliminates the pathological
>> self-reference of the halting problem proof counter-example templates
>> making them decidable.
>
> We know 'pure simulation' is not possible, H has to decide P is in an infinite
> loop or not and return an answer. Then, the question is how does H detect an infinite loop?

H acts are a pure simulator until the infinite loop behavior pattern is
detected in the simulation of its input. All of the details of this case
are shown in my paper.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

> Now, H(P,P)==0 is modified to include the meaning that "P is undecidable in
> the sense of the conventional HP".

When the pure simulation of a machine description on its input never
halts we know that the machine never halts on its input.

> By the convention HP proof, the same code example of P, this version of H will
> again fall in infinite loop, not able to return a correct answer.
>

H remains a pure simulator only until its input demonstrate non-halting
behavior. If its input never demonstrate non-halting behavior then H
remains a pure simulator.

olcott

unread,
Jul 7, 2021, 6:05:45 PMJul 7
to
On 7/7/2021 4:52 PM, Chris M. Thomasson wrote:
> On 7/7/2021 5:18 AM, Bonita Montero wrote:
>> According to your posting-frequency you're manic.
>
> Yeah, he sure seems to be suffering from some sort of mania, from time
> to time. Humm...
>
>
>> But post only to comp.arch; this is the only appropriate NG.
>> You don't have any C/C++-specific issues and your thoguhts
>> aren't related to AI either.
>

With every few posts my words become increasingly more clear and
undeniably correct. This only happens because of the feedback that I get
for these posts.

If you were Edison on the verge of invented the light bulb you would
probably continue with great vigor until you were done.

My words were clear enough to be understood as correct for months now,
by any expert software engineer highly skilled in C and x86 that was
highly motivated to understand what I am saying.

People that really really want me to be wrong will never acknowledge
that I am correct no matter how clear my words become. That seems to be
most everyone here.

olcott

unread,
Jul 7, 2021, 7:05:13 PMJul 7
to
On 7/7/2021 5:41 PM, wij wrote:
> I (and many) do wish you are right. But you don't have real proof, that is the fact.
>

I do have sound deductive inference which is a kind of proof.
Mike Terry incorrectly rejected what I have entirely on the basis that
it did not fit the pattern of a mathematical proof.


Premise(1) (Axiom) When the pure simulation of the machine description
⟨P⟩ of a machine P on its input I never halts we know that P(I) never
halts. This can be rephrased as every computation that never halts
unless its simulation is aborted is a computation that never halts.

Premise(2) (verified fact) The simulation of the input to H(P,P) never
halts without being aborted is a verified fact on the basis of its x86
execution trace.

When the simulator determines whether or not it must abort the
simulation of its input based on the behavior of its input the simulator
only acts as an x86 emulator thus has no effect on the behavior of its
input. This allows the simulator to always ignore its own behavior. H
simply screens out its own address range when making its halt status
decision.

Conclusion(3) From the above true premises it necessarily follows that
simulating halt decider H correctly reports that its input: (P,P) never
halts.

olcott

unread,
Jul 7, 2021, 9:15:37 PMJul 7
to
On 7/7/2021 7:26 PM, Richard Damon wrote:
> But, as you just admitted, H ISN'T a pure simulator, because is WILL at
> some point possible abort its simulation.
>
> When H abort its simulation, it affect the path of exection of the
> machine that called it,

I am only repeating this a ridiculous number of times because your
mental deficiency requires things to be repeated hundreds of times
before you notice them for the first time:




The behavior of H has no effect on the halt status decision
of H(P,P) because H remains a pure simulator of its input until
after the halt status decision has been made.

The behavior of H has no effect on the halt status decision
of H(P,P) because H remains a pure simulator of its input until
after the halt status decision has been made.

The behavior of H has no effect on the halt status decision
of H(P,P) because H remains a pure simulator of its input until
after the halt status decision has been made.

The behavior of H has no effect on the halt status decision
of H(P,P) because H remains a pure simulator of its input until
after the halt status decision has been made.

The behavior of H has no effect on the halt status decision
of H(P,P) because H remains a pure simulator of its input until
after the halt status decision has been made.

olcott

unread,
Jul 7, 2021, 9:24:50 PMJul 7
to
On 7/7/2021 7:18 PM, Richard Damon wrote:
> On 7/7/21 5:49 PM, olcott wrote:
>
>> As long as I show how the conventional halting problem counter-example
>> template is correctly decided as non-halting I have refuted these
>> proofs. You are one of two people in this forum that does not understand
>> that.
>>
>
> Except that you haven't proved any such thing, as given an H that does
> abort the Linz H^ template, it is trivial to show that H^ does halt.
>
> PERIOD.
>
> DEFINITION.
>
> END OF ARGUMENT.
>

We know that every black cat is a cat that is black even if this black
cat barks.

[Axiom] When the pure simulation of the machine description ⟨P⟩ of a
machine P on its input I never halts we know that P(I) never halts.

Every input that never halts while the simulating halt decider remains a
pure simulator is an input that never halts.

olcott

unread,
Jul 7, 2021, 9:31:47 PMJul 7
to
On 7/7/2021 7:17 PM, Richard Damon wrote:
> On 7/7/21 3:51 PM, olcott wrote:
>>
>> No non-halting input can avoid being analyzed by the global (partial)
>> halt decider. Only programs that are input parameters to the local
>> (partial) halt decider H are analyzed by H.
>
> Then you are working in a non-Turing Complete computational environment,
> and thus NONE of your proofs matter, because you don't have REAL Turing
> Machines.

So if the the halt decider is a Universal Turing machine (UTM) that
simulates the execution of its inputs as the basis for its halting
decision then this is not based on a real Turing machine?

Is sounds to me like you are trying to say that some black cats are not
cats that are black.

olcott

unread,
Jul 7, 2021, 10:04:07 PMJul 7
to
On 7/7/2021 8:45 PM, Richard Damon wrote:
> On 7/7/21 9:24 PM, olcott wrote:
>> On 7/7/2021 7:18 PM, Richard Damon wrote:
>>> On 7/7/21 5:49 PM, olcott wrote:
>>>
>>>> As long as I show how the conventional halting problem counter-example
>>>> template is correctly decided as non-halting I have refuted these
>>>> proofs. You are one of two people in this forum that does not understand
>>>> that.
>>>>
>>>
>>> Except that you haven't proved any such thing, as given an H that does
>>> abort the Linz H^ template, it is trivial to show that H^ does halt.
>>>
>>> PERIOD.
>>>
>>> DEFINITION.
>>>
>>> END OF ARGUMENT.
>>>
>>
>> We know that every black cat is a cat that is black even if this black
>> cat barks.
>
> STRAW MAN.
>>
>> [Axiom] When the pure simulation of the machine description ⟨P⟩ of a
>> machine P on its input I never halts we know that P(I) never halts.
>>
>> Every input that never halts while the simulating halt decider remains a
>> pure simulator is an input that never halts.
>>
>
> But a decider that eventually halts a simulation is NOT a simulator that
> NEVER halts. It doesn't matter that it waits until after it has made its
> decision, the problem is it hasn't waited until after the simulator it
> is simulating has made its decision, and THAT is what really counts.
>

I thought this same thing for three days until I figured out that unless
the current halt decider aborts its input that no halt decider ever will
abort its input.

olcott

unread,
Jul 7, 2021, 10:07:44 PMJul 7
to
On 7/7/2021 8:51 PM, Richard Damon wrote:
> On 7/7/21 9:31 PM, olcott wrote:
>> On 7/7/2021 7:17 PM, Richard Damon wrote:
>>> On 7/7/21 3:51 PM, olcott wrote:
>>>>
>>>> No non-halting input can avoid being analyzed by the global (partial)
>>>> halt decider. Only programs that are input parameters to the local
>>>> (partial) halt decider H are analyzed by H.
>>>
>>> Then you are working in a non-Turing Complete computational environment,
>>> and thus NONE of your proofs matter, because you don't have REAL Turing
>>> Machines.
>>
>> So if the the halt decider is a Universal Turing machine (UTM) that
>> simulates the execution of its inputs as the basis for its halting
>> decision then this is not based on a real Turing machine?
>
>
> If your decider IS a UTM, then it must never halt a non-halting
> computation, and thus doesn't answer for H^.
>

So damned nit picky. The freaking halt decider is freaking based on a
freaking UTM.

> If there is a GLOBAL halt decider in your computational environment that
> aborts supposed Turing Machines that are NOT being run under your Halt
> Decider, then your computational environment is NOT Turing Complete, and
> thus you can't use it to argue about Turing Machines.
>

In the environment that I propose it is not possible for any input to
avoid halt deciding analysis.

>> Is sounds to me like you are trying to say that some black cats are not
>> cats that are black.
>>
>
> No, I am saying that the presence of a global halt decider in your
> system means you aren't allowing all 'cats' to exist, and in particular,
> it is disallowing one of the machines specifically called out in the
> proof you are working on because the global decider is BROKEN.
>

How so?

olcott

unread,
Jul 8, 2021, 8:47:03 AMJul 8
to
On 7/8/2021 5:56 AM, Richard Damon wrote:
> On 7/7/21 11:03 PM, olcott wrote:
>
>> The behavior of H has no effect on the halt status decision
>> of H(P,P) because H remains a pure simulator of its input until
>> after the halt status decision has been made.
>>
>
> Maybe it doesn't affect the decision that H makes, but it should, as it
> does affect the behavior of P.
>

A pure simulator has no effect on the behavior of its input thus no
effect on its own halt status decision. Only after the simulating halt
decider has already made its halt status decision does it switch to
modes and abort the simulation of its input.

> Can be clearly shown. Create one H that always returns 0, another that
> always return 1
>
> Compare.
>
> Obviously, H affect the behavior of P.
>
> PERIOD.
>
> Obviously your logic is wrong.
>
> Now, maybe the behavior of H doesn't affect what H decides, but then
> THAT is the source of the problem, it should.
>

Pathological self-reference is an error that must be removed.
When studying the effect of an independent variable on a dependent
variable the results are tainted when the dependent variable has any
feedback loop to the independent variable.

https://www.scribbr.com/methodology/independent-and-dependent-variables/

While H is studying the behavior of P if H has any effect on the
behavior of P the results are tainted.

olcott

unread,
Jul 8, 2021, 9:30:02 AMJul 8
to
On 7/8/2021 6:02 AM, Richard Damon wrote:
> On 7/7/21 11:04 PM, olcott wrote:
>> On 7/7/2021 9:51 PM, Richard Damon wrote:
>
>>> Because The Halting Problem proof is based on a machine that that can be
>>> given ANY Turing Machine, If you environment happens to disallow certain
>>> machines, and that machine happens to be the machine H^, then you proof
>>> isn't valid.It is quite possible to write a Turing Equivalent machine to
>>> halt decide many different sorts of non-Turing complete systems, so you
>>> aren't really proving anything new.
>>>
>>
>> Where the Hell did you get the idea that this machine disallows any input?
>>
>>
>
> Sine your system does not proper execute any machine that it thinks in
> an infinite behavior,

H does not execute any machines that never halt until they halt because
they never halt.

> These machines don't exist as proper Turing Machines.
>

There is nothing improper about them.

> Particularly since it gets some machines (like H^(H^)) wring.
>
> H^(H^) is EASILY proved to be halting for your H from fundamental
> principles, thus your system is broken.
>

The global halt decider would abort H(⟨Ĥ⟩, ⟨Ĥ⟩) its input before its
input ever reached either final state.

H and the embedded halt decider are both designed to abort their input
as soon as they detect that the pure simulation of their input would
never halt. A global halt decider is always one step ahead of any input.
A local halt decider is sometimes one step behind its input.

The issue of a computation halting even though the halt decider decides
that it never halts is an issue of timing.

The halt decider is only required to get its inputs correctly. If the
later part of a non-halting computation is presented to the halt decider
it does what it is supposed to do and aborts this input.

It can't do anything with the earlier part because the earlier part was
not submitted as input. A global halt decider eliminates this issue.

olcott

unread,
Jul 8, 2021, 12:24:16 PMJul 8
to
On 7/8/2021 11:07 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> We can know that my halt deciding criteria is the same as the halting
>> problem halt deciding...
>
> We can know it isn't because you said it isn't:
>
> "This maps to every element of the conventional halting problem set of
> non-halting computations *and a few more*." (emphasis mine)
>

My earlier statement is corrected below:

[Axiom] When the pure simulation of the machine description ⟨P⟩ of a
machine P on its input I never halts we know that P(I) never halts.

The second half of above criteria is the same criteria that the
conventional halting problem proofs use. It is known to be
computationally equivalent to the first half.

When we apply the first half of that criteria to the set of halting
computations using a simulating halt decider it decides that they halt.

When we apply the first half of that criteria to the set of non-halting
computations using a simulating halt decider it decides that they do not
halt.

When we apply the first half of that criteria to the set of halting
problem proof counter-example templates using a simulating halt decider
it decides that they do not halt.

olcott

unread,
Jul 8, 2021, 9:07:37 PMJul 8
to
On 7/8/2021 5:52 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/8/2021 11:07 AM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> We can know that my halt deciding criteria is the same as the halting
>>>> problem halt deciding...
>>> We can know it isn't because you said it isn't:
>>> "This maps to every element of the conventional halting problem set of
>>> non-halting computations *and a few more*." (emphasis mine)
>>
>> My earlier statement is corrected below:
>
> So right up until a few days ago you knew your "adapted" criterion
> defined different accept and reject set to the halting problem and you
> were just pretending they were the same.
>

The words have continually gotten clearer in my mind.

[Halt Deciding Axiom] When the pure simulation of the machine
description ⟨P⟩ of a machine P on its input I never halts we know that
P(I) never halts. Every input that never halts while the simulating halt
decider remains a pure simulator is an input that never halts.

A non-halting input is an input that would never halt without
interference by the simulating halt decider. If the halt decider merely
watches what the input program does and can see that it will never halt,
then it can stop simulating this input and report that it never halts.

The key thing here is that the pathological self-reference(olcott 2004)
is eliminated from the halting problem when the simulating halt decider
simply watches what its input does without any interference
what-so-ever. When the simulating halt decider does this then it can
ignore its own behavior in its halt status analysis, thus eliminating
the confounding feedback loop.

Halting Problem Final Conclusion
Peter Olcott Sep 5, 2004, 11:21:57 AM

The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ


> But now the two criteria (yours and halting) really do define exactly
> the same sets, yes? So we can just forget about all your fiddly
> definitions using simulations and waffle and use the usual criterion,
> yes? I'd really like a non-waffle answer to this. If your halting is
> now what the world means by halting you need to say so.
>
> So rather than being right about the POOH problem you are just wrong
> about halting, right? Do you now, after more than 20 years, accept that
> every input to the halting problem has a correct yes/no answer and that
> yes is the correct answer only for those inputs that represent halting
> computations, and no is the correct answer for the rest?
>
> (Expecting a direct answer to any of these questions is the triumph of
> hope over experience.)

olcott

unread,
Jul 8, 2021, 10:21:28 PMJul 8
to
On 7/8/2021 8:48 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/8/2021 5:52 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 7/8/2021 11:07 AM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> We can know that my halt deciding criteria is the same as the halting
>>>>>> problem halt deciding...
>>>>> We can know it isn't because you said it isn't:
>>>>> "This maps to every element of the conventional halting problem set of
>>>>> non-halting computations *and a few more*." (emphasis mine)
>>>>
>>>> My earlier statement is corrected below:
>>> So right up until a few days ago you knew your "adapted" criterion
>>> defined different accept and reject set to the halting problem and you
>>> were just pretending they were the same.
>>
>> The words have continually gotten clearer in my mind.
>
> So you have not changed the meaning, only clarified the expression. The
> two criteria, yours and halting, do define different accept/reject sets
> as you said explicitly in the quote I posted.
>

[Halt Deciding Axiom] When the pure simulation of the machine
description ⟨P⟩ of a machine P on its input I never halts we know that
P(I) never halts. This is a conventional axiom.

When the simulating halt decider has detected that the pure simulation
of its input ⟨P⟩ never halts on its input I it has detected an instance
an input that never halts according to the above purely conventional axiom.

> So which of your statements is the one you want to stand by?
>
> "We can know that my halt deciding criteria is the same as the halting
> problem"
>
> or
>
> "This maps to every element of the conventional halting problem set of
> non-halting computations and a few more."
>
> It should be obvious to others why this is the fence you are sitting on.
> Is it comfy?
>
The first one. When we apply the conventional halt deciding criteria to
the halting problem counter-example templates using a simulating halt
decider, the simulating halt decider can correctly decide halting on
these inputs because it can totally ignore its own behavior while it
acts as a pure simulator, thus eliminating the pathological
self-reference(Olcott 2004) from the halting problem.

comp.theory Peter Olcott Sep 5, 2004, 11:21:57 AM
[Halting Problem Final Conclusion]
The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

17 years later I am finally getting around to finishing this.

You have been talking to me far longer than anyone else, since 2006:

[Re: A Possible "solution" to the Halting Problem]
On 10/17/2006 7:03 PM, Ben Bacarisse wrote:

olcott

unread,
Jul 8, 2021, 10:36:39 PMJul 8
to
To eliminate the pathological self-reference(Olcott 2004) from the
halting problem such that there is no feedback loop between what the
halt decider decides and how the input behaves the simulating halt
decider simply watches what the input does without interfering at all.

As soon as the simulating halt decider determines that the simulation of
the input on its input would never halt (the conventional definition of
non-halting) it aborts the simulation of its inputs and reports that its
input does not halt.

olcott

unread,
Jul 8, 2021, 11:54:55 PMJul 8
to
On 7/8/2021 10:39 PM, Richard Damon wrote:
> On 7/8/21 8:46 AM, olcott wrote:
>> On 7/8/2021 5:56 AM, Richard Damon wrote:
>>> On 7/7/21 11:03 PM, olcott wrote:
>>>
>>>> The behavior of H has no effect on the halt status decision
>>>> of H(P,P) because H remains a pure simulator of its input until
>>>> after the halt status decision has been made.
>>>>
>>>
>>> Maybe it doesn't affect the decision that H makes, but it should, as it
>>> does affect the behavior of P.
>>>
>>
>> A pure simulator has no effect on the behavior of its input thus no
>> effect on its own halt status decision. Only after the simulating halt
>> decider has already made its halt status decision does it switch to
>> modes and abort the simulation of its input.
>
> Except the copy of H you are simulating WILL affect the program that
> called it that you are also simulating, so you need to simulate it until
> it makes its decision. You keep on conflating the simulator with the
> program it is simulting.
>

The behavior of the simulating halt decider cannot possibly have any
effect on its halt status decision because it always makes sure to
ignore every machine address of its own address range while it is making
its halt status decision.

Every invocation of H in the nested simulation chain can totally ignore
the behavior of every H while every invocation of H is only acting as a
pure simulator.

To eliminate the pathological self-reference(Olcott 2004) from the
halting problem such that there is no feedback loop between what the
halt decider decides and how the input behaves the simulating halt
decider simply watches what the input does without interfering at all.

If the simulating halt decider's behavior cannot possibly have any
effect on the behavior of its input then its input cannot possibly do
the opposite of whatever the halt decider decides thus eliminating the
halting problem paradox.



>>
>>> Can be clearly shown. Create one H that always returns 0, another that
>>> always return 1
>>>
>>> Compare.
>>>
>>> Obviously, H affect the behavior of P.
>>>
>>> PERIOD.
>>>
>>> Obviously your logic is wrong.
>>>
>>> Now, maybe the behavior of H doesn't affect what H decides, but then
>>> THAT is the source of the problem, it should.
>>>
>>
>> Pathological self-reference is an error that must be removed.
>> When studying the effect of an independent variable on a dependent
>> variable the results are tainted when the dependent variable has any
>> feedback loop to the independent variable.
>
> WHY? What is wrong with self reference? You seem to have your variables
> backwards. The algorithm of H is your independent variable, and there is
> no feedback loop that changes that algorithm. By varing that you see
> what answers H gives and what P does. Neither of these feedback to
> change your alogirthm of H except as you work to try to 'optimize' the
> answer to be more right.
>
>>
>> https://www.scribbr.com/methodology/independent-and-dependent-variables/
>>
>> While H is studying the behavior of P if H has any effect on the
>> behavior of P the results are tainted.
>>
>
> But P is BY DEFINITION a function of H if you use the Linz construction,
> so that means you have chosen a wrong method.

olcott

unread,
Jul 9, 2021, 10:00:04 AMJul 9
to
On 7/9/2021 6:30 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/8/2021 8:48 PM, Ben Bacarisse wrote:
>
>>> So which of your statements is the one you want to stand by?
>>>
>>> "We can know that my halt deciding criteria is the same as the halting
>>> problem"
>>> or
>>> "This maps to every element of the conventional halting problem set of
>>> non-halting computations and a few more."
>>>
>>> It should be obvious to others why this is the fence you are sitting on.
>>> Is it comfy?
>>>
>> The first one.
>
> Thank you. Your directness make me hopeful that you'll be clear about
> some other things... How long have you though that "and a few more" was
> correct? I.e. how long have you been arguing for a position you now
> concede is mistaken? Months? Years? Decades?
>

I have only been trying to specifically define the set that are involved
for a few days. comp.theory gets all of my newest material before I put
it in my paper.

> You have refused to accept the definition of the halting problem for
> decades. Do you now accept that every string has a correct yes/no
> answer as far as halting is concerned, and that "yes" is the correct
> answer for those strings that represent halting computations and "no" is
> the correct answer for all the others?
>

The question: What Boolean value can H return to P representing the
correct halt status of P(P) in this computation has no correct answer:

// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}

int main()
{
u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}

You always consistently twist these words to say something else entirely
knowing full well that you twist these words.

In the same way that the Liar Paradox contradicts its own truth value
the halting problem counter-example templates contradict the return
value of some programs that would otherwise be halt deciders.

The Liar Paradox and the halting problem counter example templates have
the exact same pathological self-reference(Olcott 2004) error.

comp.theory Peter Olcott Sep 5, 2004, 11:21:57 AM
[Halting Problem Final Conclusion]
The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

> And since we now know that your "halt deciding criteria is the same as
> the halting problem" we can ditch all the waffle about simulation. It's
> just halting as conventionally defined.
>

[Halt Deciding Axiom] When the pure simulation of the machine
description ⟨P⟩ of a machine P on its input I never halts we know that
P(I) never halts.

No we cannot. In order to remove the pathological feedback loop such
that P does the opposite of whatever H decides H simply acts as a pure
simulator of P thus having no effect what-so-ever on the behavior of P
until after its halt status decision has been made.

H then aborts its simulation of P before ever returning any value to P
because every function called in infinite recursion or infinitely nested
simulation never returns to this caller.

> Your favourite book, and your favourite quoted lines from it, make it
> quite clear that halting computations like P(P) need to be accepted not
> rejected. P(P) halts, but H(P,P) == 0 which is wrong. So what have you
> now after all this time except a huge mistake?
>

Because the pure simulation of P(P) never halts this proves that P(P)
meets the conventional definition of a computation that never halts.

olcott

unread,
Jul 9, 2021, 10:02:12 AMJul 9
to
On 7/9/2021 4:53 AM, Richard Damon wrote:
> On 7/9/21 12:27 AM, olcott wrote:
>> On 7/8/2021 11:05 PM, Richard Damon wrote:
>>> And thus your system can not be used to figure out if H is correct or
>>> not, because it stops the machine before the answer is REALLY proven.
>>>
>>>>
>>>> H and the embedded halt decider are both designed to abort their input
>>>> as soon as they detect that the pure simulation of their input would
>>>> never halt. A global halt decider is always one step ahead of any input.
>>>> A local halt decider is sometimes one step behind its input.
>>>>
>>>> The issue of a computation halting even though the halt decider decides
>>>> that it never halts is an issue of timing.
>>>>
>>>> The halt decider is only required to get its inputs correctly. If the
>>>> later part of a non-halting computation is presented to the halt decider
>>>> it does what it is supposed to do and aborts this input.
>>>>
>>>> It can't do anything with the earlier part because the earlier part was
>>>> not submitted as input. A global halt decider eliminates this issue.
>>>>
>>>
>>> Right, The global decider says that a machine that WOULD come to a HALT
>>> if let run, gets aborted and not allowed to finish, thus it is WRONG, as
>>> the computation is REALLY HALTING, because if given enough (but still a
>>> finite number) of step, it would halt.
>>>
>>
>> I can discard the global halt deicider again.
>>
> It has ALWAYS been a failure, because it immediately make your system
> unsuitable for your proof.
>
> Removing it doesn't make your statement right, but at least you start
> with something you can talk about being able to run Turing Machine
> Equivalents.
>
> Without the Global Halt Decider, we can talk about what P(P) actually
> does, which is a required part of the proof, since that is what the
> question is about.
>

[Halt Deciding Axiom] When the pure simulation of the machine
description ⟨P⟩ of a machine P on its input I never halts we know that
P(I) never halts.

Because the pure simulation of P(P) never halts this proves that P(P)
meets the conventional definition of a computation that never halts.

Mr Flibble

unread,
Jul 9, 2021, 1:06:45 PMJul 9
to
On Fri, 9 Jul 2021 08:59:51 -0500
olcott <No...@NoWhere.com> wrote:
> [Halt Deciding Axiom] When the pure simulation of the machine
> description ⟨P⟩ of a machine P on its input I never halts we know
> that P(I) never halts.
>
> No we cannot. In order to remove the pathological feedback loop such
> that P does the opposite of whatever H decides H simply acts as a
> pure simulator of P thus having no effect what-so-ever on the
> behavior of P until after its halt status decision has been made.

Except your decider can only handle trivial uninteresting cases: if you
wish to make progress on this then prove your decider works with a
non-trivial case which includes branching logic predicated on arbitrary
program input that is unknown a priori to the simulation starting; but
before you even do that prove your decider works with a non-trivial
case with branching logic predicated on arbitrary program input that
*is* known a priori.

I also note that you repeatedly refuse to address my point regarding how
x86 mov instructions can read/write from/to memory mapped I/O
rather than RAM so the result of the mov instruction cannot be known a
priori. The halting program concerns computing devices and a computing
device which cannot do I/O is next to useless, much like your decider
(until you actually prove otherwise which I have a feeling is never
going to happen as you appear to be stuck in a loop).

/Flibble

olcott

unread,
Jul 9, 2021, 1:47:20 PMJul 9
to
On 7/9/2021 12:06 PM, Mr Flibble wrote:
> On Fri, 9 Jul 2021 08:59:51 -0500
> olcott <No...@NoWhere.com> wrote:
>> [Halt Deciding Axiom] When the pure simulation of the machine
>> description ⟨P⟩ of a machine P on its input I never halts we know
>> that P(I) never halts.
>>
>> No we cannot. In order to remove the pathological feedback loop such
>> that P does the opposite of whatever H decides H simply acts as a
>> pure simulator of P thus having no effect what-so-ever on the
>> behavior of P until after its halt status decision has been made.
>
> Except your decider can only handle trivial uninteresting cases: if you
> wish to make progress on this then prove your decider works with a
> non-trivial case which includes branching logic predicated on arbitrary
> program input that is unknown a priori to the simulation starting; but
> before you even do that prove your decider works with a non-trivial
> case with branching logic predicated on arbitrary program input that
> *is* known a priori.
>

You continue to prove to everyone that actually knows these things that
you are an ignoramus on this subject.

That H correctly decides that all of the standard counter-examples
templates never halt eliminates the entire basis of all of the
conventional halting problem undecidability proofs.

> I also note that you repeatedly refuse to address my point regarding how
> x86 mov instructions can read/write from/to memory mapped I/O
> rather than RAM so the result of the mov instruction cannot be known a
> priori. The halting program concerns computing devices and a computing
> device which cannot do I/O is next to useless, much like your decider
> (until you actually prove otherwise which I have a feeling is never
> going to happen as you appear to be stuck in a loop).
>
> /Flibble
>


Mr Flibble

unread,
Jul 9, 2021, 3:16:41 PMJul 9
to
I continue to note that you repeatedly refuse to address my point

olcott

unread,
Jul 9, 2021, 3:24:41 PMJul 9
to
You are the only one that believes that your points have any relevance.
That you believe that data movement instructions have anything to do
with control flow proves that your points have no relevance.

Mr Flibble

unread,
Jul 9, 2021, 5:08:09 PMJul 9
to
On Fri, 9 Jul 2021 14:24:33 -0500
You literally have no clue about what you are talking about,
whatsoever. This explains everything.

/Flibble

olcott

unread,
Jul 9, 2021, 5:13:56 PMJul 9
to
*Make sure that you read all of this especially the last line*

halt (p, i)
{
if ( program p halts on input i )
return true ; // p halts
else
return false ; // p doesn’t halt
}
Fig. 1. Pseudocode of the Halting Function

Strachey’s Impossible Program Strachey proposed a program
based on the result of an assumed halting function [2].
The way Strachey’s construction and other similar constructions
are used to show the impossibility of a decideable halting
function is quite similar to Turing’s original disproof.
But the relevant difference we want to emphasize is that
they do not explicitly assume an infinite number of possible
machines (programs) or input data, because they directly use
reductio ad absurdum to prove that both, Strachey’s construction
and the universal halting function cannot exist.

strachey ( p )
{
if ( halt (p, p) == true )
L1 : goto L1 ; // loop forever
else
return;
}

Fig. 2. Strachey’s Impossible Program

The impossibility of Strachey’s construction given in Figure 2 becomes
obvious if one tries to apply the halting function as follows:

halt(strachey, strachey)

Since in this case strachey() itself calls halt(strachey, strachey),
it is required that the direct call of halt() and the nested call
provide the same result. However, this leads to a contradiction,
whatever result halt() returns. Within this disproof there seems
to be no indication why not it could be even applied to finite-state
systems having a concrete upper bound of state space.

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.206.1468&rep=rep1&type=pdf

olcott

unread,
Jul 9, 2021, 6:29:26 PMJul 9
to
On 7/9/2021 4:59 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/9/2021 6:30 AM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 7/8/2021 8:48 PM, Ben Bacarisse wrote:
>>>
>>>>> So which of your statements is the one you want to stand by?
>>>>>
>>>>> "We can know that my halt deciding criteria is the same as the halting
>>>>> problem"
>>>>> or
>>>>> "This maps to every element of the conventional halting problem set of
>>>>> non-halting computations and a few more."
>>>>>
>>>>> It should be obvious to others why this is the fence you are sitting on.
>>>>> Is it comfy?
>>>>>
>>>> The first one.
>>> Thank you. Your directness make me hopeful that you'll be clear about
>>> some other things... How long have you though that "and a few more" was
>>> correct? I.e. how long have you been arguing for a position you now
>>> concede is mistaken? Months? Years? Decades?
>>
>> I have only been trying to specifically define the set that are
>> involved for a few days.
>
> I wrote something about this but deleted it since it turns out, further
> down, you are still sitting on the fence.
>
>>> You have refused to accept the definition of the halting problem for
>>> decades. Do you now accept that every string has a correct yes/no
>>> answer as far as halting is concerned, and that "yes" is the correct
>>> answer for those strings that represent halting computations and "no" is
>>> the correct answer for all the others?
>>
>> The question: What Boolean value can H return to P representing the
>> correct halt status of P(P) in this computation has no correct answer:
>
> You seem to think that because every H gets at least one case wrong (the
> one designed to confound it) that this means that there is no correct
> answer to every halting instance. That is wrong, and until you realise
> that, you are not going to make any progress.
>
> For any two-argument Boolean function H, there is a corresponding
> function hat(H). The computation hat(H)(hat(H)) either halts or it does
> not, so that computation has a correct answer as to its halting. The
> fact that no H gives the right answer for its own personal Nemesis,
> hat(H)(hat(H)), does not mean there isn't one in every single case.
>
> We even know what it is for your H (despite the fact that you a
> studiously hiding the code), because you have stated, and posted a trace
> showing, what actually happens! P (your current name for the 'hat'
> version of H) halts when passed P. This is why H(P,P) == 0 is wrong.
>
>> // Simplified Linz Ĥ (Linz:1990:319)
>> void P(u32 x)
>> {
>> u32 Input_Halts = H(x, x);
>> if (Input_Halts)
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> u32 Input_Halts = H((u32)P, (u32)P);
>> Output("Input_Halts = ", Input_Halts);
>> }
>>
>> You always consistently twist these words to say something else
>> entirely knowing full well that you twist these words.
>
> You are correctly explaining that H is wrong about P(P). How can it be
> put any more simply?

The reason that H cannot return the correct halt status to P is that
this TM / input pair was intentionally modeled on the basis of the liar
paradox.

The liar paradox is not a truth bearer because it is self-contradictory.
Any expression of formal or natural language that is not a truth bearer
has no associated Boolean value.

The halting problem counter-example (prior to my insights) had no
associated Boolean value specifically because most of the details are
always unspecified.

When we ask the specific question: What correct value of {true, false}
can H correctly return to P that indicates the actual halt status of P?

(The answer is restricted to Boolean, the answer of "neither" is not
allowed).

This 100% specific question <is> as I have always said exactly the same
type mismatch error as asking the question: What time is it (yes or no)?

> How is that twisting your words? Surely you don't
> deny that, since P(P) halts, there is a correct answer as to whether
> P(P) halts or not?
>
> The halting problem is about deciding if a computation -- some code and
> some input -- halts or not. For a halt decider, H, to be correct
>
> H(P,I) != 0 if and only if P(I) halts and
> H(P,I) != 1 if and only if P(I) does not halt.
>
> In particular, the facts that H(P,P) == 0 and P(P) halts (facts you
> don't deny) show that H is not a halt decider. I know you never claimed
> it was (except by accident), but you do claim it is right about P(P).
> It is not.
>
> I think you consider my refusal to anthropomorphise code as "twisting
> your words". If you rephrased it in terms of the programmer, I'd just
> agree. Given bool H(code P, data I) {...}, what code can a programmer
> write in the brackets so that H(P,P) is correct? Answer: none. There
> is no code that can "get round" the construction of P from H.
>
>>> And since we now know that your "halt deciding criteria is the same as
>>> the halting problem" we can ditch all the waffle about simulation. It's
>>> just halting as conventionally defined.
>
>> No we cannot.
>
> Nonsense. Despite apparently being clear that your "and a few more" was
> wrong, you are sticking by it. H(P,I) == 0 is "correct" when P(I) does
> not halt, and for a few more cases (like P(P) which halts).
>

int main() { P(P); } does not count as halting even though its stops
running in the same way that Infinite_loop() does not count as halting
when the simulator aborts its simulation.

When H simply simulates its input and never interferes with the behavior
of its input H can screen out its own address range from the execution
trace that it examines as the basis for its halt status decision.

The set of halting computations halt on their own without interference.

The set of not halting computations do not halt on their own without
interference.

> If your waffle "halting" definition is the same as halting, there would
> be no need for it at all. Your apparently clear answer above ("the
> first one") is either a lie or the result of some deep self-deception on
> your part.
>
>> In order to remove the pathological feedback loop such that P does the
>> opposite of whatever H decides H simply acts as a pure simulator of P
>> thus having no effect what-so-ever on the behavior of P until after
>> its halt status decision has been made.
>>
>> H then aborts its simulation of P before ever returning any value to P
>> because every function called in infinite recursion or infinitely
>> nested simulation never returns to this caller.
>
> P(P) halts. H(P,P) == 0 is wrong when P(P) halts. Whatever all your
> guff really means, it is not the same as halting. You are not
> addressing the halting problem.
>
>>> Your favourite book, and your favourite quoted lines from it, make it
>>> quite clear that halting computations like P(P) need to be accepted not
>>> rejected. P(P) halts, but H(P,P) == 0 which is wrong. So what have you
>>> now after all this time except a huge mistake?
>>
>> Because the pure simulation of P(P) never halts this proves that P(P)
>> meets the conventional definition of a computation that never halts.
>
> P(P) halts. It does not meet the conventional definition of a
> computation that never halts. Your words are nonsense of the first
> order.

olcott

unread,
Jul 9, 2021, 7:32:00 PMJul 9
to
On 7/9/2021 6:23 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
> Please stop putting back irrelevant groups. You are not a tom cat.
> There is not need to spray everywhere.
> At least you agree, then that H(P,P) is wrong since P(P) halts. Good.
>
>> The halting problem counter-example (prior to my insights) had no
>> associated Boolean value specifically because most of the details are
>> always unspecified.
>
> Flat-out wrong. P(P) halts. The correct associated Boolean value is
> true. If you write some other H', the resulting hat(H')(hat(H'))
> computation might not halt so the correct associated Boolean value would
> be false. There is always a correct associated Boolean value describing
> the halting of every computation, despite the fact that there is no
> function that gets the corresponding 'hat' case right.
>
>> When we ask the specific question: What correct value of {true, false}
>> can H correctly return to P that indicates the actual halt status of
>> P?
>>
>> (The answer is restricted to Boolean, the answer of "neither" is not allowed).
>>
>> This 100% specific question <is> as I have always said exactly the
>> same type mismatch error as asking the question: What time is it (yes
>> or no)?
>
> But your 100% specific question is not an instance of the halting
> problem. It's a related question about what is possible in code, and we
> know the answer -- no code can decide halting. It's odd that your
> defence includes such a robust argument that the halting theorem is
> correct.
>
> That every bit of code, no matter how simple or how subtle, is wrong
> about some inputs is just a statement of the halting theorem. That all
> inputs have a correct yes/no answer is just a statement of fact.
> P(P) halts. If you don't "count" all halting computations as halting
> you are talking nonsense.
>

A computation that stops running because it has been aborted is as
Richard put it suspended, and not halted.

> Remember, you have relinquished your right to make up a definition of
> what halting is. You've been clear that you intend "halting" to refer
> to the conventional meaning of the term as used in the halting problem.
> If you are unsure about what counts, you need to ask experts what counts
> as halting. And when people like me tell you what counts, you have to
> suck it up. Halting is not a mysterious concept.
>

When-so-ever the pure simulation of an input on its input never halts
then this input never halts.

When-so-ever any input to H never halts while H remains a pure simulator
then we know this input never halts.

int main() { P(P); } never halts while H remains a pure simulator.

olcott

unread,
Jul 9, 2021, 8:33:16 PMJul 9
to
On 7/9/2021 7:13 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/9/2021 6:23 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>
>>> Please stop putting back irrelevant groups. You are not a tom cat.
>>> There is not need to spray everywhere.
>
> Please take note. There is no need to be rude as well as wrong.
>
>>>> On 7/9/2021 4:59 PM, Ben Bacarisse wrote:
>
>>>>> ... Despite apparently being clear that your "and a few more"
>>>>> was wrong, you are sticking by it. H(P,I) == 0 is "correct" when
>>>>> P(I) does not halt, and for a few more cases (like P(P) which halts).
>>>>
>>>> int main() { P(P); } does not count as halting even though its stops
>>>> running in the same way that Infinite_loop() does not count as halting
>>>> when the simulator aborts its simulation.
>>>
>>> P(P) halts. If you don't "count" all halting computations as halting
>>> you are talking nonsense.
>>
>> A computation that stops running because it has been aborted is as
>> Richard put it suspended, and not halted.
>
> I see you don't want to discuss any of the above so I've cut it all and
> I'll keep my replies short. No point in writing explanations just for
> you to ignore.
>
> P(P) halts. It counts. You don't get to say that some halting does not
> count (until you go back to admitting that you are not talking about the
> halting problem when you can make up any old dross you like).
>
>>> Remember, you have relinquished your right to make up a definition of
>>> what halting is. You've been clear that you intend "halting" to refer
>>> to the conventional meaning of the term as used in the halting problem.
>>> If you are unsure about what counts, you need to ask experts what counts
>>> as halting. And when people like me tell you what counts, you have to
>>> suck it up. Halting is not a mysterious concept.
>>
>> When-so-ever the pure simulation of an input on its input never halts
>> then this input never halts.
>>
>> When-so-ever any input to H never halts while H remains a pure
>> simulator then we know this input never halts.
>
> You have stated your intention that whatever waffle you write about
> simulation, you intend it to capture exactly the same meaning as
> conventional halting. Until you go back to being honest, and admit you
> are not talking about the halting problem as the world understands it, I
> can safely ignore all of your clumsy attempts at a definition because
> they are supposed to mean what everyone else means by halting.
>
>> int main() { P(P); } never halts while H remains a pure simulator.
>
> For some H to be correct
>
> H(P,I) != 0 if and only if P(I) halts and
> H(P,I) != 1 if and only if P(I) does not halt.
>
> If H is a pure simulator it will not meet this specification. But your
> H is not a pure simulator. It is simply wrong about P(P). It is wrong
> based in fact you have reported: that H(P,P) == 0 and that P(P) halts.
> Whatever H you come up with, it will be wrong about some inputs. That's
> what an impossible program is.
>

Simulating halt decider H is only answering the question:
Would the input halt on its input if H never stopped simulating it?

An answer of "no" universally means that the input never halts.

An answer of "yes" universally means that the input halts.

[Halt Deciding Axiom] When the pure simulation of the machine
description ⟨P⟩ of a machine P on its input I never halts we know that
P(I) never halts.


olcott

unread,
Jul 9, 2021, 11:18:43 PMJul 9
to
On 7/9/2021 9:39 PM, André G. Isaak wrote:
> On 2021-07-09 17:31, olcott wrote:
>> On 7/9/2021 6:23 PM, Ben Bacarisse wrote:
>
>>> P(P) halts.  If you don't "count" all halting computations as halting
>>> you are talking nonsense.
>>>
>>
>> A computation that stops running because it has been aborted is as
>> Richard put it suspended, and not halted.
>
> Yes, but when P(P) is run independently there is nothing which can
> suspend this computation because it isn't being run in a simulator.
>

What everyone consistently ignores is that only the prefix of the
computation runs independently. If the suffix of this computation was
not aborted then P(P) would never halt.

Simulating halt decider H is only answering the question:
Would the input halt on its input if H never stopped simulating it?
(a) An answer of "no" universally means that the input never halts.
(b) An answer of "yes" universally means that the input halts.

Halt Deciding Axiom: When the pure simulation of the machine description
⟨P⟩ of a machine P on its input I never halts we know that P(I) never
halts.

> In this case, the outermost P is the computation which is being
> performed and acts as the simulator. The innermost P is the input which
> is being simulated. The inner P might get suspended by the outer P, but
> the outer P can't be suspended. It simply *halts*.
>
> André
>
>

No P ever halts unless some P is aborted, thus P(P) is accurately
construed as specifying infinitely nested simulation.

olcott

unread,
Jul 10, 2021, 12:01:42 AMJul 10
to
On 7/9/2021 10:46 PM, André G. Isaak wrote:
> On 2021-07-09 21:18, olcott wrote:
>> On 7/9/2021 9:39 PM, André G. Isaak wrote:
>>> On 2021-07-09 17:31, olcott wrote:
>>>> On 7/9/2021 6:23 PM, Ben Bacarisse wrote:
>>>
>>>>> P(P) halts.  If you don't "count" all halting computations as halting
>>>>> you are talking nonsense.
>>>>>
>>>>
>>>> A computation that stops running because it has been aborted is as
>>>> Richard put it suspended, and not halted.
>>>
>>> Yes, but when P(P) is run independently there is nothing which can
>>> suspend this computation because it isn't being run in a simulator.
>>>
>>
>> What everyone consistently ignores is that only the prefix of the
>> computation runs independently. If the suffix of this computation was
>> not aborted then P(P) would never halt.
>
> Computations don't have 'prefixes' or 'suffixes'. P(P) represents a
> single computation.
>
>> Simulating halt decider H is only answering the question:
>> Would the input halt on its input if H never stopped simulating it?
>
> When we run P(P) independently it isn't being run inside of H so the
> above question is meaningless. If P(P) halts, then it halts. If not, it
> doesn't. Whatever H might have to say about it is irrelevant.
>
>> (a) An answer of "no" universally means that the input never halts.
>> (b) An answer of "yes" universally means that the input halts.
>>
>> Halt Deciding Axiom: When the pure simulation of the machine
>> description ⟨P⟩ of a machine P on its input I never halts we know that
>> P(I) never halts.
>
> You really need to learn what 'axioms' are.
>
> If the above is provable from existing tenets of computational theory,
> then it has no business being called an axiom.
>
> If it isn't, and you're introducing something new as an axiom, then
> you're no longer talking about the same computational theory that the
> halting problem is part of.
>

The above axiom is provided by the definition of a UTM, thus neither
provable nor something new. It is like all axioms a stipulated definition.

>>> In this case, the outermost P is the computation which is being
>>> performed and acts as the simulator. The innermost P is the input
>>> which is being simulated. The inner P might get suspended by the
>>> outer P, but the outer P can't be suspended. It simply *halts*.
>>>
>>> André
>>>
>>>
>>
>> No P ever halts unless some P is aborted, thus P(P) is accurately
>> construed as specifying infinitely nested simulation.
>
>
> But when we ask whether P(P) halts, we're asking specifically about the
> computation P(P). We're not asking about 'some P'.
>
> André
>

P(P) specifies an infinite set of nested simulations that never halts
unless one of the invocations of this infinite chain is aborted, thus
proving that it really does specify an infinite set of nested simulations.

olcott

unread,
Jul 10, 2021, 12:45:28 AMJul 10
to
On 7/9/2021 11:28 PM, André G. Isaak wrote:
> As I said, you really need to learn what 'axioms' are.
>
>>>>> In this case, the outermost P is the computation which is being
>>>>> performed and acts as the simulator. The innermost P is the input
>>>>> which is being simulated. The inner P might get suspended by the
>>>>> outer P, but the outer P can't be suspended. It simply *halts*.
>>>>>
>>>>> André
>>>>>
>>>>>
>>>>
>>>> No P ever halts unless some P is aborted, thus P(P) is accurately
>>>> construed as specifying infinitely nested simulation.
>>>
>>>
>>> But when we ask whether P(P) halts, we're asking specifically about
>>> the computation P(P). We're not asking about 'some P'.
>>>
>>> André
>>>
>>
>> P(P) specifies an infinite set of nested simulations that never halts
>> unless one of the invocations of this infinite chain is aborted, thus
>> proving that it really does specify an infinite set of nested
>> simulations.
>
> But by virtue of the way P is written, one of the nested simulations in
> P(P) is *always* aborted. Ergo the computation itself always halts.
>

When one of the function calls of infinite recursion is aborted the
infinite recursion also stops running but this does not count as halting
because the only reason that any of it ever stopped running is that one
of the links of the infinite recursion chain was aborted.

It is the same thing with infinitely nested simulation.

> As soon as you talk about a case where none of these simulations are
> aborted, you are no longer talking about P(P). You are talking about
> some other computation.

P(P) specifies an infinite chain of nested simulations. When you see its
execution trace this becomes obvious.

> The halting status of that other computation is
> entirely irrelevant to the halting status of P(P).

P(P) specifies an infinite chain of nested simulations. When you see its
execution trace this becomes obvious.

> And absolutely nothing in your post has anything to do with the C or
> software engineering, let alone the philosophy of AI. Those groups
> simply do not belong.
>
> André

olcott

unread,
Jul 10, 2021, 10:25:25 AMJul 10