Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #1932 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2020-11-27 11:10 -0600 |
| Last post | 2020-11-27 17:09 -0600 |
| Articles | 20 on this page of 33 — 3 participants |
Back to article view | Back to comp.software-eng
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 11:10 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-27 17:24 +0000
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 11:54 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 13:34 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 14:04 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:24 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-27 21:57 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-30 11:55 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 21:06 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 15:14 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 22:48 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 17:23 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-30 23:54 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:08 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:18 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:59 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 01:40 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 19:48 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 08:41 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 08:52 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 21:30 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 16:34 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 23:10 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 12:12 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 18:35 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 12:54 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 10:08 -0600
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 01:23 +0000
Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 19:30 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 12:46 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:40 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:52 -0600
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 17:09 -0600
Page 1 of 2 [1] 2 Next page →
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-27 11:10 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) |
| Message-ID | <jLSdncNvGeKGrlzCnZ2dnUU7-I3NnZ2d@giganews.com> |
On 11/27/2020 10:57 AM, Mr Flibble wrote: > On 27/11/2020 16:52, olcott wrote: >> On 10/19/2020 12:45 PM, olcott wrote: >>> x86utm is a universal Turing Machine having the x86 language as >>> machine description language. It can directly execute the COFF object >>> file output of the Microsoft "C" compiler as long as the code does >>> not invoke any external libraries. All global data must be >>> initialized or it does not exist in the COFF object file. All >>> relocatable refernces are patched to point to their file offsets. >>> >>> This was the most difficult aspect of the entire x86utm system: >>> The operating system function DebugStep() can now invoke itself >>> recursively to an arbitrary depth. >>> >>> It can DebugStep() itself DebugStep()ing itself... >>> DebugStep()ing another function with an arbitrary hierarchy of >>> DebugStep()ing in-between. >>> >>> The halt decider aborts the execution of its target function and >>> reports not halting behavior as soon as it detects that its target >>> function would not otherwise halt. Without a DebugStep() function its >>> examination of the Target code wold be insufficiently granular. >>> >>> The code that correctly decides the conventional self-referential >>> halting problem counter-examples can now finally be written. This >>> code utterly depended upon the now finally completed DebugStep() >>> operating system function. >>> >>> This code exploits a key undiscovered aspect that is common to all >>> the conventional self-referential halting problem counter-examples. >>> >>> This key undiscovered aspect that makes all of the conventional >>> self-referential halting problem counter-examples decidable cannot >>> simply be dismissed out-of-hand without review when a fully >>> operational program shows that it does correctly decide elements of >>> the set of of conventional self-referential halting problem >>> counter-examples. > > You still haven't shown how non-halting behaviour is decided. > > Still nothing to see here. > > /Flibble > I have explained how non-halting is decided in complete detail many times. It turns out that the complete detail is so simple that no-one accepted that it was complete until I proved that it is complete to Mike. Here is the proof. The sequences of instructions from HERE to THERE and HERE to HERE are from actual execution traces. The x86 emulator screens out all dead code and only shows us the precise sequence of the code that is actually reached. -HERE: // current location - Instructions that cannot possibly exit a loop -THERE: goto HERE; To form a mathematical proof on the basis of the x86 language being construed as a formal language we only have to derive the complete list of every instruction that can possibly exit the above loop and if there are none of these between the labels HERE and THERE then we know that the loop is infinite. The case for infinite recursion is similar. -HERE: Call Function At Address X - Instructions that cannot possibly exit recursion -HERE: Call Function At Address X If there are no instructions that can possibly exit recursion between invocations of the same function from the same machine address, then recursion is infinite. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2020-11-27 17:24 +0000 |
| Message-ID | <xDawH.48368$%m67.27765@fx02.ams4> |
| In reply to | #1932 |
On 27/11/2020 17:10, olcott wrote: > On 11/27/2020 10:57 AM, Mr Flibble wrote: >> On 27/11/2020 16:52, olcott wrote: >>> On 10/19/2020 12:45 PM, olcott wrote: >>>> x86utm is a universal Turing Machine having the x86 language as machine description language. It can directly execute the COFF object file output of the Microsoft "C" compiler as long as the code does not invoke any external libraries. All global data must be initialized or it does not exist in the COFF object file. All relocatable refernces are patched to point to their file offsets. >>>> >>>> This was the most difficult aspect of the entire x86utm system: >>>> The operating system function DebugStep() can now invoke itself recursively to an arbitrary depth. >>>> >>>> It can DebugStep() itself DebugStep()ing itself... >>>> DebugStep()ing another function with an arbitrary hierarchy of DebugStep()ing in-between. >>>> >>>> The halt decider aborts the execution of its target function and reports not halting behavior as soon as it detects that its target function would not otherwise halt. Without a DebugStep() function its examination of the Target code wold be insufficiently granular. >>>> >>>> The code that correctly decides the conventional self-referential halting problem counter-examples can now finally be written. This code utterly depended upon the now finally completed DebugStep() operating system function. >>>> >>>> This code exploits a key undiscovered aspect that is common to all the conventional self-referential halting problem counter-examples. >>>> >>>> This key undiscovered aspect that makes all of the conventional self-referential halting problem counter-examples decidable cannot simply be dismissed out-of-hand without review when a fully operational program shows that it does correctly decide elements of the set of of conventional self-referential halting problem counter-examples. >> >> You still haven't shown how non-halting behaviour is decided. >> >> Still nothing to see here. >> >> /Flibble >> > > I have explained how non-halting is decided in complete detail many times. It turns out that the complete detail is so simple that no-one accepted that it was complete until I proved that it is complete to Mike. Here is the proof. > > The sequences of instructions from HERE to THERE and HERE to HERE are from actual execution traces. The x86 emulator screens out all dead code and only shows us the precise sequence of the code that is actually reached. > > -HERE: // current location > - Instructions that cannot possibly exit a loop > -THERE: goto HERE; > > To form a mathematical proof on the basis of the x86 language being construed as a formal language we only have to derive the complete list of every instruction that can possibly exit the above loop and if there are none of these between the labels HERE and THERE then we know that the loop is infinite. > > The case for infinite recursion is similar. > > -HERE: Call Function At Address X > - Instructions that cannot possibly exit recursion > -HERE: Call Function At Address X > > If there are no instructions that can possibly exit recursion between invocations of the same function from the same machine address, then recursion is infinite. Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't sufficient to decide non-halting behaviour for an arbitrary program given arbitrary input. /Flibble -- ¬
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-27 11:54 -0600 |
| Message-ID | <aqudnTRmQ87RoFzCnZ2dnUU7-QnNnZ2d@giganews.com> |
| In reply to | #1933 |
On 11/27/2020 11:24 AM, Mr Flibble wrote:
> On 27/11/2020 17:10, olcott wrote:
>> On 11/27/2020 10:57 AM, Mr Flibble wrote:
>>> On 27/11/2020 16:52, olcott wrote:
>>>> On 10/19/2020 12:45 PM, olcott wrote:
>>>>> x86utm is a universal Turing Machine having the x86 language as
>>>>> machine description language. It can directly execute the COFF
>>>>> object file output of the Microsoft "C" compiler as long as the
>>>>> code does not invoke any external libraries. All global data must
>>>>> be initialized or it does not exist in the COFF object file. All
>>>>> relocatable refernces are patched to point to their file offsets.
>>>>>
>>>>> This was the most difficult aspect of the entire x86utm system:
>>>>> The operating system function DebugStep() can now invoke itself
>>>>> recursively to an arbitrary depth.
>>>>>
>>>>> It can DebugStep() itself DebugStep()ing itself...
>>>>> DebugStep()ing another function with an arbitrary hierarchy of
>>>>> DebugStep()ing in-between.
>>>>>
>>>>> The halt decider aborts the execution of its target function and
>>>>> reports not halting behavior as soon as it detects that its target
>>>>> function would not otherwise halt. Without a DebugStep() function
>>>>> its examination of the Target code wold be insufficiently granular.
>>>>>
>>>>> The code that correctly decides the conventional self-referential
>>>>> halting problem counter-examples can now finally be written. This
>>>>> code utterly depended upon the now finally completed DebugStep()
>>>>> operating system function.
>>>>>
>>>>> This code exploits a key undiscovered aspect that is common to all
>>>>> the conventional self-referential halting problem counter-examples.
>>>>>
>>>>> This key undiscovered aspect that makes all of the conventional
>>>>> self-referential halting problem counter-examples decidable cannot
>>>>> simply be dismissed out-of-hand without review when a fully
>>>>> operational program shows that it does correctly decide elements of
>>>>> the set of of conventional self-referential halting problem
>>>>> counter-examples.
>>>
>>> You still haven't shown how non-halting behaviour is decided.
>>>
>>> Still nothing to see here.
>>>
>>> /Flibble
>>>
>>
>> I have explained how non-halting is decided in complete detail many
>> times. It turns out that the complete detail is so simple that no-one
>> accepted that it was complete until I proved that it is complete to
>> Mike. Here is the proof.
>>
>> The sequences of instructions from HERE to THERE and HERE to HERE are
>> from actual execution traces. The x86 emulator screens out all dead
>> code and only shows us the precise sequence of the code that is
>> actually reached.
>>
>> -HERE: // current location
>> - Instructions that cannot possibly exit a loop
>> -THERE: goto HERE;
>>
>> To form a mathematical proof on the basis of the x86 language being
>> construed as a formal language we only have to derive the complete
>> list of every instruction that can possibly exit the above loop and if
>> there are none of these between the labels HERE and THERE then we know
>> that the loop is infinite.
>>
>> The case for infinite recursion is similar.
>>
>> -HERE: Call Function At Address X
>> - Instructions that cannot possibly exit recursion
>> -HERE: Call Function At Address X
>>
>> If there are no instructions that can possibly exit recursion between
>> invocations of the same function from the same machine address, then
>> recursion is infinite.
>
> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
> sufficient to decide non-halting behaviour for an arbitrary program
> given arbitrary input.
>
> /Flibble
>
It is sufficient to definitively decide all of the non-halting cases
meeting the above criteria including this one:
void H_Hat(u32 P)
{
u32 Would_Halt = Halts(P, P);
if (!Would_Halt)
HALT
else
HERE: goto HERE;
}
Halts(H_Hat, H_Hat);
The above code (computationally equivalent to all of the conventional
halting probem proof counter-examples) is provably decidable by the
criteria provided.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-27 13:34 -0600 |
| Message-ID | <eZednUauDfsiyVzCnZ2dnUU7-N_NnZ2d@giganews.com> |
| In reply to | #1934 |
On 11/27/2020 1:08 PM, Mike Terry wrote:
> On 27/11/2020 18:24, Richard Damon wrote:
>> On 11/27/20 12:54 PM, olcott wrote:
>>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>>> On 27/11/2020 17:10, olcott wrote:
>>>>> On 11/27/2020 10:57 AM, Mr Flibble wrote:
>>>>>> On 27/11/2020 16:52, olcott wrote:
>>>>>>> On 10/19/2020 12:45 PM, olcott wrote:
>>>>>>>> x86utm is a universal Turing Machine having the x86 language as
>>>>>>>> machine description language. It can directly execute the COFF
>>>>>>>> object file output of the Microsoft "C" compiler as long as the
>>>>>>>> code does not invoke any external libraries. All global data must
>>>>>>>> be initialized or it does not exist in the COFF object file. All
>>>>>>>> relocatable refernces are patched to point to their file offsets.
>>>>>>>>
>>>>>>>> This was the most difficult aspect of the entire x86utm system:
>>>>>>>> The operating system function DebugStep() can now invoke itself
>>>>>>>> recursively to an arbitrary depth.
>>>>>>>>
>>>>>>>> It can DebugStep() itself DebugStep()ing itself...
>>>>>>>> DebugStep()ing another function with an arbitrary hierarchy of
>>>>>>>> DebugStep()ing in-between.
>>>>>>>>
>>>>>>>> The halt decider aborts the execution of its target function and
>>>>>>>> reports not halting behavior as soon as it detects that its target
>>>>>>>> function would not otherwise halt. Without a DebugStep() function
>>>>>>>> its examination of the Target code wold be insufficiently granular.
>>>>>>>>
>>>>>>>> The code that correctly decides the conventional self-referential
>>>>>>>> halting problem counter-examples can now finally be written. This
>>>>>>>> code utterly depended upon the now finally completed DebugStep()
>>>>>>>> operating system function.
>>>>>>>>
>>>>>>>> This code exploits a key undiscovered aspect that is common to all
>>>>>>>> the conventional self-referential halting problem counter-examples.
>>>>>>>>
>>>>>>>> This key undiscovered aspect that makes all of the conventional
>>>>>>>> self-referential halting problem counter-examples decidable cannot
>>>>>>>> simply be dismissed out-of-hand without review when a fully
>>>>>>>> operational program shows that it does correctly decide elements
>>>>>>>> of the set of of conventional self-referential halting problem
>>>>>>>> counter-examples.
>>>>>>
>>>>>> You still haven't shown how non-halting behaviour is decided.
>>>>>>
>>>>>> Still nothing to see here.
>>>>>>
>>>>>> /Flibble
>>>>>>
>>>>>
>>>>> I have explained how non-halting is decided in complete detail many
>>>>> times. It turns out that the complete detail is so simple that no-one
>>>>> accepted that it was complete until I proved that it is complete to
>>>>> Mike. Here is the proof.
>>>>>
>>>>> The sequences of instructions from HERE to THERE and HERE to HERE are
>>>>> from actual execution traces. The x86 emulator screens out all dead
>>>>> code and only shows us the precise sequence of the code that is
>>>>> actually reached.
>>>>>
>>>>> -HERE: // current location
>>>>> - Instructions that cannot possibly exit a loop
>>>>> -THERE: goto HERE;
>>>>>
>>>>> To form a mathematical proof on the basis of the x86 language being
>>>>> construed as a formal language we only have to derive the complete
>>>>> list of every instruction that can possibly exit the above loop and
>>>>> if there are none of these between the labels HERE and THERE then we
>>>>> know that the loop is infinite.
>>>>>
>>>>> The case for infinite recursion is similar.
>>>>>
>>>>> -HERE: Call Function At Address X
>>>>> - Instructions that cannot possibly exit recursion
>>>>> -HERE: Call Function At Address X
>>>>>
>>>>> If there are no instructions that can possibly exit recursion between
>>>>> invocations of the same function from the same machine address, then
>>>>> recursion is infinite.
>>>>
>>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
>>>> sufficient to decide non-halting behaviour for an arbitrary program
>>>> given arbitrary input.
>>>>
>>>> /Flibble
>>>>
>>>
>>> It is sufficient to definitively decide all of the non-halting cases
>>> meeting the above criteria including this one:
>>>
>>> void H_Hat(u32 P)
>>> {
>>> u32 Would_Halt = Halts(P, P);
>>> if (!Would_Halt)
>>> HALT
>>> else
>>> HERE: goto HERE;
>>> }
>>>
>>> Halts(H_Hat, H_Hat);
>>>
>>> The above code (computationally equivalent to all of the conventional
>>> halting probem proof counter-examples) is provably decidable by the
>>> criteria provided.
>>>
>>
>> Except that if we look at the FULL trace of the problem execution of
>> H_Hat, we see conditionals in the loop.
>>
>
> Maybe so, but - the whole issue of "conditionals in the loop" is a bogus
> issue. The underlying test for infinite recursion IS JUST WRONG. I.e.
> the whole "no conditionals in the loop" idea doesn't work. So
> demonstrating there really are "missed conditionals in the loop" is a
> red herring.
>
> In a way it's a good thing that PO has picked up on this aspect, and
> delivered his "proof" that he is right - because he is WRONG and now has
> pinned his colours to the mast in a way that can easily be SHOWN to be
> wrong. This will reveal that PO is a complete DUFFER who's incapable of
> delivering anything of value in such a technical area. When that
> happens, I don't expect PO to acknowledge anything of course, so it
> won't really make much difference to this newsgroup.
>
Mere empty rhetoric utterly bereft of any actual reasoning.
I did not expect you to stoop to this level of tactics, this is the sort
of thing that Ben does.
If you can provide a valid counter-example feel free. To the best of my
knowledge valid counter-examples are categorically impossible.
Every "counter-example" so far has at best been the straw-man error of
reasoning.
If you understand the basic principle that a TMD simulated by a UTM is
computationally equivalent to the direct execution of a TM then you
would understand that:
(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to
(b) TM1 executing TM2 executing TM1 executing TM2
Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
actual computation.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-27 14:04 -0600 |
| Message-ID | <5O2dnZEAp4wwxlzCnZ2dnUU7-YvNnZ2d@giganews.com> |
| In reply to | #1942 |
On 11/27/2020 1:34 PM, olcott wrote:
> On 11/27/2020 1:08 PM, Mike Terry wrote:
>> On 27/11/2020 18:24, Richard Damon wrote:
>>> On 11/27/20 12:54 PM, olcott wrote:
>>>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>>>> On 27/11/2020 17:10, olcott wrote:
>>>>>> On 11/27/2020 10:57 AM, Mr Flibble wrote:
>>>>>>> On 27/11/2020 16:52, olcott wrote:
>>>>>>>> On 10/19/2020 12:45 PM, olcott wrote:
>>>>>>>>> x86utm is a universal Turing Machine having the x86 language as
>>>>>>>>> machine description language. It can directly execute the COFF
>>>>>>>>> object file output of the Microsoft "C" compiler as long as the
>>>>>>>>> code does not invoke any external libraries. All global data must
>>>>>>>>> be initialized or it does not exist in the COFF object file. All
>>>>>>>>> relocatable refernces are patched to point to their file offsets.
>>>>>>>>>
>>>>>>>>> This was the most difficult aspect of the entire x86utm system:
>>>>>>>>> The operating system function DebugStep() can now invoke itself
>>>>>>>>> recursively to an arbitrary depth.
>>>>>>>>>
>>>>>>>>> It can DebugStep() itself DebugStep()ing itself...
>>>>>>>>> DebugStep()ing another function with an arbitrary hierarchy of
>>>>>>>>> DebugStep()ing in-between.
>>>>>>>>>
>>>>>>>>> The halt decider aborts the execution of its target function and
>>>>>>>>> reports not halting behavior as soon as it detects that its target
>>>>>>>>> function would not otherwise halt. Without a DebugStep() function
>>>>>>>>> its examination of the Target code wold be insufficiently
>>>>>>>>> granular.
>>>>>>>>>
>>>>>>>>> The code that correctly decides the conventional self-referential
>>>>>>>>> halting problem counter-examples can now finally be written. This
>>>>>>>>> code utterly depended upon the now finally completed DebugStep()
>>>>>>>>> operating system function.
>>>>>>>>>
>>>>>>>>> This code exploits a key undiscovered aspect that is common to all
>>>>>>>>> the conventional self-referential halting problem
>>>>>>>>> counter-examples.
>>>>>>>>>
>>>>>>>>> This key undiscovered aspect that makes all of the conventional
>>>>>>>>> self-referential halting problem counter-examples decidable cannot
>>>>>>>>> simply be dismissed out-of-hand without review when a fully
>>>>>>>>> operational program shows that it does correctly decide elements
>>>>>>>>> of the set of of conventional self-referential halting problem
>>>>>>>>> counter-examples.
>>>>>>>
>>>>>>> You still haven't shown how non-halting behaviour is decided.
>>>>>>>
>>>>>>> Still nothing to see here.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> I have explained how non-halting is decided in complete detail many
>>>>>> times. It turns out that the complete detail is so simple that no-one
>>>>>> accepted that it was complete until I proved that it is complete to
>>>>>> Mike. Here is the proof.
>>>>>>
>>>>>> The sequences of instructions from HERE to THERE and HERE to HERE are
>>>>>> from actual execution traces. The x86 emulator screens out all dead
>>>>>> code and only shows us the precise sequence of the code that is
>>>>>> actually reached.
>>>>>>
>>>>>> -HERE: // current location
>>>>>> - Instructions that cannot possibly exit a loop
>>>>>> -THERE: goto HERE;
>>>>>>
>>>>>> To form a mathematical proof on the basis of the x86 language being
>>>>>> construed as a formal language we only have to derive the complete
>>>>>> list of every instruction that can possibly exit the above loop and
>>>>>> if there are none of these between the labels HERE and THERE then we
>>>>>> know that the loop is infinite.
>>>>>>
>>>>>> The case for infinite recursion is similar.
>>>>>>
>>>>>> -HERE: Call Function At Address X
>>>>>> - Instructions that cannot possibly exit recursion
>>>>>> -HERE: Call Function At Address X
>>>>>>
>>>>>> If there are no instructions that can possibly exit recursion between
>>>>>> invocations of the same function from the same machine address, then
>>>>>> recursion is infinite.
>>>>>
>>>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
>>>>> sufficient to decide non-halting behaviour for an arbitrary program
>>>>> given arbitrary input.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> It is sufficient to definitively decide all of the non-halting cases
>>>> meeting the above criteria including this one:
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Would_Halt = Halts(P, P);
>>>> if (!Would_Halt)
>>>> HALT
>>>> else
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> Halts(H_Hat, H_Hat);
>>>>
>>>> The above code (computationally equivalent to all of the conventional
>>>> halting probem proof counter-examples) is provably decidable by the
>>>> criteria provided.
>>>>
>>>
>>> Except that if we look at the FULL trace of the problem execution of
>>> H_Hat, we see conditionals in the loop.
>>>
>>
>> Maybe so, but - the whole issue of "conditionals in the loop" is a
>> bogus issue. The underlying test for infinite recursion IS JUST
>> WRONG. I.e. the whole "no conditionals in the loop" idea doesn't
>> work. So demonstrating there really are "missed conditionals in the
>> loop" is a red herring.
>>
>> In a way it's a good thing that PO has picked up on this aspect, and
>> delivered his "proof" that he is right - because he is WRONG and now
>> has pinned his colours to the mast in a way that can easily be SHOWN
>> to be wrong. This will reveal that PO is a complete DUFFER who's
>> incapable of delivering anything of value in such a technical area.
>> When that happens, I don't expect PO to acknowledge anything of
>> course, so it won't really make much difference to this newsgroup.
>>
> Mere empty rhetoric utterly bereft of any actual reasoning.
>
> I did not expect you to stoop to this level of tactics, this is the sort
> of thing that Ben does.
>
> If you can provide a valid counter-example feel free. To the best of my
> knowledge valid counter-examples are categorically impossible.
>
> Every "counter-example" so far has at best been the straw-man error of
> reasoning.
>
>
>
>
> If you understand the basic principle that a TMD simulated by a UTM is
> computationally equivalent to the direct execution of a TM then you
> would understand that:
>
> (a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
> is computationally equivalent to
>
> (b) TM1 executing TM2 executing TM1 executing TM2
>
> Thus your RECURSIVE EMULATIONS, are shown to have no effect on the
> actual computation.
Thus when I simply screen out all of the emulator instructions and only
focus on the emulated instructions I am only screening out instructions
that have no effect on the actual computation what-so-ever.
Output_Debug_Trace() [00010bc4] size(148) capacity(65536)
[000005a4](01) 55 push ebp
[000005a5](02) 8bec mov ebp,esp
[000005a7](01) 51 push ecx
[000005a8](07) c745fc74050000 mov [ebp-04],00000574
[000005af](03) 8b45fc mov eax,[ebp-04]
[000005b2](01) 50 push eax
[000005b3](03) 8b4dfc mov ecx,[ebp-04]
[000005b6](01) 51 push ecx
[000005b7](05) e898fdffff call 00000354 ----CALL[00000354]
[00000574](01) 55 push ebp
[00000575](02) 8bec mov ebp,esp
[00000577](01) 51 push ecx
[00000578](03) 8b4508 mov eax,[ebp+08]
[0000057b](01) 50 push eax
[0000057c](03) 8b4d08 mov ecx,[ebp+08]
[0000057f](01) 51 push ecx
[00000580](05) e8cffdffff call 00000354 ----CALL[00000354]
[00000574](01) 55 push ebp
[00000575](02) 8bec mov ebp,esp
[00000577](01) 51 push ecx
[00000578](03) 8b4508 mov eax,[ebp+08]
[0000057b](01) 50 push eax
[0000057c](03) 8b4d08 mov ecx,[ebp+08]
[0000057f](01) 51 push ecx
[00000580](05) e8cffdffff call 00000354 ----CALL[00000354]
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-27 15:24 -0600 |
| Message-ID | <a82dnd0yv6Xm81zCnZ2dnUU7-IvNnZ2d@giganews.com> |
| In reply to | #1942 |
On 11/27/2020 3:04 PM, Mike Terry wrote:
> On 27/11/2020 19:34, olcott wrote:
>> On 11/27/2020 1:08 PM, Mike Terry wrote:
>>> On 27/11/2020 18:24, Richard Damon wrote:
>>>> On 11/27/20 12:54 PM, olcott wrote:
>>>>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>>>>> On 27/11/2020 17:10, olcott wrote:
>>>>>>> On 11/27/2020 10:57 AM, Mr Flibble wrote:
>>>>>>>> On 27/11/2020 16:52, olcott wrote:
>>>>>>>>> On 10/19/2020 12:45 PM, olcott wrote:
>>>>>>>>>> x86utm is a universal Turing Machine having the x86 language as
>>>>>>>>>> machine description language. It can directly execute the COFF
>>>>>>>>>> object file output of the Microsoft "C" compiler as long as the
>>>>>>>>>> code does not invoke any external libraries. All global data must
>>>>>>>>>> be initialized or it does not exist in the COFF object file. All
>>>>>>>>>> relocatable refernces are patched to point to their file offsets.
>>>>>>>>>>
>>>>>>>>>> This was the most difficult aspect of the entire x86utm system:
>>>>>>>>>> The operating system function DebugStep() can now invoke itself
>>>>>>>>>> recursively to an arbitrary depth.
>>>>>>>>>>
>>>>>>>>>> It can DebugStep() itself DebugStep()ing itself...
>>>>>>>>>> DebugStep()ing another function with an arbitrary hierarchy of
>>>>>>>>>> DebugStep()ing in-between.
>>>>>>>>>>
>>>>>>>>>> The halt decider aborts the execution of its target function and
>>>>>>>>>> reports not halting behavior as soon as it detects that its
>>>>>>>>>> target
>>>>>>>>>> function would not otherwise halt. Without a DebugStep() function
>>>>>>>>>> its examination of the Target code wold be insufficiently
>>>>>>>>>> granular.
>>>>>>>>>>
>>>>>>>>>> The code that correctly decides the conventional self-referential
>>>>>>>>>> halting problem counter-examples can now finally be written. This
>>>>>>>>>> code utterly depended upon the now finally completed DebugStep()
>>>>>>>>>> operating system function.
>>>>>>>>>>
>>>>>>>>>> This code exploits a key undiscovered aspect that is common to
>>>>>>>>>> all
>>>>>>>>>> the conventional self-referential halting problem
>>>>>>>>>> counter-examples.
>>>>>>>>>>
>>>>>>>>>> This key undiscovered aspect that makes all of the conventional
>>>>>>>>>> self-referential halting problem counter-examples decidable
>>>>>>>>>> cannot
>>>>>>>>>> simply be dismissed out-of-hand without review when a fully
>>>>>>>>>> operational program shows that it does correctly decide elements
>>>>>>>>>> of the set of of conventional self-referential halting problem
>>>>>>>>>> counter-examples.
>>>>>>>>
>>>>>>>> You still haven't shown how non-halting behaviour is decided.
>>>>>>>>
>>>>>>>> Still nothing to see here.
>>>>>>>>
>>>>>>>> /Flibble
>>>>>>>>
>>>>>>>
>>>>>>> I have explained how non-halting is decided in complete detail many
>>>>>>> times. It turns out that the complete detail is so simple that
>>>>>>> no-one
>>>>>>> accepted that it was complete until I proved that it is complete to
>>>>>>> Mike. Here is the proof.
>>>>>>>
>>>>>>> The sequences of instructions from HERE to THERE and HERE to HERE
>>>>>>> are
>>>>>>> from actual execution traces. The x86 emulator screens out all dead
>>>>>>> code and only shows us the precise sequence of the code that is
>>>>>>> actually reached.
>>>>>>>
>>>>>>> -HERE: // current location
>>>>>>> - Instructions that cannot possibly exit a loop
>>>>>>> -THERE: goto HERE;
>>>>>>>
>>>>>>> To form a mathematical proof on the basis of the x86 language being
>>>>>>> construed as a formal language we only have to derive the complete
>>>>>>> list of every instruction that can possibly exit the above loop and
>>>>>>> if there are none of these between the labels HERE and THERE then we
>>>>>>> know that the loop is infinite.
>>>>>>>
>>>>>>> The case for infinite recursion is similar.
>>>>>>>
>>>>>>> -HERE: Call Function At Address X
>>>>>>> - Instructions that cannot possibly exit recursion
>>>>>>> -HERE: Call Function At Address X
>>>>>>>
>>>>>>> If there are no instructions that can possibly exit recursion
>>>>>>> between
>>>>>>> invocations of the same function from the same machine address, then
>>>>>>> recursion is infinite.
>>>>>>
>>>>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation
>>>>>> isn't
>>>>>> sufficient to decide non-halting behaviour for an arbitrary program
>>>>>> given arbitrary input.
>>>>>>
>>>>>> /Flibble
>>>>>>
>>>>>
>>>>> It is sufficient to definitively decide all of the non-halting cases
>>>>> meeting the above criteria including this one:
>>>>>
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>> u32 Would_Halt = Halts(P, P);
>>>>> if (!Would_Halt)
>>>>> HALT
>>>>> else
>>>>> HERE: goto HERE;
>>>>> }
>>>>>
>>>>> Halts(H_Hat, H_Hat);
>>>>>
>>>>> The above code (computationally equivalent to all of the conventional
>>>>> halting probem proof counter-examples) is provably decidable by the
>>>>> criteria provided.
>>>>>
>>>>
>>>> Except that if we look at the FULL trace of the problem execution of
>>>> H_Hat, we see conditionals in the loop.
>>>>
>>>
>>> Maybe so, but - the whole issue of "conditionals in the loop" is a
>>> bogus issue. The underlying test for infinite recursion IS JUST
>>> WRONG. I.e. the whole "no conditionals in the loop" idea doesn't
>>> work. So demonstrating there really are "missed conditionals in the
>>> loop" is a red herring.
>>>
>>> In a way it's a good thing that PO has picked up on this aspect, and
>>> delivered his "proof" that he is right - because he is WRONG and now
>>> has pinned his colours to the mast in a way that can easily be SHOWN
>>> to be wrong. This will reveal that PO is a complete DUFFER who's
>>> incapable of delivering anything of value in such a technical area.
>>> When that happens, I don't expect PO to acknowledge anything of
>>> course, so it won't really make much difference to this newsgroup.
>>>
>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>
>> I did not expect you to stoop to this level of tactics, this is the sort
>> of thing that Ben does.
>>
>
> I was replying to Richard, not you.
I will pay closer attention to that.
> I was not "arguing" with you, just
> pointing out something Richard may not (or may) have realised. If
> Richard wants me to clarify, then he can ask questions, and also I've
> said elsewhere that at some point I'll start a new thread on the topic
> (but I'm busy at the moment).
>
> Meanwhile in direct responses to your claim I've pointed out why your
> "proof" isn't a proof at all, and I've pointed out the nature of your
> mistake: you don't understand the difference between recursive CALLs
> and recursive EMULATIONS.
That the UTM emulation of a TMD of A TM is computationally equivalent to
the direct execution of this same TM proves:
When <A> emulates <B> emulates <A>
this is computationally equivalent to
A calls B calls A
> Your explanation as to why there's no
> difference just doesn't work, for reasons I've given. In the end,
> you're reduced to just saying over and over "it's true and I've proved it".
>
>> If you can provide a valid counter-example feel free. To the best of my
>> knowledge valid counter-examples are categorically impossible.
>
> If YOU make a claim, it's up to you to prove it, not up to others to
> hunt around for counterexamples. (But I'll probably put one in the new
> thread if/when I start it.)
>
> Mike.
>
So far it merely seems like you are demonstrating a lack of sufficient
knowledge of the equivalence that I just pointed out:
UTM1(<TM1>, DATA) ≡ TM1(DATA)
thus
UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA))
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-27 21:57 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) |
| Message-ID | <tvqdnQnZIdgWV1zCnZ2dnUU7-XvNnZ2d@giganews.com> |
| In reply to | #1942 |
On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
> olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:
>
>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>
>> I did not expect you to stoop to this level of tactics, this is the
>> sort of thing that Ben does.
>
> Here's the sort of "empty rhetoric utterly bereft of any actual
> reasoning" that I post. I challenged you to post a halt decider after a
> clear definition from me of what I mean:
>
> A halt decider (in this context) is a function F such that F(P, I) is
> true if, and only if, P(I) is a finite computation and false
> otherwise.
If you can have the discipline to very very carefully analyze my answers
as if there was a real chance that I am correct then it should be quite
easy to verify in your own mind that I am actually correct.
This is the key to understanding that I am correct.
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.
When the simulator stops simulating H_Hat before H_Hat ever gets any
return value from Halts this makes it impossible for H_Hat to do the
opposite of whatever Halts decides, thus making all the conventional HP
proofs lose their entire basis.
> You posted this:
>
> bool Halts(u32 P, u32 I)
> {
> bool Halted = false;
> bool Aborted = false;
> while (!Halted && !Aborted)
> {
> Halted = DebugStep(P, I);
> Aborted = Needs_To_Be_Aborted();
> }
> return !Aborted;
> }
>
> and I then posted the confounding example:
>
> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>
> along with these two facts about it:
>
> (a) Halts(Confound_Halts, Confound_Halts) returns false, and
> (b) Confound_Halts(Confound_Halts) is a finite computation.
>
> My conclusion was to ask:
>
> Therefore Halts is not a halt decider. Which of the these do you
> disagree with?
>
> Your response was to ignore these points and, instead, to give your own
> defintion of what the right answer is, whilst carefuly avoiding saying
> that it differed from mine (and everyone else's).
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 11:55 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) |
| Message-ID | <oY2dnbTxTOKDr1jCnZ2dnUU7-QPNnZ2d@giganews.com> |
| In reply to | #1956 |
On 11/30/2020 11:25 AM, Mr Flibble wrote: > On 30/11/2020 02:40, olcott wrote: >> On 11/29/2020 7:42 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> On 11/27/2020 9:29 PM, Ben Bacarisse wrote: >>>>> olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes: >>>>> >>>>>> Mere empty rhetoric utterly bereft of any actual reasoning. >>>>>> >>>>>> I did not expect you to stoop to this level of tactics, this is the >>>>>> sort of thing that Ben does. >>>>> >>>>> Here's the sort of "empty rhetoric utterly bereft of any actual >>>>> reasoning" that I post. I challenged you to post a halt decider >>>>> after a >>>>> clear definition from me of what I mean: >>>>> >>>>> A halt decider (in this context) is a function F such that F(P, >>>>> I) is >>>>> true if, and only if, P(I) is a finite computation and false >>>>> otherwise. >>>> >>>> If you can have the discipline to very very carefully analyze my >>>> answers as if there was a real chance that I am correct then it should >>>> be quite easy to verify in your own mind that I am actually correct. >>> >>> Yet another opportunity to accept the correct definition side stepped. >>> I ended up writing more but then saw that you had finally been clear >>> about my other questions so I am not sure this sub-thread really matters >>> any more. >>> >>> <cut stuff you ignored here bue have have discussed elsewhere> >>> >> >> 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. >> >> Just like there is no exception to this rule: >> ∀n ∈ ℕ ((n > 5) → (N > 3)) >> >> Every computation that would not halt unless its simulation was halted >> is by logical necessity a non-halting computation. >> >> Both the x86 virtual machine computation and its simulated Turing >> machine description equivalent computation would never halt unless >> their simulator stopped simulating them. >> >> In logic and mathematics, necessity and sufficiency are terms used to >> describe a conditional or implicational relationship between two >> statements. ... a sufficient condition is one which produces the said >> condition. https://en.wikipedia.org/wiki/Necessity_and_sufficiency >> >> When-so-ever >> A computation would not halt unless its simulation was halted >> this computation is necessarily always a non-halting computation. >> THE SUFFICIENCY CONDITION IS FULLY MET !!! >> >> H_Hat <is> a computation that would not halt unless its simulation was >> halted ∴ (no matter how much you don't like it) H_Hat is a non-halting >> computation. > > You still haven't explained how your non-halting decider can decide if > an arbitrary program given arbitrary input halts. My goal is not to actually solve the halting problem because to do this I would have to write a computer program that is ALL-KNOWING. What I have done instead is show the exact steps required to decide the conventional halting problem proof counter examples of defining an input that does the opposite of whatever the halt decider decides: Now we construct a new Turing machine D with H as a subroutine. This new TM calls H to determine what M does when the input to M is its own description <M>. Once D has determined this information, it does the opposite. That is, it rejects if M accepts and accepts if M does not accept. The following is a description of D. (Sipser 1997) D = "On input <M>, where M is a TM: 1. Run H on input <M, <M>>. 2. Output the opposite of what H outputs; that is if H accepts, reject and if H rejects, accept." http://www.liarparadox.org/sipser_165.pdf Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: PWS Publishing Company (165-167) > Publish your working code (complete solution) so we can see past the > guff and look at the actual implementation and then give it a test case > that it fails to analyse correctly. My actual code is not ready for prime-time however the halt decider does provide the full execution trace that its decision is based on (every single assembly language instruction that was executed prior to terminating the simulation) and from this execution trace it can be verified that the decider did make the correct halt decision. > Until you produce a working implementation in the form of code all you > have is conjecture; i.e. no refutation of the HP. > > /Flibble > -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-11-30 21:06 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) |
| Message-ID | <20201130125512.705@kylheku.com> |
| In reply to | #1989 |
On 2020-11-30, olcott <NoOne@NoWhere.com> wrote: >> You still haven't explained how your non-halting decider can decide if >> an arbitrary program given arbitrary input halts. > > My goal is not to actually solve the halting problem because to do this > I would have to write a computer program that is ALL-KNOWING. An imaginary "all knowing" entity is called an "oracle". You believe that calculating halting requires an "oracle" program; yet you don't see that as an impediment against computability?
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 15:14 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <I5udnWySYf1e_VjCnZ2dnUU7-KmdnZ2d@giganews.com> |
| In reply to | #1992 |
On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>> You still haven't explained how your non-halting decider can decide if
>>> an arbitrary program given arbitrary input halts.
>>
>> My goal is not to actually solve the halting problem because to do this
>> I would have to write a computer program that is ALL-KNOWING.
>
> An imaginary "all knowing" entity is called an "oracle".
>
> You believe that calculating halting requires an "oracle" program;
> yet you don't see that as an impediment against computability?
>
I already posted the complete execution trace of the details of how
Halts decides halting on H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (!Input_Halts)
HALT
else
HERE: goto HERE;
}
When Halts() always simulates its input it is obvious that
Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
decided as non halting.
Just like some people really believe that 250% of all of the beings in
the universe voted for Trump some people deny infinite recursion even
when it slaps them in the face.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-11-30 22:48 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <20201130142819.218@kylheku.com> |
| In reply to | #1993 |
["Followup-To:" header set to comp.theory.]
On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>> You still haven't explained how your non-halting decider can decide if
>>>> an arbitrary program given arbitrary input halts.
>>>
>>> My goal is not to actually solve the halting problem because to do this
>>> I would have to write a computer program that is ALL-KNOWING.
>>
>> An imaginary "all knowing" entity is called an "oracle".
>>
>> You believe that calculating halting requires an "oracle" program;
>> yet you don't see that as an impediment against computability?
>>
>
> I already posted the complete execution trace of the details of how
> Halts decides halting on H_Hat()
>
> void H_Hat(u32 P)
> {
> u32 Input_Halts = Halts(P, P);
> if (!Input_Halts)
> HALT
> else
> HERE: goto HERE;
> }
>
> When Halts() always simulates its input it is obvious that
> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
> decided as non halting.
You're blind to the obvious issue that H_Hat isn't a single
function/program. It's a *class* of programs.
The usual proofs just give a simple, direct representative of that class
for the sake of clarity, but it's obvious that an effective such program
can be written in an unlimited number of ways.
There is no way that a halting decider can distinguish whether the input
is one of the infinitely large class of H_Hat programs, or whether it an
innocent test case. That itself is a decision problem equivalent to
halting.
If you have make a halting-equivalent decision before deciding halting,
you've lost.
No level of simulation or execution trace monitoring, or any
number of nestings thereof, can fix this.
You're also forgeting that the Halts has to be *correct* on all inputs.
The author of Halts cannot be so obsessed with defeating H_Hat programs
that he overlooks correctness.
Suppose that Halts includes some simple hacks in order to guess whether
some trivial infinite loop or recursion is happening inside P (evidence
that it's being gamed). Those simple hacks can be always be used to
create a test case which coaxes an incorrect result out of Halts.
The author of H_Hat procedure always has the last word. The proposed
halting function Halt exists first, and H_Hat is crafted afterward,
using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
instance from an infinite class of programs, not one specific program.
--
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 17:23 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <EfqdnV8AFZ1341jCnZ2dnUU7-XvNnZ2d@giganews.com> |
| In reply to | #1995 |
On 11/30/2020 4:48 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>> You still haven't explained how your non-halting decider can decide if
>>>>> an arbitrary program given arbitrary input halts.
>>>>
>>>> My goal is not to actually solve the halting problem because to do this
>>>> I would have to write a computer program that is ALL-KNOWING.
>>>
>>> An imaginary "all knowing" entity is called an "oracle".
>>>
>>> You believe that calculating halting requires an "oracle" program;
>>> yet you don't see that as an impediment against computability?
>>>
>>
>> I already posted the complete execution trace of the details of how
>> Halts decides halting on H_Hat()
>>
>> void H_Hat(u32 P)
>> {
>> u32 Input_Halts = Halts(P, P);
>> if (!Input_Halts)
>> HALT
>> else
>> HERE: goto HERE;
>> }
>>
>> When Halts() always simulates its input it is obvious that
>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
>> decided as non halting.
>
> You're blind to the obvious issue that H_Hat isn't a single
> function/program. It's a *class* of programs.
>
Every element of this class (where Halts() bases its decision on
simulating its input) specifies infinite recursion.
> The usual proofs just give a simple, direct representative of that class
> for the sake of clarity, but it's obvious that an effective such program
> can be written in an unlimited number of ways.
>
> There is no way that a halting decider can distinguish whether the input
> is one of the infinitely large class of H_Hat programs, or whether it an
> innocent test case. That itself is a decision problem equivalent to
> halting.
>
> If you have make a halting-equivalent decision before deciding halting,
> you've lost.
For the above H_Hat template it does not matter what state transitions
comprise the unspecified (wildcard) state transitions: ⊢*
H.q0 wMw ⊢* H.yes if M applied to w halts, and
H.q0 wMw ⊢* H.no if M applied to w does not halt.
as long as the halt decider bases its decision on simulating its input
then every single element of the class of H_Hat computations specifies
infinite recursion.
> No level of simulation or execution trace monitoring, or any
> number of nestings thereof, can fix this.
>
> You're also forgeting that the Halts has to be *correct* on all inputs.
> The author of Halts cannot be so obsessed with defeating H_Hat programs
> that he overlooks correctness.
So then if I correctly refute all the conventional proofs this does not
count until I actually solve the halting problem?
> Suppose that Halts includes some simple hacks in order to guess whether
> some trivial infinite loop or recursion is happening inside P (evidence
> that it's being gamed). Those simple hacks can be always be used to
> create a test case which coaxes an incorrect result out of Halts.
>
> The author of H_Hat procedure always has the last word. The proposed
> halting function Halt exists first, and H_Hat is crafted afterward,
> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
> instance from an infinite class of programs, not one specific program.
>
The key thing that you are utterly oblivious to is that I just showed
how to correctly decide the "impossible to decide" template of all the
conventional "do the opposite of whatever the halt decider decides"
halting problem counter-examples.
That is easy to miss when one starts with the fundamental goal:
How do I show Pete that he is wrong?
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2020-11-30 23:54 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <dDfxH.176510$b5kb.95272@fx15.ams4> |
| In reply to | #1997 |
On 30/11/2020 23:23, olcott wrote:
> On 11/30/2020 4:48 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.theory.]
>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>>> You still haven't explained how your non-halting decider can decide if
>>>>>> an arbitrary program given arbitrary input halts.
>>>>>
>>>>> My goal is not to actually solve the halting problem because to do this
>>>>> I would have to write a computer program that is ALL-KNOWING.
>>>>
>>>> An imaginary "all knowing" entity is called an "oracle".
>>>>
>>>> You believe that calculating halting requires an "oracle" program;
>>>> yet you don't see that as an impediment against computability?
>>>>
>>>
>>> I already posted the complete execution trace of the details of how
>>> Halts decides halting on H_Hat()
>>>
>>> void H_Hat(u32 P)
>>> {
>>> u32 Input_Halts = Halts(P, P);
>>> if (!Input_Halts)
>>> HALT
>>> else
>>> HERE: goto HERE;
>>> }
>>>
>>> When Halts() always simulates its input it is obvious that
>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
>>> decided as non halting.
>>
>> You're blind to the obvious issue that H_Hat isn't a single
>> function/program. It's a *class* of programs.
>>
>
> Every element of this class (where Halts() bases its decision on simulating its input) specifies infinite recursion.
>
>
>> The usual proofs just give a simple, direct representative of that class
>> for the sake of clarity, but it's obvious that an effective such program
>> can be written in an unlimited number of ways.
>>
>> There is no way that a halting decider can distinguish whether the input
>> is one of the infinitely large class of H_Hat programs, or whether it an
>> innocent test case. That itself is a decision problem equivalent to
>> halting.
>>
>> If you have make a halting-equivalent decision before deciding halting,
>> you've lost.
>
> For the above H_Hat template it does not matter what state transitions comprise the unspecified (wildcard) state transitions: ⊢*
>
> H.q0 wMw ⊢* H.yes if M applied to w halts, and
> H.q0 wMw ⊢* H.no if M applied to w does not halt.
>
> as long as the halt decider bases its decision on simulating its input then every single element of the class of H_Hat computations specifies infinite recursion.
>
>> No level of simulation or execution trace monitoring, or any
>> number of nestings thereof, can fix this.
>>
>> You're also forgeting that the Halts has to be *correct* on all inputs.
>> The author of Halts cannot be so obsessed with defeating H_Hat programs
>> that he overlooks correctness.
>
> So then if I correctly refute all the conventional proofs this does not count until I actually solve the halting problem?
>
>> Suppose that Halts includes some simple hacks in order to guess whether
>> some trivial infinite loop or recursion is happening inside P (evidence
>> that it's being gamed). Those simple hacks can be always be used to
>> create a test case which coaxes an incorrect result out of Halts.
>>
>> The author of H_Hat procedure always has the last word. The proposed
>> halting function Halt exists first, and H_Hat is crafted afterward,
>> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
>> instance from an infinite class of programs, not one specific program.
>>
>
> The key thing that you are utterly oblivious to is that I just showed how to correctly decide the "impossible to decide" template of all the conventional "do the opposite of whatever the halt decider decides" halting problem counter-examples.
>
> That is easy to miss when one starts with the fundamental goal:
> How do I show Pete that he is wrong?
Your wrongness is fractal in nature. Deliver an open source working implementation that backs up your claims or fuck off, spammer.
/Flibble
--
¬
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 18:08 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <FZ6dnTSyifT-FFjCnZ2dnUU7-fnNnZ2d@giganews.com> |
| In reply to | #1998 |
On 11/30/2020 5:54 PM, Mr Flibble wrote:
> On 30/11/2020 23:23, olcott wrote:
>> On 11/30/2020 4:48 PM, Kaz Kylheku wrote:
>>> ["Followup-To:" header set to comp.theory.]
>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>>>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>>>> You still haven't explained how your non-halting decider can
>>>>>>> decide if
>>>>>>> an arbitrary program given arbitrary input halts.
>>>>>>
>>>>>> My goal is not to actually solve the halting problem because to do
>>>>>> this
>>>>>> I would have to write a computer program that is ALL-KNOWING.
>>>>>
>>>>> An imaginary "all knowing" entity is called an "oracle".
>>>>>
>>>>> You believe that calculating halting requires an "oracle" program;
>>>>> yet you don't see that as an impediment against computability?
>>>>>
>>>>
>>>> I already posted the complete execution trace of the details of how
>>>> Halts decides halting on H_Hat()
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Input_Halts = Halts(P, P);
>>>> if (!Input_Halts)
>>>> HALT
>>>> else
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> When Halts() always simulates its input it is obvious that
>>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
>>>> decided as non halting.
>>>
>>> You're blind to the obvious issue that H_Hat isn't a single
>>> function/program. It's a *class* of programs.
>>>
>>
>> Every element of this class (where Halts() bases its decision on
>> simulating its input) specifies infinite recursion.
>>
>>
>>> The usual proofs just give a simple, direct representative of that class
>>> for the sake of clarity, but it's obvious that an effective such program
>>> can be written in an unlimited number of ways.
>>>
>>> There is no way that a halting decider can distinguish whether the input
>>> is one of the infinitely large class of H_Hat programs, or whether it an
>>> innocent test case. That itself is a decision problem equivalent to
>>> halting.
>>>
>>> If you have make a halting-equivalent decision before deciding halting,
>>> you've lost.
>>
>> For the above H_Hat template it does not matter what state transitions
>> comprise the unspecified (wildcard) state transitions: ⊢*
>>
>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
>> H.q0 wMw ⊢* H.no if M applied to w does not halt.
>>
>> as long as the halt decider bases its decision on simulating its input
>> then every single element of the class of H_Hat computations specifies
>> infinite recursion.
>>
>>> No level of simulation or execution trace monitoring, or any
>>> number of nestings thereof, can fix this.
>>>
>>> You're also forgeting that the Halts has to be *correct* on all inputs.
>>> The author of Halts cannot be so obsessed with defeating H_Hat programs
>>> that he overlooks correctness.
>>
>> So then if I correctly refute all the conventional proofs this does
>> not count until I actually solve the halting problem?
>>
>>> Suppose that Halts includes some simple hacks in order to guess whether
>>> some trivial infinite loop or recursion is happening inside P (evidence
>>> that it's being gamed). Those simple hacks can be always be used to
>>> create a test case which coaxes an incorrect result out of Halts.
>>>
>>> The author of H_Hat procedure always has the last word. The proposed
>>> halting function Halt exists first, and H_Hat is crafted afterward,
>>> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
>>> instance from an infinite class of programs, not one specific program.
>>>
>>
>> The key thing that you are utterly oblivious to is that I just showed
>> how to correctly decide the "impossible to decide" template of all the
>> conventional "do the opposite of whatever the halt decider decides"
>> halting problem counter-examples.
>>
>> That is easy to miss when one starts with the fundamental goal:
>> How do I show Pete that he is wrong?
>
> Your wrongness is fractal in nature. Deliver an open source working
> implementation that backs up your claims or fuck off, spammer.
>
> /Flibble
>
If you can't verify what I said on the basis the infinite recursion that
I just proved, you won't be able to understand the source code either.
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Input_Halts = Halts(P, P);
>>>> if (!Input_Halts)
>>>> HALT
>>>> else
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> When Halts() always simulates its input it is obvious that
for the whole class of computations specified by the above template
>>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion
>>>> thus can be decided as non halting.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 18:18 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <odOdnRng2b18FljCnZ2dnUU7-I3NnZ2d@giganews.com> |
| In reply to | #1998 |
On 11/30/2020 5:54 PM, Mr Flibble wrote:
> On 30/11/2020 23:23, olcott wrote:
>> On 11/30/2020 4:48 PM, Kaz Kylheku wrote:
>>> ["Followup-To:" header set to comp.theory.]
>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>>>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>>>> You still haven't explained how your non-halting decider can
>>>>>>> decide if
>>>>>>> an arbitrary program given arbitrary input halts.
>>>>>>
>>>>>> My goal is not to actually solve the halting problem because to do
>>>>>> this
>>>>>> I would have to write a computer program that is ALL-KNOWING.
>>>>>
>>>>> An imaginary "all knowing" entity is called an "oracle".
>>>>>
>>>>> You believe that calculating halting requires an "oracle" program;
>>>>> yet you don't see that as an impediment against computability?
>>>>>
>>>>
>>>> I already posted the complete execution trace of the details of how
>>>> Halts decides halting on H_Hat()
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Input_Halts = Halts(P, P);
>>>> if (!Input_Halts)
>>>> HALT
>>>> else
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> When Halts() always simulates its input it is obvious that
>>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
>>>> decided as non halting.
>>>
>>> You're blind to the obvious issue that H_Hat isn't a single
>>> function/program. It's a *class* of programs.
>>>
>>
>> Every element of this class (where Halts() bases its decision on
>> simulating its input) specifies infinite recursion.
>>
>>
>>> The usual proofs just give a simple, direct representative of that class
>>> for the sake of clarity, but it's obvious that an effective such program
>>> can be written in an unlimited number of ways.
>>>
>>> There is no way that a halting decider can distinguish whether the input
>>> is one of the infinitely large class of H_Hat programs, or whether it an
>>> innocent test case. That itself is a decision problem equivalent to
>>> halting.
>>>
>>> If you have make a halting-equivalent decision before deciding halting,
>>> you've lost.
>>
>> For the above H_Hat template it does not matter what state transitions
>> comprise the unspecified (wildcard) state transitions: ⊢*
>>
>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
>> H.q0 wMw ⊢* H.no if M applied to w does not halt.
>>
>> as long as the halt decider bases its decision on simulating its input
>> then every single element of the class of H_Hat computations specifies
>> infinite recursion.
>>
>>> No level of simulation or execution trace monitoring, or any
>>> number of nestings thereof, can fix this.
>>>
>>> You're also forgeting that the Halts has to be *correct* on all inputs.
>>> The author of Halts cannot be so obsessed with defeating H_Hat programs
>>> that he overlooks correctness.
>>
>> So then if I correctly refute all the conventional proofs this does
>> not count until I actually solve the halting problem?
>>
>>> Suppose that Halts includes some simple hacks in order to guess whether
>>> some trivial infinite loop or recursion is happening inside P (evidence
>>> that it's being gamed). Those simple hacks can be always be used to
>>> create a test case which coaxes an incorrect result out of Halts.
>>>
>>> The author of H_Hat procedure always has the last word. The proposed
>>> halting function Halt exists first, and H_Hat is crafted afterward,
>>> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
>>> instance from an infinite class of programs, not one specific program.
>>>
>>
>> The key thing that you are utterly oblivious to is that I just showed
>> how to correctly decide the "impossible to decide" template of all the
>> conventional "do the opposite of whatever the halt decider decides"
>> halting problem counter-examples.
>>
>> That is easy to miss when one starts with the fundamental goal:
>> How do I show Pete that he is wrong?
>
> Your wrongness is fractal in nature. Deliver an open source working
> implementation that backs up your claims or fuck off, spammer.
>
> /Flibble
>
int DebugTrace(u32 P, u32 I)
{
((int(*)(int))P)(I);
return 1;
}
void H_Hat(u32 P)
{
u32 Aborted = DebugTrace(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}
int main()
{
u32 P = (u32)H_Hat;
DebugTrace(P, P);
HALT;
}
From the above infinite recursion it is easy to see that when
DebugTrace(P, P) is replaced with a full x86 emulator that we still have
infinite recursion.
This logically entails that any halt decider based on an x86 emulator
would be also infinitely recursive too. (such as the first H_Hat above).
This logically entails that we can correctly decide not halting on the
whole class of computations specified by the origibal H_Hat above, as
long as the halt decider is based on x86 emulation.
This logically entails that we can decide not halting on the equivalent
computation where an actual Turing machine partial halt decider bases
its decision on simulating its input Turing machine description.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 18:59 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <I9udnSLXI9rpCFjCnZ2dnUU7-e3NnZ2d@giganews.com> |
| In reply to | #2000 |
On 11/30/2020 6:18 PM, olcott wrote:
> On 11/30/2020 5:54 PM, Mr Flibble wrote:
>> On 30/11/2020 23:23, olcott wrote:
>>> On 11/30/2020 4:48 PM, Kaz Kylheku wrote:
>>>> ["Followup-To:" header set to comp.theory.]
>>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>>>>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>> You still haven't explained how your non-halting decider can
>>>>>>>> decide if
>>>>>>>> an arbitrary program given arbitrary input halts.
>>>>>>>
>>>>>>> My goal is not to actually solve the halting problem because to
>>>>>>> do this
>>>>>>> I would have to write a computer program that is ALL-KNOWING.
>>>>>>
>>>>>> An imaginary "all knowing" entity is called an "oracle".
>>>>>>
>>>>>> You believe that calculating halting requires an "oracle" program;
>>>>>> yet you don't see that as an impediment against computability?
>>>>>>
>>>>>
>>>>> I already posted the complete execution trace of the details of how
>>>>> Halts decides halting on H_Hat()
>>>>>
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>> u32 Input_Halts = Halts(P, P);
>>>>> if (!Input_Halts)
>>>>> HALT
>>>>> else
>>>>> HERE: goto HERE;
>>>>> }
>>>>>
>>>>> When Halts() always simulates its input it is obvious that
>>>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
>>>>> decided as non halting.
>>>>
>>>> You're blind to the obvious issue that H_Hat isn't a single
>>>> function/program. It's a *class* of programs.
>>>>
>>>
>>> Every element of this class (where Halts() bases its decision on
>>> simulating its input) specifies infinite recursion.
>>>
>>>
>>>> The usual proofs just give a simple, direct representative of that
>>>> class
>>>> for the sake of clarity, but it's obvious that an effective such
>>>> program
>>>> can be written in an unlimited number of ways.
>>>>
>>>> There is no way that a halting decider can distinguish whether the
>>>> input
>>>> is one of the infinitely large class of H_Hat programs, or whether
>>>> it an
>>>> innocent test case. That itself is a decision problem equivalent to
>>>> halting.
>>>>
>>>> If you have make a halting-equivalent decision before deciding halting,
>>>> you've lost.
>>>
>>> For the above H_Hat template it does not matter what state
>>> transitions comprise the unspecified (wildcard) state transitions: ⊢*
>>>
>>> H.q0 wMw ⊢* H.yes if M applied to w halts, and
>>> H.q0 wMw ⊢* H.no if M applied to w does not halt.
>>>
>>> as long as the halt decider bases its decision on simulating its
>>> input then every single element of the class of H_Hat computations
>>> specifies infinite recursion.
>>>
>>>> No level of simulation or execution trace monitoring, or any
>>>> number of nestings thereof, can fix this.
>>>>
>>>> You're also forgeting that the Halts has to be *correct* on all inputs.
>>>> The author of Halts cannot be so obsessed with defeating H_Hat programs
>>>> that he overlooks correctness.
>>>
>>> So then if I correctly refute all the conventional proofs this does
>>> not count until I actually solve the halting problem?
>>>
>>>> Suppose that Halts includes some simple hacks in order to guess whether
>>>> some trivial infinite loop or recursion is happening inside P (evidence
>>>> that it's being gamed). Those simple hacks can be always be used to
>>>> create a test case which coaxes an incorrect result out of Halts.
>>>>
>>>> The author of H_Hat procedure always has the last word. The proposed
>>>> halting function Halt exists first, and H_Hat is crafted afterward,
>>>> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
>>>> instance from an infinite class of programs, not one specific program.
>>>>
>>>
>>> The key thing that you are utterly oblivious to is that I just showed
>>> how to correctly decide the "impossible to decide" template of all
>>> the conventional "do the opposite of whatever the halt decider
>>> decides" halting problem counter-examples.
>>>
>>> That is easy to miss when one starts with the fundamental goal:
>>> How do I show Pete that he is wrong?
>>
>> Your wrongness is fractal in nature. Deliver an open source working
>> implementation that backs up your claims or fuck off, spammer.
>>
>> /Flibble
>>
>
> int DebugTrace(u32 P, u32 I)
> {
> ((int(*)(int))P)(I);
> return 1;
> }
>
> void H_Hat(u32 P)
> {
> u32 Aborted = DebugTrace(P, P);
> if (Aborted)
> HALT
> else
> HERE: goto HERE;
> }
>
> int main()
> {
> u32 P = (u32)H_Hat;
> DebugTrace(P, P);
> HALT;
> }
>
> From the above infinite recursion it is easy to see that when
> DebugTrace(P, P) is replaced with a full x86 emulator that we still have
> infinite recursion.
>
> This logically entails that any halt decider based on an x86 emulator
> would be also infinitely recursive too. (such as the first H_Hat above).
>
> This logically entails that we can correctly decide not halting on the
> whole class of computations specified by the origibal H_Hat above, as
> long as the halt decider is based on x86 emulation.
>
> This logically entails that we can decide not halting on the equivalent
> computation where an actual Turing machine partial halt decider bases
> its decision on simulating its input Turing machine description.
>
This last part may be a little more difficult to see because textbooks
probably never delve into the case where a UTM is simulating its own
Turing Machine Description simulating this same Turing Machine
Description. It may not be clear that this is the TM equivalent of
recursive invocation:
UTM1(<TM1>, DATA) ≡ TM1(DATA)
∴
UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA))
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-01 01:40 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <20201130172804.625@kylheku.com> |
| In reply to | #2000 |
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> int DebugTrace(u32 P, u32 I)
> {
> ((int(*)(int))P)(I);
> return 1;
> }
>
> void H_Hat(u32 P)
> {
> u32 Aborted = DebugTrace(P, P);
> if (Aborted)
> HALT
> else
> HERE: goto HERE;
> }
>
> int main()
> {
> u32 P = (u32)H_Hat;
> DebugTrace(P, P);
> HALT;
> }
>
> From the above infinite recursion it is easy to see that when
> DebugTrace(P, P) is replaced with a full x86 emulator that we still have
> infinite recursion.
In that case we must detect the recursion and report that the program
does not halt; we can't just let it go on. This means that we are
looking for a specific pattern of execution which looks like runaway
recursion.
Problem is, H_Hat can be this (among other possible structures in a
similar vain):
void H_Hat(u32 P)
{
Decoy_1003(P); // One of an infinite library of decoys
u32 Aborted = DebugTrace(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}
Some of the decoys terminate, and so the DebugTrace line is
executed. Some do not terminate.
The manners in which the non-terminating ones fail to terminate is
completely arbitrary; it doesn't necessarily look anything like the
infinite recursion execution trace pattern.
Stepping through a program to decide its halting is completely
wrongheaded. We cannot decide halting that way. If we actually
execute a program P on input I, it either halts (whereupon halting
is decided) or does not, in which case halting remains undecided.
To decide halting means to calculate, in a finite number of steps,
whether any P on any I halts or does not halt.
Allowing P to execute, and monitoring it for specific non-termination
patterns does not add up to a halting decider.
The problem is that as you execute P(I), looking for it to hit
one of the specific non-terminating patterns, it might appear not
to be hitting any of those patterns---and yet not terminating!
Your only choices are:
1) step yet anoher instruction cycle and hope that one of the
non-termination patterns (such as a specific instance of runaway
recursion) appears, so you can conclude "does not terminate".
2) give up.
But (2) means you must report "undecided": you have failed to
decide whether P halts on I.
--
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 19:48 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <T_qdnVVBhKNOPVjCnZ2dnUU7-I3NnZ2d@giganews.com> |
| In reply to | #2004 |
On 11/30/2020 7:40 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> int DebugTrace(u32 P, u32 I)
>> {
>> ((int(*)(int))P)(I);
>> return 1;
>> }
>>
>> void H_Hat(u32 P)
>> {
>> u32 Aborted = DebugTrace(P, P);
>> if (Aborted)
>> HALT
>> else
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> u32 P = (u32)H_Hat;
>> DebugTrace(P, P);
>> HALT;
>> }
>>
>> From the above infinite recursion it is easy to see that when
>> DebugTrace(P, P) is replaced with a full x86 emulator that we still have
>> infinite recursion.
>
> In that case we must detect the recursion and report that the program
> does not halt; we can't just let it go on. This means that we are
> looking for a specific pattern of execution which looks like runaway
> recursion.
>
> Problem is, H_Hat can be this (among other possible structures in a
> similar vain):
The key is that whenever Halts is based on emulation that every instance
of the template of H_Hat shown above <is> infinitely recursive.
I skimmed what you said below and it is all beside the point that I just
made. The H_Hat template <is> the template of every conventional halting
problem proof, thus deciding this one template refutes all these proofs.
> void H_Hat(u32 P)
> {
> Decoy_1003(P); // One of an infinite library of decoys
>
> u32 Aborted = DebugTrace(P, P);
> if (Aborted)
> HALT
> else
> HERE: goto HERE;
> }
>
> Some of the decoys terminate, and so the DebugTrace line is
> executed. Some do not terminate.
>
> The manners in which the non-terminating ones fail to terminate is
> completely arbitrary; it doesn't necessarily look anything like the
> infinite recursion execution trace pattern.
>
> Stepping through a program to decide its halting is completely
> wrongheaded. We cannot decide halting that way. If we actually
> execute a program P on input I, it either halts (whereupon halting
> is decided) or does not, in which case halting remains undecided.
>
> To decide halting means to calculate, in a finite number of steps,
> whether any P on any I halts or does not halt.
>
> Allowing P to execute, and monitoring it for specific non-termination
> patterns does not add up to a halting decider.
>
> The problem is that as you execute P(I), looking for it to hit
> one of the specific non-terminating patterns, it might appear not
> to be hitting any of those patterns---and yet not terminating!
>
> Your only choices are:
>
> 1) step yet anoher instruction cycle and hope that one of the
> non-termination patterns (such as a specific instance of runaway
> recursion) appears, so you can conclude "does not terminate".
>
> 2) give up.
>
> But (2) means you must report "undecided": you have failed to
> decide whether P halts on I.
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-01 08:41 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <20201201002056.333@kylheku.com> |
| In reply to | #2006 |
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote: > I skimmed what you said below and it is all beside the point that I just > made. Here we go: this is how you dismiss situations that reveal flaws in your so-called work, and then continue to claim that no flaws have been found. > The H_Hat template <is> the template of every conventional halting > problem proof, thus deciding this one template refutes all these proofs. In other words, you're attacking a strawman version of the proof, by taking a particular pseudo-code template literally. You're not taking on the general technique given in the proof.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-01 08:52 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <ftqdnT2Vt805xVvCnZ2dnUU7-bfNnZ2d@giganews.com> |
| In reply to | #2011 |
On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> I skimmed what you said below and it is all beside the point that I just
>> made.
>
> Here we go: this is how you dismiss situations that reveal flaws in your
> so-called work, and then continue to claim that no flaws have been found.
>
>> The H_Hat template <is> the template of every conventional halting
>> problem proof, thus deciding this one template refutes all these proofs.
>
> In other words, you're attacking a strawman version of the proof,
> by taking a particular pseudo-code template literally.
>
> You're not taking on the general technique given in the proof.
>
If you try and provide the reasoning supporting this empty assertion you
will find that there is none.
This is computationally equivalent to every conventional halting problem
counter-example that "does the opposite of whatever the halt decide
decides":
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (!Input_Halts)
HALT
else
HERE: goto HERE;
}
You can claim that it is not equivalent the same way that you can claim
that there are 10,000 fairies dancing on the head of every pin.
x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
What you cannot do is show that I am incorrect. We are at the point
where no one has even slightly plausible rebuttals.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
Page 1 of 2 [1] 2 Next page →
Back to top | Article view | comp.software-eng
csiph-web