Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(39 days of review and no mistakes found)
19 views
Skip to first unread message
olcott
Nov 27, 2020, 11:53:08 AM11/27/20
to
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.
>
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
> 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.
>
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott
Nov 29, 2020, 9:40:54 PM11/29/20
to
On 11/29/2020 7:42 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
>>> olcott "Ĥ does not copy its input" <No...@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.
> olcott <No...@NoWhere.com> writes:
>
>> On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
>>> olcott "Ĥ does not copy its input" <No...@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.
olcott
Dec 1, 2020, 10:14:27 AM12/1/20
to
On 12/1/2020 6:00 AM, Malcolm McLean wrote:
> On Tuesday, 1 December 2020 at 08:42:01 UTC, Kaz Kylheku wrote:
>> On 2020-12-01, olcott <No...@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.
>>
> No, that's reasonable. If he can produc a pair of Turing machines,
> one of which is a "partial halt decider", the other which calls that
> decider and inverts the result, and somehow gets consistent results
> on the call to the decider and the direct run, then he's refuted the proof.
>
> The halt decider doesn't have to handle every case, and it doesn't have to
> work for the infinite possible variations on the H_Hat theme. You just
> need one counter-example and the proof falls.
>
Bingo !!! Thanks for your support !!!
> On Tuesday, 1 December 2020 at 08:42:01 UTC, Kaz Kylheku wrote:
>> On 2020-12-01, olcott <No...@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.
>>
> No, that's reasonable. If he can produc a pair of Turing machines,
> one of which is a "partial halt decider", the other which calls that
> decider and inverts the result, and somehow gets consistent results
> on the call to the decider and the direct run, then he's refuted the proof.
>
> The halt decider doesn't have to handle every case, and it doesn't have to
> work for the infinite possible variations on the H_Hat theme. You just
> need one counter-example and the proof falls.
>
Bingo !!! Thanks for your support !!!
olcott
Dec 1, 2020, 10:34:23 AM12/1/20
to
On 12/1/2020 9:22 AM, Andy Walker wrote:
> On 01/12/2020 01:40, Kaz Kylheku wrote:
>> Stepping through a program to decide its halting is completely
>> wrongheaded.
>
> It's not /completely/ wrong-headed. ...
>
>> 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.
> [...]
>> 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.
>
> ... The set of P and I of a given size [measured in some
> reasonable way, such as the number of bytes needed to define P and
> to list I] is finite, and "easily" enumerated. For a given P,I,
> define N_P,I to be 0 if P doesn't halt on I, and otherwise to be
> the number of steps taken by P before halting. Let S be the max
> over that set of P,I of N_P,I. Then an emulation of P on I for
> S steps shows either that P on I halts or that it will never
> halt. But, you object, we need to know whether P on I halts
> before we can calculate S. True, I riposte, but we don't need
> to know S exactly, any bound /whatsoever/ on S will suffice.
>
> Now the argument can go either of two ways. (a) Since
> the HP is "unsolvable", this shows that S is uncomputable, even
> though it's just any sufficiently large, and otherwise perfectly
> unexceptional, integer. Or (b), by an argument very similar to
> Busy Beaver theory, we can show directly that S is uncomputable
> and deduce that the HP is "unsolvable". [This proof is independent
> of the "Linz H_hat" argument that PO so dislikes, and also of the
> two-liner that Linz prefers, as given also by Mr Flibble.]
>
> IOW, emulation is doomed to failure, but not in such an
> obvious way that it's wrong-headed, which I would reserve for
> approaches to problems that anyone should be able to see in
> advance are not going to work.
>
> [I put "unsolvable" in quotes as shorthand for "there is
> no Turing machine or near equivalent that solves the general
> problem", as any fule kno.*]
>
> ____
> * https://en.wikipedia.org/wiki/Nigel_Molesworth
>
Here is another choice from fully operational code.
The only way that you can maintain your false believe that I am
incorrect is to make sure to not pay attention to the following complete
execution trace of fully operational code.
void H_Hat(u32 P)
{
u32 Aborted = DebugTrace(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}
int main()
{
DebugTrace((u32)H_Hat, (u32)H_Hat);
HALT;
}
_H_Hat()
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354
[00000595](03) 83c408 add esp,+08
[00000598](03) 8945fc mov [ebp-04],eax
[0000059b](04) 837dfc00 cmp dword [ebp-04],+00
[0000059f](02) 7403 jz 000005a4
[000005a1](01) f4 hlt
[000005a2](02) eb02 jmp 000005a6
[000005a4](02) ebfe jmp 000005a4
[000005a6](02) 8be5 mov esp,ebp
[000005a8](01) 5d pop ebp
[000005a9](01) c3 ret
_main()
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
[000005bc](05) 6884050000 push 00000584
[000005c1](05) e88efdffff call 00000354
[000005c6](03) 83c408 add esp,+08
[000005c9](01) f4 hlt
[000005ca](01) 5d pop ebp
[000005cb](01) c3 ret
Output_Debug_Trace() [00010bd3] size(80) capacity(65536)
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
[000005bc](05) 6884050000 push 00000584
[000005c1](05) e88efdffff call 00000354 ----CALL [00000354]
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
> On 01/12/2020 01:40, Kaz Kylheku wrote:
>> Stepping through a program to decide its halting is completely
>> wrongheaded.
>
> It's not /completely/ wrong-headed. ...
>
>> 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.
> [...]
>> 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.
>
> ... The set of P and I of a given size [measured in some
> reasonable way, such as the number of bytes needed to define P and
> to list I] is finite, and "easily" enumerated. For a given P,I,
> define N_P,I to be 0 if P doesn't halt on I, and otherwise to be
> the number of steps taken by P before halting. Let S be the max
> over that set of P,I of N_P,I. Then an emulation of P on I for
> S steps shows either that P on I halts or that it will never
> halt. But, you object, we need to know whether P on I halts
> before we can calculate S. True, I riposte, but we don't need
> to know S exactly, any bound /whatsoever/ on S will suffice.
>
> Now the argument can go either of two ways. (a) Since
> the HP is "unsolvable", this shows that S is uncomputable, even
> though it's just any sufficiently large, and otherwise perfectly
> unexceptional, integer. Or (b), by an argument very similar to
> Busy Beaver theory, we can show directly that S is uncomputable
> and deduce that the HP is "unsolvable". [This proof is independent
> of the "Linz H_hat" argument that PO so dislikes, and also of the
> two-liner that Linz prefers, as given also by Mr Flibble.]
>
> IOW, emulation is doomed to failure, but not in such an
> obvious way that it's wrong-headed, which I would reserve for
> approaches to problems that anyone should be able to see in
> advance are not going to work.
>
> [I put "unsolvable" in quotes as shorthand for "there is
> no Turing machine or near equivalent that solves the general
> problem", as any fule kno.*]
>
> ____
> * https://en.wikipedia.org/wiki/Nigel_Molesworth
>
Here is another choice from fully operational code.
The only way that you can maintain your false believe that I am
incorrect is to make sure to not pay attention to the following complete
execution trace of fully operational code.
void H_Hat(u32 P)
{
u32 Aborted = DebugTrace(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}
int main()
{
DebugTrace((u32)H_Hat, (u32)H_Hat);
HALT;
}
_H_Hat()
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354
[00000595](03) 83c408 add esp,+08
[00000598](03) 8945fc mov [ebp-04],eax
[0000059b](04) 837dfc00 cmp dword [ebp-04],+00
[0000059f](02) 7403 jz 000005a4
[000005a1](01) f4 hlt
[000005a2](02) eb02 jmp 000005a6
[000005a4](02) ebfe jmp 000005a4
[000005a6](02) 8be5 mov esp,ebp
[000005a8](01) 5d pop ebp
[000005a9](01) c3 ret
_main()
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
[000005bc](05) 6884050000 push 00000584
[000005c1](05) e88efdffff call 00000354
[000005c6](03) 83c408 add esp,+08
[000005c9](01) f4 hlt
[000005ca](01) 5d pop ebp
[000005cb](01) c3 ret
Output_Debug_Trace() [00010bd3] size(80) capacity(65536)
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
[000005bc](05) 6884050000 push 00000584
[000005c1](05) e88efdffff call 00000354 ----CALL [00000354]
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
Kaz Kylheku
Dec 1, 2020, 1:15:12 PM12/1/20
to
On 2020-12-01, olcott <No...@NoWhere.com> wrote:
> void H_Hat(u32 P)
This program has issues.
> {
> u32 Aborted = DebugTrace(P, P);
one of two ways. If it returns nonzero, it means that the termination
was forced by the simulator, otherwise zero means that P(P)
spontaneously halted.
The nonzero case can be a false positive, arising from
DebugTrace simply not having run P(P) long enough for it to
terminate.
The essence of the halting problem is that the decider runs into
situations in which it itself does not terminate and those are
the big problem.
You essentially are begging the question: you're *assuming* that your
halting decider will always terminate, and therefore arguing that the
proofs are wrong because your decider terminates.
> if (Aborted)
> HALT
> else
> HERE: goto HERE;
> }
>
>
> int main()
> {
> DebugTrace((u32)H_Hat, (u32)H_Hat);
> HALT;
Well, what is the meaning of that? This program is supposed to report
whether something halted or not; where is it doing that?
Why are we ignoring the return value of DebugTrace here?
It seems that we can substitute any arguments whatsoever in the
DebugTrace call and the program reports the same termination status; how
is that a decider?
The above are all serious flaws in your work.
olcott
Dec 1, 2020, 1:38:12 PM12/1/20
to
so that it correctly decides these non halting cases:
int main()
{
HERE: goto HERE;
OutputString("Hello World!");
HALT;
}
Output_Debug_Trace() [00010be8] size(12) capacity(65536)
[000005c4](01) 55 push ebp
[000005c5](02) 8bec mov ebp,esp
[000005c7](02) ebfe jmp 000005c7 ---- JMP [000005c7]
[000005c7](02) ebfe jmp 000005c7 ---- JMP [000005c7]
The PRIOR Instruction Specifies an Infinite Loop: Simulation Stopped:
HERE: goto HERE;
H_Hat((u32)H_Hat);
HALT;
}
Output_Debug_Trace() [00010bc4] size(76) capacity(65536)
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
[000005bc](05) e8c3ffffff call 00000584 ----CALL [00000584]
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
olcott
Dec 1, 2020, 4:50:12 PM12/1/20
to
On 12/1/2020 3:30 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <No...@NoWhere.com> wrote:
>> On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <No...@NoWhere.com> wrote:
>> 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;
>> }
>
> This is just an element of the "educational" version of the proof.
>> else
>> HERE: goto HERE;
>> }
>
>
> It's obvious to everyone that strawman interpretations of this have
> weaknesses; if it were compiled on an actual machine, there will be
> instruction sequences that a VM could look for to detect the trivial
> loop and such.
>
> You must make the strongest possible interpretation of this.
> For instance, H_Hat can invoke Halts using a tamper-proof virtual
> machine of its own.
I only have to find one case of the conventional halting problem proof
"do the opposite of whatever the halt decider decides" to refute all of
these proofs.
Malcolm understands this:
On 12/1/2020 6:00 AM, Malcolm McLean wrote:
> No, that's reasonable. If he can produc a pair of Turing machines,
> one of which is a "partial halt decider", the other which calls that
> decider and inverts the result, and somehow gets consistent results
> on the call to the decider and the direct run, then he's refuted
> the proof.
>
> The halt decider doesn't have to handle every case, and it
> doesn't have to
> work for the infinite possible variations on the H_Hat theme. You just
> need one counter-example and the proof falls.
>
PROOFS.
> Or: I can write H_Hat in a custom programming language, which compiles
> to byte code. And then H_Hat looks like this:
>
>
> uint8_t H_Hat_Bytecode = { 0xF3, 0xD9, ... reams of hex };
>
> void H_Hat(P)
> {
> H_Hat_Bytecode_Execute(H_Hat_Bytecode, P);
> }
>
> now the "HERE: goto HERE" is hidden in bytecode. A completely different
> strategy is needed to discover it, since it is not apparent in any
> native instruction sequence.
0 new messages