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 | 13 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 2 of 2 — ← Prev page 1 [2]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-01 21:30 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <20201201132248.326@kylheku.com> |
| In reply to | #2012 |
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> On 12/1/2020 2:41 AM, Kaz Kylheku 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.
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.
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.
--
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-12-01 16:34 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <ULGdnUkRI-FpWVvCnZ2dnUU7-X3NnZ2d@giganews.com> |
| In reply to | #2020 |
On 12/1/2020 4:22 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> On 12/1/2020 3:30 PM, Kaz Kylheku wrote:
>>> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>>>> On 12/1/2020 2:41 AM, Kaz Kylheku 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.
>>>
>>> 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.
>
> You're only refuting a strawman interpretation of proof sketches.
>
> Those proof skeches are for educational purposes; they are not the
> intellectual work that underlies our understanding of computability.
>
>>> 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);
>>> }
>
> The above is still the "conventional template"; I just compiled
> it a particular way.
>
> That is to say, I can have a program which /automatically/ converts this:
>
> void H_Hat(P)
> {
> if (Halts(P, P))
> {
> for (;;);
> }
> else
> {
> HALT;
> }
> }
>
> into custom byte code:
>
> void H_Hat(P)
> {
> static uint8_t bytecode = { 0xF3, 0xD9, ... };
> bytecode_execute(bytecode, P);
> }
>
> I'm still conforming to the template.
You don't seem to be able to understand this:
Any example where the template is decidable is all that is needed to
prove that the template itself does not prove undecidability.
--
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 23:10 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <20201201150342.507@kylheku.com> |
| In reply to | #2024 |
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote: > You don't seem to be able to understand this: > Any example where the template is decidable is all that is needed to > prove that the template itself does not prove undecidability. Yes; the template itself doesn't do any such thing. It's only an illustration of the method, which you are supposed to apply in the best possible way in order to break a given proposed halting decider. The main idea is that for any function offered as a halting decider, we can use the method to find a breaking example. Similarly to how "the map is not the territory", the template is not the method. -- 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-12-01 12:12 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <lvSdnVrkbdISGlvCnZ2dnUU7-fvNnZ2d@giganews.com> |
| In reply to | #2011 |
On 12/1/2020 11:32 AM, Kaz Kylheku wrote:
> On 2020-12-01, Malcolm McLean <malcolm.arthur.mclean@gmail.com> 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.
>
> Olcott is working against strawman versions of the proof which use
> hand-waving arguments and pseudo-code in order to be easy to follow.
>
Like I said I am stopping after correcting your first mistake.
Actual debug trace of Halts() deciding halting on H_Hat()
I spent about 3000 hours creating the x86utm operating system that
executes x86 based virtual machines using a very excellent x86 emulator.
It executes the COFF object file output of the Microsoft C compiler
using x86 emulation.
x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
It is common knowledge that all x86 based programs are computationally
equivalent to UTMs for every computation that does not require more
memory than they have.
The following is fully executable code and its complete execution trace
is provided below.
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:
--
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 18:35 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <20201201101804.411@kylheku.com> |
| In reply to | #2016 |
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> The following is fully executable code and its complete execution trace
> is provided below.
>
> 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;
> }
[ snip ]
> [00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
OK, so here, we are inside H_Hat and invoked DebugTrace(P, P), right?
This DebugTrace machine has detected a trivial recursion, right? And so,
in that case, it terminates with the above diagnostic message and
returns a nonzero value.
So now, we have a non-zero Aborted value from DebugTrace(P, P).
Thus, the if statement calls HALT.
Well, what does that mean? Presumably, the outer DebugTrace in main
will now terminate. (With a zero, since it was due to a HALT and not
a simulator-induced abort.)
Thus, now control pops out of the DebugTrace call in main, and
falls through to main's HALT; and that's that.
I don't understand what is the decision verdict. The program has
stopped, surely enough, but what has the program decided?
- Has it decided that H_Hat(H_Hat) halts?
- Or has it decided that it does not halt?
Since H_Hat(H_Hat) hit infinite recursion, it should somehow be reporting
"does not halt", right?
Consider the following two programs, based on the above program. All I
have done is changed H_Hat. Do these two programs report different
decisions from each other? How do they do that?
void H_Hat(u32 P)
{
HALT;
}
int main()
{
DebugTrace((u32)H_Hat, (u32)H_Hat);
HALT;
}
and:
void H_Hat(u32 P)
{
HERE: goto HERE;
}
int main()
{
DebugTrace((u32)H_Hat, (u32)H_Hat);
HALT;
}
(Related question: will the DebugTrace halt in this second program?
Does DebugTrace detect a trivial "HERE: goto here;" loop, like it
detects recursion?)
--
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-12-01 12:54 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <4eednaTjve7hDFvCnZ2dnUU7-IGdnZ2d@giganews.com> |
| In reply to | #2017 |
On 12/1/2020 12:35 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> The following is fully executable code and its complete execution trace
>> is provided below.
>>
>> 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;
>> }
>
> [ snip ]
>
>> [00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
>
>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>
> OK, so here, we are inside H_Hat and invoked DebugTrace(P, P), right?
> This DebugTrace machine has detected a trivial recursion, right? And so,
> in that case, it terminates with the above diagnostic message and
> returns a nonzero value.
Any time the same function is called from the same machine address
without any conditional branch instructions in-between we have infinite
recursion.
> So now, we have a non-zero Aborted value from DebugTrace(P, P).
> Thus, the if statement calls HALT.
No, it is the call to DebugTrace() is aborted before ever returning any
value to H_Hat.
> Well, what does that mean? Presumably, the outer DebugTrace in main
> will now terminate. (With a zero, since it was due to a HALT and not
> a simulator-induced abort.)
>
No the operating system is the halt decider as exaplained in my other
reply.
> Thus, now control pops out of the DebugTrace call in main, and
> falls through to main's HALT; and that's that.
No main() is aborted by the operating system before then.
> I don't understand what is the decision verdict. The program has
> stopped, surely enough, but what has the program decided?
>
>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
The entire simulation of all user code is stopped as soon as some of the
user code was found to be infinitely recursive.
The operating system version of Halts is invoked against main() as
required by these two cases:
int main()
{
HERE: goto HERE;
OutputString("Hello World!");
HALT;
}
int main()
{
H_Hat((u32)H_Hat);
HALT;
}
> - Has it decided that H_Hat(H_Hat) halts?
>
> - Or has it decided that it does not halt?
>
> Since H_Hat(H_Hat) hit infinite recursion, it should somehow be reporting
> "does not halt", right?
>
> Consider the following two programs, based on the above program. All I
> have done is changed H_Hat. Do these two programs report different
> decisions from each other? How do they do that?
>
> void H_Hat(u32 P)
> {
> HALT;
> }
>
> int main()
> {
> DebugTrace((u32)H_Hat, (u32)H_Hat);
> HALT;
> }
>
> and:
>
> void H_Hat(u32 P)
> {
> HERE: goto HERE;
> }
>
> int main()
> {
> DebugTrace((u32)H_Hat, (u32)H_Hat);
> HALT;
> }
>
> (Related question: will the DebugTrace halt in this second program?
> Does DebugTrace detect a trivial "HERE: goto here;" loop, like it
> detects recursion?)
>
>
--
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-12-01 10:08 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <AvWdna1EjI3491vCnZ2dnUU7-WHNnZ2d@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):
>
> 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".
>
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:
--
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:23 +0000 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <20201130165528.727@kylheku.com> |
| In reply to | #1997 |
On 2020-11-30, olcott <NoOne@NoWhere.com> 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.
Firstly, you don't yet understand what it means to decide halting.
You cannot "decide" whether a program P halts on input I simply
by running P(I). This is because P(I) might not terminate.
Whenever P(I) does not terminate, the halting is not decided.
To decide halting means, /in a finite number of steps/ to decide whether
any P halts on any I.
You're missing he possibility that H_Hat above can include arbitrary
decoy code. For instance, like this, or in any number of other ways:
void H_Hat(u32 P)
{
Decoy_Calculation(P); // may or may not terminate
u32 Input_Halts = Halts(P, P);
if (!Input_Halts)
HALT
else
HERE: goto HERE;
}
If you execute this with a stepwise simulation, you will end up inside
the decoy. So then, you must decide whether that decoy terminates.
Well, assuming you even know you're inside a decoy. A decoy can look
like any innocent program. (Deciding whether the decoy part terminates:
note how that is an embedded instance of the halting problem!)
Now these programs can be generated such that sometimes the decoy does
not terminate, and sometimes it does. Whenever it doesn't terminate, the
runaway recursion part that Halt() is naively looking for is never
reached.
>> 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?
If someone were to refute the conventional proofs, it would count for
something. Namely, it would mean that computability reverts to being an
open problem. I.e. that halting may or may not be decidable: we have no
proof one way or the other, in spite of for decades having thought we
had some.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-11-30 19:30 -0600 |
| Subject | Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) |
| Message-ID | <pcmdnZn7zqICAVjCnZ2dnUU7-aOdnZ2d@giganews.com> |
| In reply to | #2002 |
On 11/30/2020 7:23 PM, Kaz Kylheku wrote:
> On 2020-11-30, olcott <NoOne@NoWhere.com> 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.
>
> Firstly, you don't yet understand what it means to decide halting.
>
This example proves that you are wrong !
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;
}
I am stopping at your first mistake because you are not bothering to pay
any attention what-so-ever to what I just said.
--
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 12:46 -0600 |
| Message-ID | <PsOdneY9RaQb1FzCnZ2dnUU7-cXNnZ2d@giganews.com> |
| In reply to | #1932 |
On 11/27/2020 12:03 PM, Richard Damon wrote: > On 11/27/20 12:10 PM, 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. >> > > Yes, infinite recursion with NO conditional is an infinite loop. When > those instruction are executed inside a virtual machine that contains > code that might decide to terminate that loop, then HAS a conditional in > the ACTUAL execution trace of the processor. It looks like I have to tell you the same thing an average of twenty-five times before you ever hear it for the very first time: HERE IT IS AGAIN: Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior. Halts decides that H_Hat would never halt unless Halts stopped simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false. -- 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:40 -0600 |
| Message-ID | <6vSdnaJBrcGv71zCnZ2dnUU7-SnNnZ2d@giganews.com> |
| In reply to | #1939 |
On 11/27/2020 3:28 PM, Richard Damon wrote: > On 11/27/20 1:46 PM, olcott wrote: >> On 11/27/2020 12:03 PM, Richard Damon wrote: > >>> >>> Yes, infinite recursion with NO conditional is an infinite loop. When >>> those instruction are executed inside a virtual machine that contains >>> code that might decide to terminate that loop, then HAS a conditional in >>> the ACTUAL execution trace of the processor. >> >> It looks like I have to tell you the same thing an average of >> twenty-five times before you ever hear it for the very first time: >> >> HERE IT IS AGAIN: >> Any input (TMD / DATA) that would never halt unless its simulator >> stopped simulating it expresses behavior that is not halting behavior. >> >> Halts decides that H_Hat would never halt unless Halts stopped >> simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false. >> > > And you STILL refuse to look at the actual behavior. > > Yes, any input (Turing Machine Description / Data) that would never halt > unless its simulator stopped simulating it expresses behavior that is > not halting. > > The problem is that when we actually TEST this, we see that, in the case > of H_Hat it does halt. > ONLY BECAUSE ITS SIMULATOR STOPPED SIMULATING IT, thus leaving no chance what-so-ever for any correct rebuttal. Why you persist in incorrect rebuttals I will never know, it sure seems quite foolish to me. Perhaps you really do have attention deficit disorder and we have to go through this twenty more times before you get it. -- 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:52 -0600 |
| Message-ID | <1JOdnQuvENeH6FzCnZ2dnUU7-cvNnZ2d@giganews.com> |
| In reply to | #1951 |
On 11/27/2020 3:40 PM, olcott wrote: > On 11/27/2020 3:28 PM, Richard Damon wrote: >> On 11/27/20 1:46 PM, olcott wrote: >>> On 11/27/2020 12:03 PM, Richard Damon wrote: >> >>>> >>>> Yes, infinite recursion with NO conditional is an infinite loop. When >>>> those instruction are executed inside a virtual machine that contains >>>> code that might decide to terminate that loop, then HAS a >>>> conditional in >>>> the ACTUAL execution trace of the processor. >>> >>> It looks like I have to tell you the same thing an average of >>> twenty-five times before you ever hear it for the very first time: >>> >>> HERE IT IS AGAIN: >>> Any input (TMD / DATA) that would never halt unless its simulator >>> stopped simulating it expresses behavior that is not halting behavior. >>> >>> Halts decides that H_Hat would never halt unless Halts stopped >>> simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false. >>> >> >> And you STILL refuse to look at the actual behavior. >> >> Yes, any input (Turing Machine Description / Data) that would never halt >> unless its simulator stopped simulating it expresses behavior that is >> not halting. >> >> The problem is that when we actually TEST this, we see that, in the case >> of H_Hat it does halt. >> > ONLY BECAUSE ITS SIMULATOR STOPPED SIMULATING IT, thus leaving no chance > what-so-ever for any correct rebuttal. > > Why you persist in incorrect rebuttals I will never know, it sure seems > quite foolish to me. > > Perhaps you really do have attention deficit disorder and we have to go > through this twenty more times before you get it. We are not asking: Does Halts(H_Hat, H_Hat) halt? We are asking: Does this input (H_Hat, H_Hat) to Halts have to be aborted? -- 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 17:09 -0600 |
| Message-ID | <ocmdndSIT4-6GlzCnZ2dnUU7-L-dnZ2d@giganews.com> |
| In reply to | #1951 |
On 11/27/2020 4:09 PM, Richard Damon wrote: > On 11/27/20 4:40 PM, olcott wrote: >> On 11/27/2020 3:28 PM, Richard Damon wrote: >>> On 11/27/20 1:46 PM, olcott wrote: >>>> On 11/27/2020 12:03 PM, Richard Damon wrote: >>> >>>>> >>>>> Yes, infinite recursion with NO conditional is an infinite loop. When >>>>> those instruction are executed inside a virtual machine that contains >>>>> code that might decide to terminate that loop, then HAS a >>>>> conditional in >>>>> the ACTUAL execution trace of the processor. >>>> >>>> It looks like I have to tell you the same thing an average of >>>> twenty-five times before you ever hear it for the very first time: >>>> >>>> HERE IT IS AGAIN: >>>> Any input (TMD / DATA) that would never halt unless its simulator >>>> stopped simulating it expresses behavior that is not halting behavior. >>>> >>>> Halts decides that H_Hat would never halt unless Halts stopped >>>> simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false. >>>> >>> >>> And you STILL refuse to look at the actual behavior. >>> >>> Yes, any input (Turing Machine Description / Data) that would never halt >>> unless its simulator stopped simulating it expresses behavior that is >>> not halting. >>> >>> The problem is that when we actually TEST this, we see that, in the case >>> of H_Hat it does halt. >>> >> ONLY BECAUSE ITS SIMULATOR STOPPED SIMULATING IT, thus leaving no chance >> what-so-ever for any correct rebuttal. >> >> Why you persist in incorrect rebuttals I will never know, it sure seems >> quite foolish to me. >> >> Perhaps you really do have attention deficit disorder and we have to go >> through this twenty more times before you get it. >> >> > Any input (TMD / DATA) that would never halt unless its simulator stopped simulating it expresses behavior that is not halting behavior. Thus proving beyond all possible doubt that Halts necessarily made a correct not halting decision when it decided to stop simulating H_Hat. We are not asking: Does Halts(H_Hat, H_Hat) halt? We are asking: Does this input (H_Hat, H_Hat) to Halts have to be aborted? -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | comp.software-eng
csiph-web