Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2966 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-07-05 11:28 -0500 |
| Last post | 2021-07-07 18:04 -0500 |
| Articles | 20 on this page of 89 — 6 participants |
Back to article view | Back to comp.software-eng
How do we know that H(P,P)==0 is correct? olcott <NoOne@NoWhere.com> - 2021-07-05 11:28 -0500
Re: How do we know that H(P,P)==0 is correct? olcott <NoOne@NoWhere.com> - 2021-07-05 14:30 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-05 16:40 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 19:04 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 20:01 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 21:37 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-05 22:06 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-06 10:59 -0500
Re: How do we know that H(P,P)==0 is correct? (correct halt deciding criterion measure) olcott <NoOne@NoWhere.com> - 2021-07-06 11:33 -0500
Re: How do we know that H(P,P)==0 is correct? (V2) olcott <NoOne@NoWhere.com> - 2021-07-06 21:00 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 11:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 13:10 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 14:51 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 20:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 21:04 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ independent v dependent variables ] olcott <NoOne@NoWhere.com> - 2021-07-08 07:46 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ independent v dependent variables ] olcott <NoOne@NoWhere.com> - 2021-07-08 22:54 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) olcott <NoOne@NoWhere.com> - 2021-07-08 11:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) olcott <NoOne@NoWhere.com> - 2021-07-08 20:07 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-08 21:21 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-08 21:36 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 08:59 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-09 18:06 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 12:47 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-09 20:16 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 14:24 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-09 22:08 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 16:13 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 10:00 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-10 16:15 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 10:21 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-10 16:25 +0100
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 11:08 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ]( You and I ) olcott <NoOne@NoWhere.com> - 2021-07-10 11:42 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-07-10 15:19 -0700
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] gazelle@shell.xmission.com (Kenny McCormack) - 2021-07-11 00:29 +0000
Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] olcott <NoOne@NoWhere.com> - 2021-07-10 19:57 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 17:29 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 18:31 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 19:33 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-10 20:00 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ suspended not halted ] olcott <NoOne@NoWhere.com> - 2021-07-11 09:14 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-11 09:30 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ]( Flibble agrees ) olcott <NoOne@NoWhere.com> - 2021-07-11 14:47 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-12 17:18 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 08:41 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 09:42 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 10:02 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-14 15:52 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-14 16:47 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-14 22:12 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-15 09:17 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-15 19:42 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-15 19:52 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ](and Flibble) olcott <NoOne@NoWhere.com> - 2021-07-15 22:03 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ](and Flibble) olcott <NoOne@NoWhere.com> - 2021-07-16 21:48 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ](and Flibble) olcott <NoOne@NoWhere.com> - 2021-07-19 10:11 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 10:33 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 10:43 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 17:21 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 20:11 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 20:52 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 21:14 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-13 21:42 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-14 15:53 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-14 10:07 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 22:18 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 23:01 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-09 23:45 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] olcott <NoOne@NoWhere.com> - 2021-07-10 09:25 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ type mismatch error ] olcott <NoOne@NoWhere.com> - 2021-07-10 10:32 -0500
Re: How do we know that H(P,P)==0 is correct? (V4) [ type mismatch error ] olcott <NoOne@NoWhere.com> - 2021-07-10 11:19 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 20:31 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 21:07 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-08 08:29 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-09 09:02 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-05 23:15 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-06 10:26 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-06 21:18 +0100
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) olcott <NoOne@NoWhere.com> - 2021-07-06 15:41 -0500
Re: How do we know that H(P,P)==0 is correct? (Ben's double-talk does not work) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-06 23:18 +0100
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 09:47 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 20:15 -0500
Re: How do we know that H(P,P)==0 is correct? Bonita Montero <Bonita.Montero@gmail.com> - 2021-07-07 14:18 +0200
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 13:43 -0500
Re: How do we know that H(P,P)==0 is correct? (V3) scott@slp53.sl.home (Scott Lurndal) - 2021-07-07 19:01 +0000
Re: How do we know that H(P,P)==0 is correct? (V3) olcott <NoOne@NoWhere.com> - 2021-07-07 14:39 -0500
Re: How do we know that H(P,P)==0 is correct? olcott <NoOne@NoWhere.com> - 2021-07-07 17:05 -0500
Re: How do we know that H(P,P)==0 is correct? [ proof ] olcott <NoOne@NoWhere.com> - 2021-07-07 18:04 -0500
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-08 21:36 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <UI6dneCLY8myK3r9nZ2dnUU7-W-dnZ2d@giganews.com> |
| In reply to | #3009 |
On 7/8/2021 9:21 PM, olcott wrote: > On 7/8/2021 8:48 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 7/8/2021 5:52 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> On 7/8/2021 11:07 AM, Ben Bacarisse wrote: >>>>>> olcott <NoOne@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: > > "Peter Olcott" <NoSpam@SeeScreen.com> writes: > > 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. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-09 08:59 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <doWdnZPz-M_By3X9nZ2dnUU7-R3NnZ2d@giganews.com> |
| In reply to | #3009 |
On 7/9/2021 6:30 AM, Ben Bacarisse wrote:
> olcott <NoOne@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.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-09 18:06 +0100 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <20210709180643.00004d28@reddwarf.jmc> |
| In reply to | #3012 |
On Fri, 9 Jul 2021 08:59:51 -0500 olcott <NoOne@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
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-09 12:47 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <4K2dnR6DL908FnX9nZ2dnUU7-bHNnZ2d@giganews.com> |
| In reply to | #3015 |
On 7/9/2021 12:06 PM, Mr Flibble wrote: > On Fri, 9 Jul 2021 08:59:51 -0500 > olcott <NoOne@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 > -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-09 20:16 +0100 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <20210709201639.00001fe7@reddwarf.jmc> |
| In reply to | #3016 |
On Fri, 9 Jul 2021 12:47:12 -0500 olcott <NoOne@NoWhere.com> wrote: > On 7/9/2021 12:06 PM, Mr Flibble wrote: > > On Fri, 9 Jul 2021 08:59:51 -0500 > > olcott <NoOne@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 > > > > I continue to 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
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-09 14:24 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <PcudnVi3q7bvP3X9nZ2dnUU7-IOdnZ2d@giganews.com> |
| In reply to | #3017 |
On 7/9/2021 2:16 PM, Mr Flibble wrote: > On Fri, 9 Jul 2021 12:47:12 -0500 > olcott <NoOne@NoWhere.com> wrote: > >> On 7/9/2021 12:06 PM, Mr Flibble wrote: >>> On Fri, 9 Jul 2021 08:59:51 -0500 >>> olcott <NoOne@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 >>> >> >> > > I continue to 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 > 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. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-09 22:08 +0100 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <20210709220803.000050f1@reddwarf.jmc> |
| In reply to | #3018 |
On Fri, 9 Jul 2021 14:24:33 -0500 olcott <NoOne@NoWhere.com> wrote: > On 7/9/2021 2:16 PM, Mr Flibble wrote: > > On Fri, 9 Jul 2021 12:47:12 -0500 > > olcott <NoOne@NoWhere.com> wrote: > > > >> On 7/9/2021 12:06 PM, Mr Flibble wrote: > >>> On Fri, 9 Jul 2021 08:59:51 -0500 > >>> olcott <NoOne@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 > >>> > >> > >> > > > > I continue to 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 > > > > 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. You literally have no clue about what you are talking about, whatsoever. This explains everything. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-09 16:13 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <nIGdnZEeKNGQIXX9nZ2dnUU7-f2dnZ2d@giganews.com> |
| In reply to | #3019 |
On 7/9/2021 4:08 PM, Mr Flibble wrote:
> On Fri, 9 Jul 2021 14:24:33 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
>>> On Fri, 9 Jul 2021 12:47:12 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
>>>>> olcott <NoOne@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
>>>>>
>>>>
>>>>
>>>
>>> I continue to 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
>>>
>>
>> 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.
>
> You literally have no clue about what you are talking about,
> whatsoever. This explains everything.
>
> /Flibble
>
*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
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-10 10:00 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <z5WdnVkIYuC5K3T9nZ2dnUU7-QvNnZ2d@giganews.com> |
| In reply to | #3020 |
On 7/10/2021 9:30 AM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 08:54:23 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 6:40 AM, Mr Flibble wrote:
>>> On Fri, 9 Jul 2021 16:13:48 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/9/2021 4:08 PM, Mr Flibble wrote:
>>>>> On Fri, 9 Jul 2021 14:24:33 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
>>>>>>> On Fri, 9 Jul 2021 12:47:12 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
>>>>>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
>>>>>>>>> olcott <NoOne@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
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> I continue to 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
>>>>>>>
>>>>>>
>>>>>> 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.
>>>>>
>>>>> You literally have no clue about what you are talking about,
>>>>> whatsoever. This explains everything.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> *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
>>>>
>>>
>>> Except your decider can only handle trivial uninteresting cases: if
>>> you
>>
>> Ask other people here if being able to correctly decide the strachey
>> case is trivial or uninteresting. Ben might be the best one to ask
>> about this.
>>
>> Here is his original 1965 letter.
>> https://academic.oup.com/comjnl/article/7/4/313/354243
>
> All Strachey's letter shows is that a decider cannot be part of
> that which is being decided.
>
> /Flibble
>
// 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);
}
What it shows is that the halting problem proof can be enormously
simplified to the impossibility of the H(P,P) in main() returning a
correct halt status value to main().
*Here are Strachey's (verbatim) own words*
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] go to 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 is the creator of CPL ancestor to BCPL then B then C
His code above is written in his CPL programming language.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-10 16:15 +0100 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <20210710161537.00002347@reddwarf.jmc> |
| In reply to | #3028 |
On Sat, 10 Jul 2021 10:00:51 -0500
olcott <NoOne@NoWhere.com> wrote:
> On 7/10/2021 9:30 AM, Mr Flibble wrote:
> > On Sat, 10 Jul 2021 08:54:23 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 7/10/2021 6:40 AM, Mr Flibble wrote:
> >>> On Fri, 9 Jul 2021 16:13:48 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 7/9/2021 4:08 PM, Mr Flibble wrote:
> >>>>> On Fri, 9 Jul 2021 14:24:33 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
> >>>>>>> On Fri, 9 Jul 2021 12:47:12 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
> >>>>>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
> >>>>>>>>> olcott <NoOne@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
> >>>>>>>>>
> >>>>>>>>
> >>>>>>>>
> >>>>>>>
> >>>>>>> I continue to 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
> >>>>>>>
> >>>>>>
> >>>>>> 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.
> >>>>>
> >>>>> You literally have no clue about what you are talking about,
> >>>>> whatsoever. This explains everything.
> >>>>>
> >>>>> /Flibble
> >>>>>
> >>>>
> >>>> *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
> >>>>
> >>>
> >>> Except your decider can only handle trivial uninteresting cases:
> >>> if you
> >>
> >> Ask other people here if being able to correctly decide the
> >> strachey case is trivial or uninteresting. Ben might be the best
> >> one to ask about this.
> >>
> >> Here is his original 1965 letter.
> >> https://academic.oup.com/comjnl/article/7/4/313/354243
> >
> > All Strachey's letter shows is that a decider cannot be part of
> > that which is being decided.
> >
> > /Flibble
> >
>
>
> // 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);
> }
>
> What it shows is that the halting problem proof can be enormously
> simplified to the impossibility of the H(P,P) in main() returning a
> correct halt status value to main().
>
> *Here are Strachey's (verbatim) own words*
> 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] go to 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 is the creator of CPL ancestor to BCPL then B then C
> His code above is written in his CPL programming language.
I repeat: all Strachey's letter shows is that a decider cannot be part
of that which is being decided.
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-10 10:21 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <j_GdncmJqZZqJ3T9nZ2dnUU7-R-dnZ2d@giganews.com> |
| In reply to | #3029 |
On 7/10/2021 10:15 AM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 10:00:51 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 9:30 AM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 08:54:23 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 6:40 AM, Mr Flibble wrote:
>>>>> On Fri, 9 Jul 2021 16:13:48 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/9/2021 4:08 PM, Mr Flibble wrote:
>>>>>>> On Fri, 9 Jul 2021 14:24:33 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
>>>>>>>>> On Fri, 9 Jul 2021 12:47:12 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
>>>>>>>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
>>>>>>>>>>> olcott <NoOne@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
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I continue to 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
>>>>>>>>>
>>>>>>>>
>>>>>>>> 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.
>>>>>>>
>>>>>>> You literally have no clue about what you are talking about,
>>>>>>> whatsoever. This explains everything.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> *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
>>>>>>
>>>>>
>>>>> Except your decider can only handle trivial uninteresting cases:
>>>>> if you
>>>>
>>>> Ask other people here if being able to correctly decide the
>>>> strachey case is trivial or uninteresting. Ben might be the best
>>>> one to ask about this.
>>>>
>>>> Here is his original 1965 letter.
>>>> https://academic.oup.com/comjnl/article/7/4/313/354243
>>>
>>> All Strachey's letter shows is that a decider cannot be part of
>>> that which is being decided.
>>>
>>> /Flibble
>>>
>>
>>
>> // 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);
>> }
>>
>> What it shows is that the halting problem proof can be enormously
>> simplified to the impossibility of the H(P,P) in main() returning a
>> correct halt status value to main().
>>
>> *Here are Strachey's (verbatim) own words*
>> 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] go to 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 is the creator of CPL ancestor to BCPL then B then C
>> His code above is written in his CPL programming language.
>
> I repeat: all Strachey's letter shows is that a decider cannot be part
> of that which is being decided.
>
> /Flibble
>
Although this <is> one way of putting it, all of the halting problem
proofs require that the decider is a part of what is being decided. When
we disallow that all of these proofs lose their entire basis and fail to
prove anything.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-10 16:25 +0100 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <20210710162549.000014b6@reddwarf.jmc> |
| In reply to | #3030 |
On Sat, 10 Jul 2021 10:21:26 -0500
olcott <NoOne@NoWhere.com> wrote:
> On 7/10/2021 10:15 AM, Mr Flibble wrote:
> > On Sat, 10 Jul 2021 10:00:51 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 7/10/2021 9:30 AM, Mr Flibble wrote:
> >>> On Sat, 10 Jul 2021 08:54:23 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 7/10/2021 6:40 AM, Mr Flibble wrote:
> >>>>> On Fri, 9 Jul 2021 16:13:48 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 7/9/2021 4:08 PM, Mr Flibble wrote:
> >>>>>>> On Fri, 9 Jul 2021 14:24:33 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
> >>>>>>>>> On Fri, 9 Jul 2021 12:47:12 -0500
> >>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>>>
> >>>>>>>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
> >>>>>>>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
> >>>>>>>>>>> olcott <NoOne@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
> >>>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>
> >>>>>>>>> I continue to 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
> >>>>>>>>>
> >>>>>>>>
> >>>>>>>> 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.
> >>>>>>>
> >>>>>>> You literally have no clue about what you are talking about,
> >>>>>>> whatsoever. This explains everything.
> >>>>>>>
> >>>>>>> /Flibble
> >>>>>>>
> >>>>>>
> >>>>>> *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
> >>>>>>
> >>>>>
> >>>>> Except your decider can only handle trivial uninteresting cases:
> >>>>> if you
> >>>>
> >>>> Ask other people here if being able to correctly decide the
> >>>> strachey case is trivial or uninteresting. Ben might be the best
> >>>> one to ask about this.
> >>>>
> >>>> Here is his original 1965 letter.
> >>>> https://academic.oup.com/comjnl/article/7/4/313/354243
> >>>
> >>> All Strachey's letter shows is that a decider cannot be part of
> >>> that which is being decided.
> >>>
> >>> /Flibble
> >>>
> >>
> >>
> >> // 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);
> >> }
> >>
> >> What it shows is that the halting problem proof can be enormously
> >> simplified to the impossibility of the H(P,P) in main() returning a
> >> correct halt status value to main().
> >>
> >> *Here are Strachey's (verbatim) own words*
> >> 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] go to 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 is the creator of CPL ancestor to BCPL then B then C
> >> His code above is written in his CPL programming language.
> >
> > I repeat: all Strachey's letter shows is that a decider cannot be
> > part of that which is being decided.
> >
> > /Flibble
> >
>
> Although this <is> one way of putting it, all of the halting problem
> proofs require that the decider is a part of what is being decided.
> When we disallow that all of these proofs lose their entire basis and
> fail to prove anything.
I agree, if these proofs do require a decider to be part of that which
is being decided then they are indeed invalid for the reason Strachey
highlights in his letter.
/Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-10 11:08 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <xcCdnY7hb5meW3T9nZ2dnUU7-d3NnZ2d@giganews.com> |
| In reply to | #3031 |
On 7/10/2021 10:25 AM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 10:21:26 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 10:15 AM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 10:00:51 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 9:30 AM, Mr Flibble wrote:
>>>>> On Sat, 10 Jul 2021 08:54:23 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/10/2021 6:40 AM, Mr Flibble wrote:
>>>>>>> On Fri, 9 Jul 2021 16:13:48 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/9/2021 4:08 PM, Mr Flibble wrote:
>>>>>>>>> On Fri, 9 Jul 2021 14:24:33 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
>>>>>>>>>>> On Fri, 9 Jul 2021 12:47:12 -0500
>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
>>>>>>>>>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
>>>>>>>>>>>>> olcott <NoOne@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
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I continue to 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
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> 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.
>>>>>>>>>
>>>>>>>>> You literally have no clue about what you are talking about,
>>>>>>>>> whatsoever. This explains everything.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>
>>>>>>>> *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
>>>>>>>>
>>>>>>>
>>>>>>> Except your decider can only handle trivial uninteresting cases:
>>>>>>> if you
>>>>>>
>>>>>> Ask other people here if being able to correctly decide the
>>>>>> strachey case is trivial or uninteresting. Ben might be the best
>>>>>> one to ask about this.
>>>>>>
>>>>>> Here is his original 1965 letter.
>>>>>> https://academic.oup.com/comjnl/article/7/4/313/354243
>>>>>
>>>>> All Strachey's letter shows is that a decider cannot be part of
>>>>> that which is being decided.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>>
>>>> // 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);
>>>> }
>>>>
>>>> What it shows is that the halting problem proof can be enormously
>>>> simplified to the impossibility of the H(P,P) in main() returning a
>>>> correct halt status value to main().
>>>>
>>>> *Here are Strachey's (verbatim) own words*
>>>> 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] go to 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 is the creator of CPL ancestor to BCPL then B then C
>>>> His code above is written in his CPL programming language.
>>>
>>> I repeat: all Strachey's letter shows is that a decider cannot be
>>> part of that which is being decided.
>>>
>>> /Flibble
>>>
>>
>> Although this <is> one way of putting it, all of the halting problem
>> proofs require that the decider is a part of what is being decided.
>> When we disallow that all of these proofs lose their entire basis and
>> fail to prove anything.
>
> I agree, if these proofs do require a decider to be part of that which
> is being decided then they are indeed invalid for the reason Strachey
> highlights in his letter.
>
> /Flibble
>
I have been saying that they are invalid since 2004, now you are
agreeing with me on this.
comp.theory 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
Everyone else believes that they are valid and prove that the halting
problem is undecidable.
Strachey does not say that the proofs are invalid he claims that his
simplified version: "shows that the function T cannot exist."
What he everyone else means by function T is a universal halt decider.
Strachey says that his simple example proves that the halting problem is
undecidable.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-10 11:42 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ]( You and I ) |
| Message-ID | <H6OdnTryGdZxUHT9nZ2dnUU7-bPNnZ2d@giganews.com> |
| In reply to | #3033 |
On 7/10/2021 11:34 AM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 11:08:35 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 10:25 AM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 10:21:26 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 10:15 AM, Mr Flibble wrote:
>>>>> On Sat, 10 Jul 2021 10:00:51 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/10/2021 9:30 AM, Mr Flibble wrote:
>>>>>>> On Sat, 10 Jul 2021 08:54:23 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/10/2021 6:40 AM, Mr Flibble wrote:
>>>>>>>>> On Fri, 9 Jul 2021 16:13:48 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 7/9/2021 4:08 PM, Mr Flibble wrote:
>>>>>>>>>>> On Fri, 9 Jul 2021 14:24:33 -0500
>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On 7/9/2021 2:16 PM, Mr Flibble wrote:
>>>>>>>>>>>>> On Fri, 9 Jul 2021 12:47:12 -0500
>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 7/9/2021 12:06 PM, Mr Flibble wrote:
>>>>>>>>>>>>>>> On Fri, 9 Jul 2021 08:59:51 -0500
>>>>>>>>>>>>>>> olcott <NoOne@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
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> I continue to 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
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> 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.
>>>>>>>>>>>
>>>>>>>>>>> You literally have no clue about what you are talking about,
>>>>>>>>>>> whatsoever. This explains everything.
>>>>>>>>>>>
>>>>>>>>>>> /Flibble
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> *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
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Except your decider can only handle trivial uninteresting
>>>>>>>>> cases: if you
>>>>>>>>
>>>>>>>> Ask other people here if being able to correctly decide the
>>>>>>>> strachey case is trivial or uninteresting. Ben might be the
>>>>>>>> best one to ask about this.
>>>>>>>>
>>>>>>>> Here is his original 1965 letter.
>>>>>>>> https://academic.oup.com/comjnl/article/7/4/313/354243
>>>>>>>
>>>>>>> All Strachey's letter shows is that a decider cannot be part of
>>>>>>> that which is being decided.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>>
>>>>>> // 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);
>>>>>> }
>>>>>>
>>>>>> What it shows is that the halting problem proof can be enormously
>>>>>> simplified to the impossibility of the H(P,P) in main()
>>>>>> returning a correct halt status value to main().
>>>>>>
>>>>>> *Here are Strachey's (verbatim) own words*
>>>>>> 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] go to 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 is the creator of CPL ancestor to BCPL then B then C
>>>>>> His code above is written in his CPL programming language.
>>>>>
>>>>> I repeat: all Strachey's letter shows is that a decider cannot be
>>>>> part of that which is being decided.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> Although this <is> one way of putting it, all of the halting
>>>> problem proofs require that the decider is a part of what is being
>>>> decided. When we disallow that all of these proofs lose their
>>>> entire basis and fail to prove anything.
>>>
>>> I agree, if these proofs do require a decider to be part of that
>>> which is being decided then they are indeed invalid for the reason
>>> Strachey highlights in his letter.
>>>
>>> /Flibble
>>>
>>
>> I have been saying that they are invalid since 2004, now you are
>> agreeing with me on this.
>>
>> comp.theory 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
>>
>> Everyone else believes that they are valid and prove that the halting
>> problem is undecidable.
>
> They are not valid as [Strachey 1965] falsifies them (if what you say
> is correct) HOWEVER given that it doesn't follow that the halting
> problem itself is not undecidable just that those particular proofs are
> invalid.
>
> /Flibble
>
You can check around.
You and I are the only one's here that hold that view.
Ben, Kaz, and Mike would all disagree with you and I on this point.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2021-07-10 15:19 -0700 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <877dhx7qww.fsf@nosuchdomain.example.com> |
| In reply to | #3029 |
Mr Flibble <flibble@reddwarf.jmc> writes:
[196 lines deleted]
*Please* stop cross-posting this stuff to comp.lang.c, or to any group
other than comp.theory. I know it's olcott who insists on adding
irrelevant newsgroups, but I don't see his posts. Please edit the
Newsgroups: header line before posting a followup.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | gazelle@shell.xmission.com (Kenny McCormack) |
|---|---|
| Date | 2021-07-11 00:29 +0000 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <scde1q$3bd2h$1@news.xmission.com> |
| In reply to | #3047 |
In article <877dhx7qww.fsf@nosuchdomain.example.com>, Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote: >Mr Flibble <flibble@reddwarf.jmc> writes: >[196 lines deleted] > >*Please* stop cross-posting this stuff to comp.lang.c, or to any group >other than comp.theory. I know it's olcott who insists on adding >irrelevant newsgroups, but I don't see his posts. Please edit the >Newsgroups: header line before posting a followup. Like you did? -- The only thing Trump's made great again is Saturday Night Live.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-10 19:57 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ strachey example ] |
| Message-ID | <l9ydnQnoXoNl3Hf9nZ2dnUU7-UOdnZ2d@giganews.com> |
| In reply to | #3048 |
On 7/10/2021 7:29 PM, Kenny McCormack wrote: > In article <877dhx7qww.fsf@nosuchdomain.example.com>, > Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote: >> Mr Flibble <flibble@reddwarf.jmc> writes: >> [196 lines deleted] >> >> *Please* stop cross-posting this stuff to comp.lang.c, or to any group >> other than comp.theory. I know it's olcott who insists on adding >> irrelevant newsgroups, but I don't see his posts. Please edit the >> Newsgroups: header line before posting a followup. > > Like you did? > Flibble is only reviewing my work because I cross-posted and it turns out that he is a great reviewer. Kaz Kylheku only reviewed my work because I cross-posted and he is my best reviewer so far. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-09 17:29 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <pq2dnZox5YgiUHX9nZ2dnUU7-YHNnZ2d@giganews.com> |
| In reply to | #3012 |
On 7/9/2021 4:59 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 7/9/2021 6:30 AM, Ben Bacarisse wrote:
>>> olcott <NoOne@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.
>
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-09 18:31 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <u7KdnXl1aJP0QXX9nZ2dnUU7-RHNnZ2d@giganews.com> |
| In reply to | #3021 |
On 7/9/2021 6:23 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
> Please stop putting back irrelevant groups. You are not a tom cat.
> There is not need to spray everywhere.
>
>> On 7/9/2021 4:59 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 7/9/2021 6:30 AM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@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.
>
> 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.
>
>>> 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.
>
> 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.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-09 19:33 -0500 |
| Subject | Re: How do we know that H(P,P)==0 is correct? (V4) [ pathological self-reference(Olcott 2004) ] |
| Message-ID | <EKmdnQbwBf5Yd3X9nZ2dnUU7-QPNnZ2d@giganews.com> |
| In reply to | #3022 |
On 7/9/2021 7:13 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 7/9/2021 6:23 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@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.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
Back to top | Article view | comp.software-eng
csiph-web