Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: Refuting the {Linz, Sipser and Kozen} HP Proofs (deciders within infinite recursion)
13 views
Skip to first unread message
olcott
Dec 14, 2020, 10:16:29 AM12/14/20
to
On 12/14/2020 8:48 AM, André G. Isaak wrote:
> On 2020-12-14 07:25, olcott wrote:
>> On 12/12/2020 2:37 PM, André G. Isaak wrote:
>>> On 2020-12-12 13:01, olcott wrote:
>>>> On 12/12/2020 1:40 PM, André G. Isaak wrote:
>>>>> On 2020-12-12 12:25, olcott wrote:
>>>>>> On 12/12/2020 1:13 PM, André G. Isaak wrote:
>>>>>>> On 2020-12-12 12:08, olcott wrote:
>>>>>>>> On 12/12/2020 1:00 PM, André G. Isaak wrote:
>>>>>>>>> On 2020-12-12 11:26, olcott wrote:
>>>>>>>>>> On 12/12/2020 12:08 PM, André G. Isaak wrote:
>>>>>>>>>>> On 2020-12-12 10:45, olcott wrote:
>>>>>>>>>>>> On 12/12/2020 11:40 AM, André G. Isaak wrote:
>>>>>>>>>>>>> On 2020-12-12 10:38, olcott wrote:
>>>>>>>>>>>>>> On 12/12/2020 11:12 AM, André G. Isaak wrote:
>>>>>>>>>>>>>>> On 2020-12-12 09:24, olcott wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>> <snip>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> The outermost Halts() always returns a value to its
>>>>>>>>>>>>>>>> caller even though it must sometimes abort the
>>>>>>>>>>>>>>>> simulations of inner infinite invocations of itself.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> And since it claims to be simulating those inner
>>>>>>>>>>>>>>> instances and to abort those instances only in cases
>>>>>>>>>>>>>>> where they would not otherwise halt, it is asserting that
>>>>>>>>>>>>>>> there *are* inputs to Halts() which will not halt. Ergo,
>>>>>>>>>>>>>>> it is asserting that Halts() is *not* a decider.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> ...in those cases where it does not halt and return a
>>>>>>>>>>>>>> value to its caller Halts() is not a decider. On those
>>>>>>>>>>>>>> invocations of Halts() where it does halt and return a
>>>>>>>>>>>>>> value to its caller it is a decider.
>>>>>>>>>>>>>
>>>>>>>>>>>>> A program is either a decider or it isn't. There's no such
>>>>>>>>>>>>> thing as a program which is sometimes a decider and
>>>>>>>>>>>>> sometimes isn't.
>>>>>>>>>>>>>
>>>>>>>>>>>>> André
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> You already know that is pure bullshit or the term "partial
>>>>>>>>>>>> decider" would not exist. What motive do you have for saying
>>>>>>>>>>>> things that you know are pure bullshit?
>>>>>>>>>>>
>>>>>>>>>>> A partial decider is not a decider. More importantly, it is
>>>>>>>>>>> not a "sometimes decider".
>>>>>>>>>>>
>>>>>>>>>>> A partial decider makes a correct decision for a particular
>>>>>>>>>>> class of inputs but may fail to halt for other inputs.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>> Your program sometimes halts and sometimes doesn't for the
>>>>>>>>>>> *same* inputs. So you cannot even claim your program is a
>>>>>>>>>>> partial decider, let alone an actual decider.
>>>>>>>>>>>
>>>>>>>>>>> André
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> So in other words you "believe" against logic that some
>>>>>>>>>> infinitely recursive invocations <do> return a result to their
>>>>>>>>>> caller. That sounds nutty to me.
>>>>>>>>>
>>>>>>>>> How you can possibly get that idea from what I wrote is utterly
>>>>>>>>> beyond me.
>>>>>>>>>
>>>>>>>>> I am saying that anything which has the possibility of getting
>>>>>>>>> caught in infinite recursion cannot return a result and
>>>>>>>>> therefore cannot constitute a decider.
>>>>>>>>>
>>>>>>>>> André
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> Except in those cases that it has not been caught in infinite
>>>>>>>> recursion and does return a result to its caller.
>>>>>>>>
>>>>>>>> Alternatively a function that can and does correctly detect
>>>>>>>> infinite recursion on itself and return its decision to its
>>>>>>>> caller does not count.
>>>>>>>>
>>>>>>>> Basically you are saying that it is wrong all of the time even
>>>>>>>> though it is right some of the time.
>>>>>>>
>>>>>>> No. I am saying that it is not a decider. A decider *must* return
>>>>>>> a result for *all* inputs. That's the definition of 'decider'.
>>>>>>> Something that only returns results in some instances is not a
>>>>>>> decider. I don't know how I can make this any clearer...
>>>>>>>
>>>>>>> André
>>>>>>>
>>>>>>
>>>>>> The way that you are defining it when a function does correctly
>>>>>> decide that it has been infinitely invoked that even though this
>>>>>> decision is correct it does not count.
>>>>>>
>>>>>> Since a partial decider <is> a decider for some inputs and not for
>>>>>> other inputs, then this same idea can be extended to some
>>>>>> invocations and not all invocations, otherwise correctly deciding
>>>>>> infinite recursion does not count even when the decision is correct.
>>>>>
>>>>> A partial decider is not a decider any more than a half-dollar is a
>>>>> dollar. A partial decider is something that correctly decides some
>>>>> cases, not something which is a decider in some cases. Things are
>>>>> either deciders or they aren't.
>>>>>
>>>> A partial decider that decides the {Linz, Sipser, Kozen}
>>>> counter-examples refutes these three proofs.
>>>>
>>>>> That a program correctly decides some cases does not make it a
>>>>> decider in those cases. You could call it a partial decider, but
>>>>> not a decider.
>>>>>
>>>>> However, in the case of your program, you can't even call it that
>>>>> because it sometimes returns and other times does not return *on
>>>>> the same input*. A partial decider is something which decides some
>>>>> set of inputs and fails to decide another, *disjoint* set of
>>>>> inputs. Something which gets different results for the same input
>>>>> isn't even a function, let alone a decider or partial decider.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> So in other words when a partial decider correctly determines that
>>>> it has been invoked in infinite recursion it must fix the bug in
>>>> this infinitely recursive invocation so that it can report its
>>>> infinitely recursive invocation to its infinitely recursive caller,
>>>> that is no longer infinitely recursive because it fixed this bug.
>>>>
>>>> <sarcasm>
>>>> That makes perfect sense to me.
>>>> </sarcasm>
>>>
>>> No, I did not say that. You need to make at least some effort to read
>>> for comprehension. I said that something which can be caught in
>>> infinite recursion is *not* a decider. This is getting rather
>>> tedious. Something that correctly decides some cases but not others
>>> could be a partial decider, but not if it decides the *same* input in
>>> some cases but not others.
>>>
>>
>> 01 void H_Hat(u32 P)
>> 02 {
>> 03Â Â u32 Input_Halts = DebugTrace(P, P);
>> 04Â Â if (Input_Halts)
>> 05Â Â Â Â HERE: goto HERE;
>> 06Â Â else
>> 07Â Â Â Â HALT
>> 08 }
>>
>> Halts((u32)H_Hat,(u32)H_Hat) is correctly decided** as not halting
>> because it aborts the invocation of itself on line 03.
>
> You've switched back from using Halts() to using DebugTrace(). Are these
> intended to be distinct functions?
>
>> ** Halts returns the correct halting determination.
>>
>> According to your way of defining a decider:
>> (a) Halts is not a decider even though it correctly decides.
>> (b) Halts would be a decider if it aborted the infinite recursion of
>> any other function besides itself.
>>
>> That is ridiculous!
> Look, a decider is a type of *function*. To be a function, something
> must consistently map the same input to the same result, but that isn't
> what you get above. Assuming that your DebugTrace() and Halts() are
> intended to be the same, you are claiming that
>
> Halts(H_Hat, H_Hat)
>
> returns false. This means Halts(H_Hat, H_Hat) is a finite computation.
>
> But by returning false is is also claiming that the instance of
> Halts(H_Hat, H_Hat) invoked from within H_Hat must be aborted as a
> non-halting function.
>
> This is a contradiction.
As I have said very many times (no one notices because they only glance
at a few of my words to contrive some lame basis for a rebuttal that
would fool the gullible):
Halts(H_Hat, H_Hat) is only a finite computation because it aborts the
otherwise infinite recursion of its input according to this criteria:
On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.
On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.
> Either Halts(H_Hat, H_Hat) is finite or it
> isn't. It can't be finite in one case and non-finite in the other given
> that it is the same function with the same input.
>
> André
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
> On 2020-12-14 07:25, olcott wrote:
>> On 12/12/2020 2:37 PM, André G. Isaak wrote:
>>> On 2020-12-12 13:01, olcott wrote:
>>>> On 12/12/2020 1:40 PM, André G. Isaak wrote:
>>>>> On 2020-12-12 12:25, olcott wrote:
>>>>>> On 12/12/2020 1:13 PM, André G. Isaak wrote:
>>>>>>> On 2020-12-12 12:08, olcott wrote:
>>>>>>>> On 12/12/2020 1:00 PM, André G. Isaak wrote:
>>>>>>>>> On 2020-12-12 11:26, olcott wrote:
>>>>>>>>>> On 12/12/2020 12:08 PM, André G. Isaak wrote:
>>>>>>>>>>> On 2020-12-12 10:45, olcott wrote:
>>>>>>>>>>>> On 12/12/2020 11:40 AM, André G. Isaak wrote:
>>>>>>>>>>>>> On 2020-12-12 10:38, olcott wrote:
>>>>>>>>>>>>>> On 12/12/2020 11:12 AM, André G. Isaak wrote:
>>>>>>>>>>>>>>> On 2020-12-12 09:24, olcott wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>> <snip>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> The outermost Halts() always returns a value to its
>>>>>>>>>>>>>>>> caller even though it must sometimes abort the
>>>>>>>>>>>>>>>> simulations of inner infinite invocations of itself.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> And since it claims to be simulating those inner
>>>>>>>>>>>>>>> instances and to abort those instances only in cases
>>>>>>>>>>>>>>> where they would not otherwise halt, it is asserting that
>>>>>>>>>>>>>>> there *are* inputs to Halts() which will not halt. Ergo,
>>>>>>>>>>>>>>> it is asserting that Halts() is *not* a decider.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> ...in those cases where it does not halt and return a
>>>>>>>>>>>>>> value to its caller Halts() is not a decider. On those
>>>>>>>>>>>>>> invocations of Halts() where it does halt and return a
>>>>>>>>>>>>>> value to its caller it is a decider.
>>>>>>>>>>>>>
>>>>>>>>>>>>> A program is either a decider or it isn't. There's no such
>>>>>>>>>>>>> thing as a program which is sometimes a decider and
>>>>>>>>>>>>> sometimes isn't.
>>>>>>>>>>>>>
>>>>>>>>>>>>> André
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> You already know that is pure bullshit or the term "partial
>>>>>>>>>>>> decider" would not exist. What motive do you have for saying
>>>>>>>>>>>> things that you know are pure bullshit?
>>>>>>>>>>>
>>>>>>>>>>> A partial decider is not a decider. More importantly, it is
>>>>>>>>>>> not a "sometimes decider".
>>>>>>>>>>>
>>>>>>>>>>> A partial decider makes a correct decision for a particular
>>>>>>>>>>> class of inputs but may fail to halt for other inputs.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>> Your program sometimes halts and sometimes doesn't for the
>>>>>>>>>>> *same* inputs. So you cannot even claim your program is a
>>>>>>>>>>> partial decider, let alone an actual decider.
>>>>>>>>>>>
>>>>>>>>>>> André
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> So in other words you "believe" against logic that some
>>>>>>>>>> infinitely recursive invocations <do> return a result to their
>>>>>>>>>> caller. That sounds nutty to me.
>>>>>>>>>
>>>>>>>>> How you can possibly get that idea from what I wrote is utterly
>>>>>>>>> beyond me.
>>>>>>>>>
>>>>>>>>> I am saying that anything which has the possibility of getting
>>>>>>>>> caught in infinite recursion cannot return a result and
>>>>>>>>> therefore cannot constitute a decider.
>>>>>>>>>
>>>>>>>>> André
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> Except in those cases that it has not been caught in infinite
>>>>>>>> recursion and does return a result to its caller.
>>>>>>>>
>>>>>>>> Alternatively a function that can and does correctly detect
>>>>>>>> infinite recursion on itself and return its decision to its
>>>>>>>> caller does not count.
>>>>>>>>
>>>>>>>> Basically you are saying that it is wrong all of the time even
>>>>>>>> though it is right some of the time.
>>>>>>>
>>>>>>> No. I am saying that it is not a decider. A decider *must* return
>>>>>>> a result for *all* inputs. That's the definition of 'decider'.
>>>>>>> Something that only returns results in some instances is not a
>>>>>>> decider. I don't know how I can make this any clearer...
>>>>>>>
>>>>>>> André
>>>>>>>
>>>>>>
>>>>>> The way that you are defining it when a function does correctly
>>>>>> decide that it has been infinitely invoked that even though this
>>>>>> decision is correct it does not count.
>>>>>>
>>>>>> Since a partial decider <is> a decider for some inputs and not for
>>>>>> other inputs, then this same idea can be extended to some
>>>>>> invocations and not all invocations, otherwise correctly deciding
>>>>>> infinite recursion does not count even when the decision is correct.
>>>>>
>>>>> A partial decider is not a decider any more than a half-dollar is a
>>>>> dollar. A partial decider is something that correctly decides some
>>>>> cases, not something which is a decider in some cases. Things are
>>>>> either deciders or they aren't.
>>>>>
>>>> A partial decider that decides the {Linz, Sipser, Kozen}
>>>> counter-examples refutes these three proofs.
>>>>
>>>>> That a program correctly decides some cases does not make it a
>>>>> decider in those cases. You could call it a partial decider, but
>>>>> not a decider.
>>>>>
>>>>> However, in the case of your program, you can't even call it that
>>>>> because it sometimes returns and other times does not return *on
>>>>> the same input*. A partial decider is something which decides some
>>>>> set of inputs and fails to decide another, *disjoint* set of
>>>>> inputs. Something which gets different results for the same input
>>>>> isn't even a function, let alone a decider or partial decider.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> So in other words when a partial decider correctly determines that
>>>> it has been invoked in infinite recursion it must fix the bug in
>>>> this infinitely recursive invocation so that it can report its
>>>> infinitely recursive invocation to its infinitely recursive caller,
>>>> that is no longer infinitely recursive because it fixed this bug.
>>>>
>>>> <sarcasm>
>>>> That makes perfect sense to me.
>>>> </sarcasm>
>>>
>>> No, I did not say that. You need to make at least some effort to read
>>> for comprehension. I said that something which can be caught in
>>> infinite recursion is *not* a decider. This is getting rather
>>> tedious. Something that correctly decides some cases but not others
>>> could be a partial decider, but not if it decides the *same* input in
>>> some cases but not others.
>>>
>>
>> 01 void H_Hat(u32 P)
>> 02 {
>> 03Â Â u32 Input_Halts = DebugTrace(P, P);
>> 04Â Â if (Input_Halts)
>> 05Â Â Â Â HERE: goto HERE;
>> 06Â Â else
>> 07Â Â Â Â HALT
>> 08 }
>>
>> Halts((u32)H_Hat,(u32)H_Hat) is correctly decided** as not halting
>> because it aborts the invocation of itself on line 03.
>
> You've switched back from using Halts() to using DebugTrace(). Are these
> intended to be distinct functions?
>
>> ** Halts returns the correct halting determination.
>>
>> According to your way of defining a decider:
>> (a) Halts is not a decider even though it correctly decides.
>> (b) Halts would be a decider if it aborted the infinite recursion of
>> any other function besides itself.
>>
>> That is ridiculous!
> Look, a decider is a type of *function*. To be a function, something
> must consistently map the same input to the same result, but that isn't
> what you get above. Assuming that your DebugTrace() and Halts() are
> intended to be the same, you are claiming that
>
> Halts(H_Hat, H_Hat)
>
> returns false. This means Halts(H_Hat, H_Hat) is a finite computation.
>
> But by returning false is is also claiming that the instance of
> Halts(H_Hat, H_Hat) invoked from within H_Hat must be aborted as a
> non-halting function.
>
> This is a contradiction.
As I have said very many times (no one notices because they only glance
at a few of my words to contrive some lame basis for a rebuttal that
would fool the gullible):
Halts(H_Hat, H_Hat) is only a finite computation because it aborts the
otherwise infinite recursion of its input according to this criteria:
On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.
On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.
> Either Halts(H_Hat, H_Hat) is finite or it
> isn't. It can't be finite in one case and non-finite in the other given
> that it is the same function with the same input.
>
> André
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott
Dec 14, 2020, 1:42:39 PM12/14/20
to
On 12/14/2020 9:32 AM, Malcolm McLean wrote:
> If Halts aborts itself, is it halted or aborted? That's the question.
>
Halts() simulates H_Hat() that invokes Halts() in infinite recursion.
Halts() stops simulating H_Hat() including its infinite recursive
invocation of Halts(), returning its non-halting decision to main()
where it is output.
> If we say "halted" then H_Hat inverts whatever result it returns,
It is not possible for an aborted function to invert any damn thing.
> and :Halts" is wrong. If we say "aborted" then "Halts" isn't a function,
> which is a slightly more subtle requirement of H_Hat.
Certainly an at least partial halt decider that bases its halting
decision by looking for patterns of behavior of its inputs can stop
simulating this input as soon as it detects any non-halting pattern.
It does not make any damn difference if it detects an infinite loop, or
infinite recursion. It also does not make any damn difference which
function is involved in infinite recursion. As long as Halts() detects
the non-halting behavior of its input then it can stop simulating this
input and report non-halting.
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("[Input_Would_Halt] =", Input_Would_Halt);
HALT;
}
I finally renamed my internal DebugTrace() to Halts() now that it
finally does return its correct halting decision to main().
>
Halts() simulates H_Hat() that invokes Halts() in infinite recursion.
Halts() stops simulating H_Hat() including its infinite recursive
invocation of Halts(), returning its non-halting decision to main()
where it is output.
> If we say "halted" then H_Hat inverts whatever result it returns,
It is not possible for an aborted function to invert any damn thing.
> and :Halts" is wrong. If we say "aborted" then "Halts" isn't a function,
> which is a slightly more subtle requirement of H_Hat.
Certainly an at least partial halt decider that bases its halting
decision by looking for patterns of behavior of its inputs can stop
simulating this input as soon as it detects any non-halting pattern.
It does not make any damn difference if it detects an infinite loop, or
infinite recursion. It also does not make any damn difference which
function is involved in infinite recursion. As long as Halts() detects
the non-halting behavior of its input then it can stop simulating this
input and report non-halting.
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("[Input_Would_Halt] =", Input_Would_Halt);
HALT;
}
I finally renamed my internal DebugTrace() to Halts() now that it
finally does return its correct halting decision to main().
Mr Flibble
Dec 15, 2020, 2:03:50 PM12/15/20
to
On 14/12/2020 18:41, olcott wrote:
> I finally renamed my internal DebugTrace() to Halts() now that it finally does return its correct halting decision to main().
>
Renaming your function to "Halt" does NOT make it a halt decider; it makes it an erroneously named function. Until your function can decide if a loop or recursion CONTAINING CONDITIONALS (i.e. branching logic) never terminates you DO NOT have a halt decider, you HAVE NOT refuted Turing and you HAVE NOT "solved" the Halting Problem.
> I finally renamed my internal DebugTrace() to Halts() now that it finally does return its correct halting decision to main().
>
/Flibble
--
😎
0 new messages