info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: Halting Problem proofs appear to be bogus!
2 views
Skip to first unread message
olcott
Jul 16, 2021, 10:13:36 AM7/16/21
to
On 7/16/2021 8:34 AM, Ben Bacarisse wrote:
> Mr Flibble <fli...@reddwarf.jmc> writes:
>
>> All extant halting problem proofs appear to be predicated on a
>> misunderstanding of the following contradiction:
>
> I don't think you've read any actual proofs, let along all of them. Why
> you would even say such a thing?
>
>> Suppose T[R] is a Boolean function taking a routine
>> (or program) R with no formal or free variables as its
>> argument and that for all R, T[R] — True if R terminates
>> if run and that T[R] = False if R does not terminate. Consider
>> the routine P defined as follows
>>
>> rec routine P
>> §L :if T[P] goto L
>> Return §
>>
>> If T[P] = True the routine P will loop, and it will
>> only terminate if T[P] = False. In each case T[P] has
>> exactly the wrong value, and this contradiction shows
>> that the function T cannot exist.
>>
>> [Strachey 1965]
>>
>> T is indeed unable to decide P but for the wrong reason: T[P] is
>> recursive
>
> T[P] is not recursive. Maybe you don't understand what the CPL means?
>
> Further, this argument must fail for any of the actual proofs that are
> based on Turing machine because TMs have not functions, not calls and no
> recursion.
>
Peter Linz Ĥ applied to the Turing machine description of itself: ⟨Ĥ⟩
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt
When we hypothesize that the halt decider embedded in Ĥ is simply a UTM
then it seems that when the Peter Linz Ĥ is applied to its own Turing
machine description ⟨Ĥ⟩ this specifies a computation that never halts.
Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥx⟩ then Ĥ0.qx simulates this input with
the copy then
Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥy⟩ then Ĥ1.qx simulates this input with
the copy then
Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥz⟩ then Ĥ2.qx simulates this input with
the copy then ...
This is expressed in figure 12.4 as a cycle from qx to q0 to qx.
Within the hypothesis that the internal halt decider embedded within Ĥ
simulates its input Ĥ applied to its own Turing machine description ⟨Ĥ⟩
derives infinitely nested simulation, unless this simulation is aborted.
Self-Evident-Truth (premise[1])
When the pure simulation of a machine on its input never halts we know
that the execution of this machine on its input never halts.
Self-Evident-Truth (premise[2])
The ⟨Ĥ⟩ ⟨Ĥ⟩ input to the embedded simulating halt decider at Ĥ.qx is
pure simulation that never halts.
∴ Sound Deductive Conclusion
The embedded simulating halt decider at Ĥ.qx correctly decides its
input: ⟨Ĥ⟩ ⟨Ĥ⟩ is a computation that never halts.
Ĥ.q0 ⟨Ĥ⟩ specifies an infinite chain of invocations that is terminated
at its third invocation. The first invocation of Ĥ.qx ⟨Ĥ⟩, ⟨Ĥ⟩ is the
first element of an infinite chain of invocations.
It is common knowledge that when any invocation of an infinite chain of
invocations is terminated that the whole chain terminates. That the
first element of this infinite chain terminates after its third element
has been terminated does not entail that this first element is an actual
terminating computation.
The above is more clear when you can see the cycle in the state
transition diagram of Ĥ(⟨Ĥ⟩) provided in this paper:
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
> Mr Flibble <fli...@reddwarf.jmc> writes:
>
>> All extant halting problem proofs appear to be predicated on a
>> misunderstanding of the following contradiction:
>
> I don't think you've read any actual proofs, let along all of them. Why
> you would even say such a thing?
>
>> Suppose T[R] is a Boolean function taking a routine
>> (or program) R with no formal or free variables as its
>> argument and that for all R, T[R] — True if R terminates
>> if run and that T[R] = False if R does not terminate. Consider
>> the routine P defined as follows
>>
>> rec routine P
>> §L :if T[P] goto L
>> Return §
>>
>> If T[P] = True the routine P will loop, and it will
>> only terminate if T[P] = False. In each case T[P] has
>> exactly the wrong value, and this contradiction shows
>> that the function T cannot exist.
>>
>> [Strachey 1965]
>>
>> T is indeed unable to decide P but for the wrong reason: T[P] is
>> recursive
>
> T[P] is not recursive. Maybe you don't understand what the CPL means?
>
> Further, this argument must fail for any of the actual proofs that are
> based on Turing machine because TMs have not functions, not calls and no
> recursion.
>
Peter Linz Ĥ applied to the Turing machine description of itself: ⟨Ĥ⟩
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt
When we hypothesize that the halt decider embedded in Ĥ is simply a UTM
then it seems that when the Peter Linz Ĥ is applied to its own Turing
machine description ⟨Ĥ⟩ this specifies a computation that never halts.
Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥx⟩ then Ĥ0.qx simulates this input with
the copy then
Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥy⟩ then Ĥ1.qx simulates this input with
the copy then
Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥz⟩ then Ĥ2.qx simulates this input with
the copy then ...
This is expressed in figure 12.4 as a cycle from qx to q0 to qx.
Within the hypothesis that the internal halt decider embedded within Ĥ
simulates its input Ĥ applied to its own Turing machine description ⟨Ĥ⟩
derives infinitely nested simulation, unless this simulation is aborted.
Self-Evident-Truth (premise[1])
When the pure simulation of a machine on its input never halts we know
that the execution of this machine on its input never halts.
Self-Evident-Truth (premise[2])
The ⟨Ĥ⟩ ⟨Ĥ⟩ input to the embedded simulating halt decider at Ĥ.qx is
pure simulation that never halts.
∴ Sound Deductive Conclusion
The embedded simulating halt decider at Ĥ.qx correctly decides its
input: ⟨Ĥ⟩ ⟨Ĥ⟩ is a computation that never halts.
Ĥ.q0 ⟨Ĥ⟩ specifies an infinite chain of invocations that is terminated
at its third invocation. The first invocation of Ĥ.qx ⟨Ĥ⟩, ⟨Ĥ⟩ is the
first element of an infinite chain of invocations.
It is common knowledge that when any invocation of an infinite chain of
invocations is terminated that the whole chain terminates. That the
first element of this infinite chain terminates after its third element
has been terminated does not entail that this first element is an actual
terminating computation.
The above is more clear when you can see the cycle in the state
transition diagram of Ĥ(⟨Ĥ⟩) provided in this paper:
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
Jul 16, 2021, 10:32:58 AM7/16/21
to
On 7/16/2021 8:24 AM, Mr Flibble wrote:
> Hi!
cannot be any T that always correctly decides the halting status of
every input. Conventionally no on ever cared that this is for the wrong
reason.
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
In the case of my H and P, because my H is a simulating halt decider
that only acts as a pure simulator until after its halt status decision
is made the pathological self-reference(olcott 2004) error that you
correctly object to has no effect on either the behavior of P or the
halt status decision of H.
H aborts the simulation of its input before any nested H ever returns
any value to any P. This utterly nullifies the prior issue that seemed
to prove that P is undecidable.
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
> T[P] is
> recursive which means T can never decide if P halts because T never
> halts itself; this mistake appears to have been missed by Strachey as
> the §L <- L loop can't ever loop due to the recursion.
>
> HOWEVER
>
> Even if we ignore the error of recursion it does NOT follow that for
> T[Q], T cannot decide if Q halts where Q is a program that does not
> reference T.
>
> [Strachey 1965] shows us that a decider cannot be part of or called by
> that which is being decided (a pathological program) and given this it
> seems to be unproven that a decider for programs that don't exhibit
> this pathology cannot exist.
>
> /Flibble
> Hi!
>
> All extant halting problem proofs appear to be predicated on a
> misunderstanding of the following contradiction:
>
> All extant halting problem proofs appear to be predicated on a
> misunderstanding of the following contradiction:
>
> Suppose T[R] is a Boolean function taking a routine
> (or program) R with no formal or free variables as its
> argument and that for all R, T[R] — True if R terminates
> if run and that T[R] = False if R does not terminate. Consider
> the routine P defined as follows
>
> rec routine P
> §L :if T[P] goto L
> Return §
>
> If T[P] = True the routine P will loop, and it will
> only terminate if T[P] = False. In each case T[P] has
> exactly the wrong value, and this contradiction shows
> that the function T cannot exist.
>
> [Strachey 1965]
>
> T is indeed unable to decide P but for the wrong reason:
Conventionally it is understood that the instance of P proves that there
> (or program) R with no formal or free variables as its
> argument and that for all R, T[R] — True if R terminates
> if run and that T[R] = False if R does not terminate. Consider
> the routine P defined as follows
>
> rec routine P
> §L :if T[P] goto L
> Return §
>
> If T[P] = True the routine P will loop, and it will
> only terminate if T[P] = False. In each case T[P] has
> exactly the wrong value, and this contradiction shows
> that the function T cannot exist.
>
> [Strachey 1965]
>
> T is indeed unable to decide P but for the wrong reason:
cannot be any T that always correctly decides the halting status of
every input. Conventionally no on ever cared that this is for the wrong
reason.
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
In the case of my H and P, because my H is a simulating halt decider
that only acts as a pure simulator until after its halt status decision
is made the pathological self-reference(olcott 2004) error that you
correctly object to has no effect on either the behavior of P or the
halt status decision of H.
H aborts the simulation of its input before any nested H ever returns
any value to any P. This utterly nullifies the prior issue that seemed
to prove that P is undecidable.
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
> T[P] is
> recursive which means T can never decide if P halts because T never
> halts itself; this mistake appears to have been missed by Strachey as
> the §L <- L loop can't ever loop due to the recursion.
>
> HOWEVER
>
> Even if we ignore the error of recursion it does NOT follow that for
> T[Q], T cannot decide if Q halts where Q is a program that does not
> reference T.
>
> [Strachey 1965] shows us that a decider cannot be part of or called by
> that which is being decided (a pathological program) and given this it
> seems to be unproven that a decider for programs that don't exhibit
> this pathology cannot exist.
>
> /Flibble
olcott
Jul 16, 2021, 10:36:21 AM7/16/21
to
On 7/16/2021 8:39 AM, Mr Flibble wrote:
> who is unfamiliar with the CPL language (a clue: read the paragraph
> before the definition of P again).
>
"Recursive" has a very different meaning in computer science than it
does in software engineering.
https://en.wikipedia.org/wiki/Recursive_language
>>
>> Further, this argument must fail for any of the actual proofs that are
>> based on Turing machine because TMs have not functions, not calls and
>> no recursion.
>
> Depends on whether or not there is an isomorphic equivalence.
> On Fri, 16 Jul 2021 14:34:54 +0100
> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>
>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>
> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>
>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>
>>> All extant halting problem proofs appear to be predicated on a
>>> misunderstanding of the following contradiction:
>>
>>> misunderstanding of the following contradiction:
>>
>> I don't think you've read any actual proofs, let along all of them.
>> Why you would even say such a thing?
>>
>> Why you would even say such a thing?
>>
>>> Suppose T[R] is a Boolean function taking a routine
>>> (or program) R with no formal or free variables as its
>>> argument and that for all R, T[R] — True if R terminates
>>> if run and that T[R] = False if R does not terminate.
>>> Consider the routine P defined as follows
>>>
>>> rec routine P
>>> §L :if T[P] goto L
>>> Return §
>>>
>>> If T[P] = True the routine P will loop, and it will
>>> only terminate if T[P] = False. In each case T[P] has
>>> exactly the wrong value, and this contradiction shows
>>> that the function T cannot exist.
>>>
>>> [Strachey 1965]
>>>
>>> (or program) R with no formal or free variables as its
>>> argument and that for all R, T[R] — True if R terminates
>>> if run and that T[R] = False if R does not terminate.
>>> Consider the routine P defined as follows
>>>
>>> rec routine P
>>> §L :if T[P] goto L
>>> Return §
>>>
>>> If T[P] = True the routine P will loop, and it will
>>> only terminate if T[P] = False. In each case T[P] has
>>> exactly the wrong value, and this contradiction shows
>>> that the function T cannot exist.
>>>
>>> [Strachey 1965]
>>>
>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>> recursive
>>
>> T[P] is not recursive. Maybe you don't understand what the CPL means?
>
> Of course it is recursive, such is obvious even to the casual reader
>>> recursive
>>
>> T[P] is not recursive. Maybe you don't understand what the CPL means?
>
> who is unfamiliar with the CPL language (a clue: read the paragraph
> before the definition of P again).
>
"Recursive" has a very different meaning in computer science than it
does in software engineering.
https://en.wikipedia.org/wiki/Recursive_language
>>
>> Further, this argument must fail for any of the actual proofs that are
>> based on Turing machine because TMs have not functions, not calls and
>> no recursion.
>
Mr Flibble
Jul 16, 2021, 10:39:59 AM7/16/21
to
directly or indirectly; in the case of [Strachey 1965] the recursion is
indirect:
T[P] -> P -> T[P] -> P -> T[P] ... ...
/Flibble
olcott
Jul 16, 2021, 10:45:04 AM7/16/21
to
On 7/16/2021 9:27 AM, Peter wrote:
> Mr Flibble wrote:
>> Hi!
> claim.
>
He is objecting to all the proofs having the pathological
self-reference(Olcott 2004) error where the input D does the opposite of
whatever the halt decider H decides. **
This includes all the informal pseudo-code proofs, Sipser, Kozen and
Linz. I am not aware of any proofs that it excludes.
** Now we construct a new Turing machine D with H as a subroutine. This
new TM calls H to determine what M does when the input to M is its own
description ⟨M⟩. Once D has determined this information, it does the
opposite. http://www.liarparadox.org/Sipser_165_167.pdf
>> misunderstanding of the following contradiction:
>>
> Mr Flibble wrote:
>> Hi!
>>
>> All extant halting problem proofs appear to be predicated on a
>
> Since you haven't read them all, you are in no position to make such a
>> All extant halting problem proofs appear to be predicated on a
>
> claim.
>
He is objecting to all the proofs having the pathological
self-reference(Olcott 2004) error where the input D does the opposite of
whatever the halt decider H decides. **
This includes all the informal pseudo-code proofs, Sipser, Kozen and
Linz. I am not aware of any proofs that it excludes.
** Now we construct a new Turing machine D with H as a subroutine. This
new TM calls H to determine what M does when the input to M is its own
description ⟨M⟩. Once D has determined this information, it does the
opposite. http://www.liarparadox.org/Sipser_165_167.pdf
>> misunderstanding of the following contradiction:
>>
>> Suppose T[R] is a Boolean function taking a routine
>> (or program) R with no formal or free variables as its
>> argument and that for all R, T[R] — True if R terminates
>> if run and that T[R] = False if R does not terminate. Consider
>> the routine P defined as follows
>>
>> rec routine P
>> §L :if T[P] goto L
>> Return §
>>
>> If T[P] = True the routine P will loop, and it will
>> only terminate if T[P] = False. In each case T[P] has
>> exactly the wrong value, and this contradiction shows
>> that the function T cannot exist.
>>
>> [Strachey 1965]
>>
>> T is indeed unable to decide P but for the wrong reason: T[P] is
>> (or program) R with no formal or free variables as its
>> argument and that for all R, T[R] — True if R terminates
>> if run and that T[R] = False if R does not terminate. Consider
>> the routine P defined as follows
>>
>> rec routine P
>> §L :if T[P] goto L
>> Return §
>>
>> If T[P] = True the routine P will loop, and it will
>> only terminate if T[P] = False. In each case T[P] has
>> exactly the wrong value, and this contradiction shows
>> that the function T cannot exist.
>>
>> [Strachey 1965]
>>
>> T is indeed unable to decide P but for the wrong reason: T[P] is
>> recursive which means T can never decide if P halts because T never
>> halts itself; this mistake appears to have been missed by Strachey as
>> the §L <- L loop can't ever loop due to the recursion.
>>
>> HOWEVER
>>
>> Even if we ignore the error of recursion it does NOT follow that for
>> T[Q], T cannot decide if Q halts where Q is a program that does not
>> reference T.
>>
>> [Strachey 1965] shows us that a decider cannot be part of or called by
>> that which is being decided (a pathological program) and given this it
>> seems to be unproven that a decider for programs that don't exhibit
>> this pathology cannot exist.
>>
>> halts itself; this mistake appears to have been missed by Strachey as
>> the §L <- L loop can't ever loop due to the recursion.
>>
>> HOWEVER
>>
>> Even if we ignore the error of recursion it does NOT follow that for
>> T[Q], T cannot decide if Q halts where Q is a program that does not
>> reference T.
>>
>> [Strachey 1965] shows us that a decider cannot be part of or called by
>> that which is being decided (a pathological program) and given this it
>> seems to be unproven that a decider for programs that don't exhibit
>> this pathology cannot exist.
>>
olcott
Jul 16, 2021, 11:02:15 AM7/16/21
to
On 7/16/2021 9:36 AM, Mr Flibble wrote:
> on whether the claim is true or false. Feel free to refute my claim,
> dear.
>
> /Flibble
>
>
On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
> I agree with Olcott that a halt decider can NOT be part of that which
> is being decided (see [Strachey 1965]) which, if Olcott is correct,
> falsifies a collection of proofs (which I don't have the time to
> examine) which rely on that mistake.
>
> /Flibble
Our claim is that the refutation applies to all cases where the behavior
of the halt decider is a part of that which is being decided. I named
this the Pathological self-reference error in 2004.
Now the ball is in Percival's court to dig up some very obscure paper
that does not depend on the PSR error. The last time that he did this he
referenced a paper that uses Gödel numbers to hide the PSR error behind
75 pages of nested formulas.
Sipser, Linz and Kozen proofs as well as all the informal pseudo-code
proofs utterly depend on the PSR error as their only basis.
> On Fri, 16 Jul 2021 15:27:53 +0100
> Peter <peterxp...@hotmail.com> wrote:
>
>> Mr Flibble wrote:
>>> Hi!
>>>
>>> All extant halting problem proofs appear to be predicated on a
>>
>> Since you haven't read them all, you are in no position to make such
>> a claim.
>
> Whether or not I am in a position to make such a claim has no bearing
> Peter <peterxp...@hotmail.com> wrote:
>
>> Mr Flibble wrote:
>>> Hi!
>>>
>>> All extant halting problem proofs appear to be predicated on a
>>
>> Since you haven't read them all, you are in no position to make such
>> a claim.
>
> on whether the claim is true or false. Feel free to refute my claim,
> dear.
>
> /Flibble
>
>
On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
> I agree with Olcott that a halt decider can NOT be part of that which
> is being decided (see [Strachey 1965]) which, if Olcott is correct,
> falsifies a collection of proofs (which I don't have the time to
> examine) which rely on that mistake.
>
> /Flibble
Our claim is that the refutation applies to all cases where the behavior
of the halt decider is a part of that which is being decided. I named
this the Pathological self-reference error in 2004.
Now the ball is in Percival's court to dig up some very obscure paper
that does not depend on the PSR error. The last time that he did this he
referenced a paper that uses Gödel numbers to hide the PSR error behind
75 pages of nested formulas.
Sipser, Linz and Kozen proofs as well as all the informal pseudo-code
proofs utterly depend on the PSR error as their only basis.
olcott
Jul 16, 2021, 11:52:53 AM7/16/21
to
On 7/16/2021 10:12 AM, Andy Walker wrote:
> "T" as a free variable, so is not a valid parameter to "T"? But that's
> a quibble, as "P" could be re-written to have the code for "H" included.
10.3.1 seems to indicate that rec routine P means that P is recursive.
>> Of course it is recursive, such is obvious even to the casual reader
>> who is unfamiliar with the CPL language (a clue: read the paragraph
>> before the definition of P again).
>
> "T[P]" is recursive only if "T" calls "P". That is a pretty
> daft thing to do. "Does this program ever halt?" "Dunno, let's find
Here is my best estimate of the CPL written in C:
void P()
{
if (T((u32)P)
HERE: goto HERE;
}
> out by running it." If that doesn't seem stupid, imagine replacing
> "halt" by "kill the patient" or "blow up this nuclear power station".
> So a well-written "T" will not call its parameter. This makes the
> whole argument as currently being debated moot; if you don't call a
> routine, then pretty much all you can do with it is assign it or pass
> it as a parameter/operand, neither of which gets us any nearer to
> deciding whether it halts [or kills people].
>
> But in this form, it also has nothing to do with the Halting
> Problem, which would not be about some "T" that /calls/ "P" but about
> one that /inspects/ "P". So the only sensible interpretation of what
> Strachey wrote is that the parameter to "T" is the /source/ of some
> program or routine "P". In most languages, that source would be of
> "string" or perhaps "file" type or similar. "P" would then be the
> string quoted above [preferably with also the string corresponding
> to the source of "T"]. Once this simple interpretation is made, the
> fundamental Strachey/Minsky/Sipser/Linz argument works perfectly well
> with no question of recursion [infinite, "pathological" or otherwise]
> unless "T" chooses it.
>
> That is why I have several times suggested, though with little
> success, that participants in this debate should be very clear about
> whether they are talking about "source" or "executable". Simply
> calling things "H", "P", "T", "H_hat", ... does not convey this
> [necessary] information, and leads to Olcottian confusions. Perhaps
> some contributors prefer to obscure the argument.
>
In my case when P is passed to P it is the machine address of the
machine language of P that is directly executed by an x86 emulator. This
eliminates all of the extraneous complexity of switching back and forth
between the machine and its description. The x86 description of P <is> P.
> On 16/07/2021 14:39, Mr Flibble wrote:
>> On Fri, 16 Jul 2021 14:34:54 +0100
>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>> Mr Flibble <fli...@reddwarf.jmc> quotes:
>> On Fri, 16 Jul 2021 14:34:54 +0100
>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>>> Suppose T[R] is a Boolean function taking a routine
>>>> (or program) R with no formal or free variables as its
>>>> argument [...].
>>>> (or program) R with no formal or free variables as its
>>>> Consider the routine P defined as follows
>>>> rec routine P
>>>> §L :if T[P] goto L
>>>> Return §
> [...]
>>>> rec routine P
>>>> §L :if T[P] goto L
>>>> Return §
>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>> recursive
>
> I suppose one should not point out that "P", as defined, has
>>>> recursive
>
> "T" as a free variable, so is not a valid parameter to "T"? But that's
> a quibble, as "P" could be re-written to have the code for "H" included.
>
>>> T[P] is not recursive. Maybe you don't understand what the CPL means?
http://www.ancientgeek.org.uk/CPL/CPL_Working_Papers.pdf
>>> T[P] is not recursive. Maybe you don't understand what the CPL means?
10.3.1 seems to indicate that rec routine P means that P is recursive.
>> Of course it is recursive, such is obvious even to the casual reader
>> who is unfamiliar with the CPL language (a clue: read the paragraph
>> before the definition of P again).
>
> daft thing to do. "Does this program ever halt?" "Dunno, let's find
Here is my best estimate of the CPL written in C:
void P()
{
if (T((u32)P)
HERE: goto HERE;
}
> out by running it." If that doesn't seem stupid, imagine replacing
> "halt" by "kill the patient" or "blow up this nuclear power station".
> So a well-written "T" will not call its parameter. This makes the
> whole argument as currently being debated moot; if you don't call a
> routine, then pretty much all you can do with it is assign it or pass
> it as a parameter/operand, neither of which gets us any nearer to
> deciding whether it halts [or kills people].
>
> But in this form, it also has nothing to do with the Halting
> Problem, which would not be about some "T" that /calls/ "P" but about
> one that /inspects/ "P". So the only sensible interpretation of what
> Strachey wrote is that the parameter to "T" is the /source/ of some
> program or routine "P". In most languages, that source would be of
> "string" or perhaps "file" type or similar. "P" would then be the
> string quoted above [preferably with also the string corresponding
> to the source of "T"]. Once this simple interpretation is made, the
> fundamental Strachey/Minsky/Sipser/Linz argument works perfectly well
> with no question of recursion [infinite, "pathological" or otherwise]
> unless "T" chooses it.
>
> That is why I have several times suggested, though with little
> success, that participants in this debate should be very clear about
> whether they are talking about "source" or "executable". Simply
> calling things "H", "P", "T", "H_hat", ... does not convey this
> [necessary] information, and leads to Olcottian confusions. Perhaps
> some contributors prefer to obscure the argument.
>
In my case when P is passed to P it is the machine address of the
machine language of P that is directly executed by an x86 emulator. This
eliminates all of the extraneous complexity of switching back and forth
between the machine and its description. The x86 description of P <is> P.
olcott
Jul 16, 2021, 12:04:55 PM7/16/21
to
On 7/16/2021 10:38 AM, wij wrote:
> // program P.c
> //-------------------
> void P();
>
> inline bool H(Func p) {
> // Rewrite H here.
> // The rewrite can be in very different but functionally equivalent ways (isomorphic).
> }
>
> void P() {
> if(H(P)) {
> for(;;) {}; // If H(P)==true, P is in infinite loop.
> }
> };
>
> If there is high-level "recursive call" it is made within H itself (may be your T), nothing to
> do with P. And this is why "undecidable" is called, H will not halt.
>
#include <stdint.h>
#define u32 uint32_t
void P()
{
if (H((u32)P)))
HERE: goto HERE;
}
Since there is no such actual thing as Func p that is currently fully
elaborated yet there is such as thing as the machine address of the
machine language code of the C function P mine can be fully understood
whereas your leaves out to many details.
In my system H is written in C returns u32 and is based on a full x86
emulator:
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
> //-------------------
> void P();
>
> inline bool H(Func p) {
> // Rewrite H here.
> // The rewrite can be in very different but functionally equivalent ways (isomorphic).
> }
>
> void P() {
> if(H(P)) {
> for(;;) {}; // If H(P)==true, P is in infinite loop.
> }
> };
>
> If there is high-level "recursive call" it is made within H itself (may be your T), nothing to
> do with P. And this is why "undecidable" is called, H will not halt.
>
#include <stdint.h>
#define u32 uint32_t
void P()
{
if (H((u32)P)))
HERE: goto HERE;
}
Since there is no such actual thing as Func p that is currently fully
elaborated yet there is such as thing as the machine address of the
machine language code of the C function P mine can be fully understood
whereas your leaves out to many details.
In my system H is written in C returns u32 and is based on a full x86
emulator:
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
olcott
Jul 16, 2021, 12:15:52 PM7/16/21
to
On 7/16/2021 11:11 AM, wij wrote:
> IMO, DOS + x86 assembly is already a TM simulator.
> x86 emulator is redundant. Besides, the input of the x86 emulator
> seems have to be COFF, this would made x86 emulator not a valid
> proof machine (input and execution codes are different).
>
A halt decider must have absolute control over its slave process.
H steps through P(P) one instruction at a time and immediately aborts
its simulation of P(P) as soon as the next instruction of P indicates
that P is stuck in infinitely nested simulation.
> x86 emulator is redundant. Besides, the input of the x86 emulator
> seems have to be COFF, this would made x86 emulator not a valid
> proof machine (input and execution codes are different).
>
A halt decider must have absolute control over its slave process.
H steps through P(P) one instruction at a time and immediately aborts
its simulation of P(P) as soon as the next instruction of P indicates
that P is stuck in infinitely nested simulation.
olcott
Jul 16, 2021, 5:20:15 PM7/16/21
to
On 7/16/2021 4:07 PM, Peter wrote:
> Mr Flibble wrote:
> Mr Flibble wrote:
>> On Fri, 16 Jul 2021 15:27:53 +0100
>> Peter <peterxp...@hotmail.com> wrote:
>>
>>> Mr Flibble wrote:
>>>> Hi!
>>>>
>> Peter <peterxp...@hotmail.com> wrote:
>>
>>> Mr Flibble wrote:
>>>> Hi!
>>>>
>>>> All extant halting problem proofs appear to be predicated on a
>>>
>>>
>>> Since you haven't read them all, you are in no position to make such
>>> a claim.
>>
>> Whether or not I am in a position to make such a claim has no bearing
>> on whether the claim is true or false. Feel free to refute my claim,
>> dear.
>>
>> /Flibble
>>
>>
> Ahem... the onus is on you to prove your--utterly implausible--claim.
>>> a claim.
>>
>> Whether or not I am in a position to make such a claim has no bearing
>> on whether the claim is true or false. Feel free to refute my claim,
>> dear.
>>
>> /Flibble
>>
>>
>
He has already proved that any requirement for a program/TM to return a
halt status value to an input to does the opposite of whatever the halt
decider returns is bogus. The meaning of these words proves that such a
case has the exactly same bogus pattern as the liar paradox.
Generically this can be understood as the scientific principle that the
dependent variable of a scientific investigation is not allowed to
interfere with the independent variable.
When P interferes with H this scientific principle is violated. Flibble
spotted this error and thus has a correct basis for his claim.
On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
> I agree with Olcott that a halt decider can NOT be part of that which
> is being decided (see [Strachey 1965]) which, if Olcott is correct,
> falsifies a collection of proofs (which I don't have the time to
> examine) which rely on that mistake.
>
> /Flibble
olcott
Jul 17, 2021, 11:52:13 AM7/17/21
to
On 7/16/2021 7:06 PM, Ben Bacarisse wrote:
> Mr Flibble <fli...@reddwarf.jmc> writes:
>
>> On Fri, 16 Jul 2021 15:40:27 +0100
> Mr Flibble <fli...@reddwarf.jmc> writes:
>
>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>
>>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>>
>>>> On Fri, 16 Jul 2021 14:34:54 +0100
>>>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>>>
>>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>>
>>>> On Fri, 16 Jul 2021 14:34:54 +0100
>>>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>>>
>>>>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>>>>
>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>
>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>> misunderstanding of the following contradiction:
>>>>>
>>>>> I don't think you've read any actual proofs, let along all of them.
>>>>> Why you would even say such a thing?
>>>>>
>>>>>
>>>>> I don't think you've read any actual proofs, let along all of them.
>>>>> Why you would even say such a thing?
>>>>>
>>>>>> Suppose T[R] is a Boolean function taking a routine
>>>>>> (or program) R with no formal or free variables as its
>>>>>> (or program) R with no formal or free variables as its
>>>>>> argument and that for all R, T[R] — True if R terminates
>>>>>> if run and that T[R] = False if R does not terminate.
>>>>>> if run and that T[R] = False if R does not terminate.
>>>>>> Consider the routine P defined as follows
>>>>>>
>>>>>> rec routine P
>>>>>> §L :if T[P] goto L
>>>>>> Return §
>>>>>>
>>>>>>
>>>>>> rec routine P
>>>>>> §L :if T[P] goto L
>>>>>> Return §
>>>>>>
>>>>>> If T[P] = True the routine P will loop, and it will
>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>> exactly the wrong value, and this contradiction shows
>>>>>> that the function T cannot exist.
>>>>>>
>>>>>> [Strachey 1965]
>>>>>>
>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>> exactly the wrong value, and this contradiction shows
>>>>>> that the function T cannot exist.
>>>>>>
>>>>>> [Strachey 1965]
>>>>>>
>>>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>>>> recursive
>>>>>
>>>>>> recursive
>>>>>
>>>>> T[P] is not recursive. Maybe you don't understand what the CPL
>>>>> means?
>>>>
>>>>> means?
>>>>
>>>> Of course it is recursive, such is obvious even to the casual reader
>>>> who is unfamiliar with the CPL language (a clue: read the paragraph
>>>> before the definition of P again).
>>>
>>> No. T[P] /might/ be recursive, but then again it might not be. Any
>>>> who is unfamiliar with the CPL language (a clue: read the paragraph
>>>> before the definition of P again).
>>>
>>> argument based on the blank assumption that T[P] is recursive is
>>> flawed. T must be permitted to make it decision based on the widest
>>> possible use of it's argument or the sketch is pointlessly
>>> restrictive.
>>
>> No. It is recursive.
>
> I suppose if anyone else is reading this, they will just have to pick a
> side!
>
Pathological self-reference(Olcott 2004) is an error.
When an input is defined to do that opposite of whatever its
corresponding halt decider decides this forms the exactly same
self-contradictory error of the liar paradox.
On Sunday, September 5, 2004 at 11:21:57 AM UTC-5, Peter Olcott wrote:
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.
Halt deciders can be defined that correctly decide the halt status of
these otherwise pathological inputs.
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
olcott
Jul 19, 2021, 11:10:54 AM7/19/21
to
On 7/17/2021 8:32 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
> ...
>> I only skimmed the above, I skipped most of the words.
>
> Good plan. You really don't want to know what I said! I've cut it
> since you don't care about details. Let's stick with the big picture.
>
>> int main() { P(P); } is computationally equivalent to Ĥ(⟨Ĥ⟩).
>
> Yes. P(P) halts (according to you). H(P,P) == 0 (according to you).
> That is wrong (according to everyone but you).
simulation of its input at some point its input never halts thus proving
beyond all possible doubt that the input that was aborted is correctly
decided as never halting.
When a computation only stops running because its simulation was aborted
this counts as a computation that never halts.
> olcott <No...@NoWhere.com> writes:
> ...
>> I only skimmed the above, I skipped most of the words.
>
> Good plan. You really don't want to know what I said! I've cut it
> since you don't care about details. Let's stick with the big picture.
>
>> int main() { P(P); } is computationally equivalent to Ĥ(⟨Ĥ⟩).
>
> Yes. P(P) halts (according to you). H(P,P) == 0 (according to you).
> That is wrong (according to everyone but you).
>
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt
Unless the simulating halt decider embedded at state Ĥ.qx aborts the
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt
simulation of its input at some point its input never halts thus proving
beyond all possible doubt that the input that was aborted is correctly
decided as never halting.
When a computation only stops running because its simulation was aborted
this counts as a computation that never halts.
olcott
Jul 20, 2021, 10:24:44 AM7/20/21
to
On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> When a computation only stops running because its simulation was
>> aborted this counts as a computation that never halts.
>
> Me: Every computation that halts, for whatever reason, is a halting
> olcott <No...@NoWhere.com> writes:
>
>> When a computation only stops running because its simulation was
>> aborted this counts as a computation that never halts.
>
> computation.
>
> You: OK
>
A computation having its simulation aborted never halts even though it
stops running. Only computation that stop running without having their
simulation aborted are halting computations.
> P(P) halts (according to you). H(P,P) == 0 (according to you).
0 new messages