Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2051 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2020-12-03 12:18 -0600 |
| Last post | 2020-12-03 17:29 -0700 |
| Articles | 18 on this page of 38 — 4 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: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 12:18 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 13:55 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 17:26 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Jeff Barnett <jbb@notatt.com> - 2020-12-03 17:21 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 18:31 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Jeff Barnett <jbb@notatt.com> - 2020-12-03 18:13 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 19:20 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 00:26 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 18:40 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 01:17 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 19:39 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 19:31 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 13:49 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 21:19 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 15:43 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 20:38 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 03:55 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 22:13 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-04 20:47 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 22:55 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-04 23:26 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 09:54 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 16:36 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:04 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:16 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:46 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 11:50 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 10:35 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 23:36 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 17:59 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-06 02:00 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 20:17 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-06 06:06 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 10:42 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:24 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 19:58 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 19:37 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] Jeff Barnett <jbb@notatt.com> - 2020-12-03 17:29 -0700
Page 2 of 2 — ← Prev page 1 [2]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2020-12-04 23:26 -0800 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqfcnf$16a0$2@gioia.aioe.org> |
| In reply to | #2089 |
On 12/4/2020 8:55 PM, olcott wrote:
> On 12/4/2020 10:47 PM, Chris M. Thomasson wrote:
>> On 12/4/2020 8:13 PM, olcott wrote:
>>> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>>>> ["Followup-To:" header set to comp.theory.]
>>>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>>>
>>>>>>>>> The same pattern of doing the opposite of whatever the halt
>>>>>>>>> decider
>>>>>>>>> decides is the same pattern of the liar paradox (if it is true
>>>>>>>>> that
>>>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness
>>>>>>>>> theorem if
>>>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>>>> provable is indeed unprovable then this contradicts its
>>>>>>>>> assertion making
>>>>>>>>> it untrue.
>>>>>>>>>
>>>>>>>>
>>>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>>>
>>>>>>>> The statement: "This Statement is False"
>>>>>>>>
>>>>>>>> Can not be assigned a truth value, as it is logically
>>>>>>>> contradictory,
>>>>>>>
>>>>>>> In this exact same way Halts cannot return a correct halting
>>>>>>> decision to
>>>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>>>
>>>>>> - The Liar Paradox *does not* have a valid interpretation of its
>>>>>> truth
>>>>>> value.
>>>>>>
>>>>>> That's a statement about reality.
>>>>>>
>>>>>> - Halts *cannot* return a correct value, sure
>>>>>>
>>>>>> That's a statement about a fantasy: the wish to have it return
>>>>>> a correct
>>>>>> value, which doesn't come true.
>>>>>>
>>>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>>>
>>>>>> There is no paradox.
>>>>>>
>>>>>
>>>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>>>
>>>>>
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>> u32 Input_Halts = H(P, P);
>>>>> if (Input_Halts)
>>>>> HERE: goto HERE;
>>>>> else
>>>>> HALT
>>>>> }
>>>>>
>>>>>
>>>>> int main()
>>>>> {
>>>>> H((u32)H_Hat, (u32)H_Hat);
>>>>> HALT;
>>>>> }
>>>>>
>>>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation
>>>>> Stopped:
>>>>> Number of Instructions Executed(2777)
>>>>
>>>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>>>> value to indicate this. The whole show simply stopped.
>>>>
>>>> Therefore H did not decide anything.
>>>>
>>>> H must terminate by returning normally with a return value that
>>>> is true or false.
>>>>
>>>> You need a program like this:
>>>>
>>>> int main()
>>>> {
>>>> if (H((u32)H_Hat, (u32)H_Hat)) {
>>>> puts("H_Hat(H_Hat) halts!");
>>>> } else {
>>>> puts("H_Hat(H_Hat) does not hal!");
>>>> }
>>>>
>>>> return 0;
>>>> }
>>>>
>>>> This program must terminate, having printed either one of the two
>>>> messages. If it does so, then it is deemed to have successfully
>>>> decided.
>>>
>>> I am working on this. This is actually just window dressing.
>>> It is a little tricky unwinding recursion cleanly.
>> [...]
>>
>> Has your window been splashed with black paint? Can it tell if an
>> unknown function halts? I say, hell no.
>>
>
> It can correctly tell if the impossible to decide function halts.
> see page 319:
> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>
When does this halt?
<pseudo-code>
______________________________
void test_program()
{
unsigned long n = 666666666;
for (unsigned long x = 0; x < n; ++x)
{
double random_number = roll(); // from 0...1
if (random_number < .5)
{
x = 0;
}
}
}
______________________________
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 09:54 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <GpWdnYvC1LasMFbCnZ2dnUU7-b_NnZ2d@giganews.com> |
| In reply to | #2090 |
On 12/5/2020 1:26 AM, Chris M. Thomasson wrote:
> On 12/4/2020 8:55 PM, olcott wrote:
>> On 12/4/2020 10:47 PM, Chris M. Thomasson wrote:
>>> On 12/4/2020 8:13 PM, olcott wrote:
>>>> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>>>>> ["Followup-To:" header set to comp.theory.]
>>>>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>>>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>>>>
>>>>>>>>>> The same pattern of doing the opposite of whatever the halt
>>>>>>>>>> decider
>>>>>>>>>> decides is the same pattern of the liar paradox (if it is true
>>>>>>>>>> that
>>>>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness
>>>>>>>>>> theorem if
>>>>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>>>>> provable is indeed unprovable then this contradicts its
>>>>>>>>>> assertion making
>>>>>>>>>> it untrue.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>>>>
>>>>>>>>> The statement: "This Statement is False"
>>>>>>>>>
>>>>>>>>> Can not be assigned a truth value, as it is logically
>>>>>>>>> contradictory,
>>>>>>>>
>>>>>>>> In this exact same way Halts cannot return a correct halting
>>>>>>>> decision to
>>>>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>>>>
>>>>>>> - The Liar Paradox *does not* have a valid interpretation of its
>>>>>>> truth
>>>>>>> value.
>>>>>>>
>>>>>>> That's a statement about reality.
>>>>>>>
>>>>>>> - Halts *cannot* return a correct value, sure
>>>>>>>
>>>>>>> That's a statement about a fantasy: the wish to have it
>>>>>>> return a correct
>>>>>>> value, which doesn't come true.
>>>>>>>
>>>>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>>>>
>>>>>>> There is no paradox.
>>>>>>>
>>>>>>
>>>>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>>>>
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>> u32 Input_Halts = H(P, P);
>>>>>> if (Input_Halts)
>>>>>> HERE: goto HERE;
>>>>>> else
>>>>>> HALT
>>>>>> }
>>>>>>
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>> H((u32)H_Hat, (u32)H_Hat);
>>>>>> HALT;
>>>>>> }
>>>>>>
>>>>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation
>>>>>> Stopped:
>>>>>> Number of Instructions Executed(2777)
>>>>>
>>>>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>>>>> value to indicate this. The whole show simply stopped.
>>>>>
>>>>> Therefore H did not decide anything.
>>>>>
>>>>> H must terminate by returning normally with a return value that
>>>>> is true or false.
>>>>>
>>>>> You need a program like this:
>>>>>
>>>>> int main()
>>>>> {
>>>>> if (H((u32)H_Hat, (u32)H_Hat)) {
>>>>> puts("H_Hat(H_Hat) halts!");
>>>>> } else {
>>>>> puts("H_Hat(H_Hat) does not hal!");
>>>>> }
>>>>>
>>>>> return 0;
>>>>> }
>>>>>
>>>>> This program must terminate, having printed either one of the two
>>>>> messages. If it does so, then it is deemed to have successfully
>>>>> decided.
>>>>
>>>> I am working on this. This is actually just window dressing.
>>>> It is a little tricky unwinding recursion cleanly.
>>> [...]
>>>
>>> Has your window been splashed with black paint? Can it tell if an
>>> unknown function halts? I say, hell no.
>>>
>>
>> It can correctly tell if the impossible to decide function halts.
>> see page 319:
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>
>
I have refuted the halting problem proofs by correctly deciding the
"provably" impossible to decide input.
Deciding halting on your example is probably not provably impossible.
Once everyone agrees that I have correctly decided the provable
impossible to decide input, then I will begin to look at other examples
such as yours.
> When does this halt?
>
> <pseudo-code>
> ______________________________
> void test_program()
> {
> unsigned long n = 666666666;
>
> for (unsigned long x = 0; x < n; ++x)
> {
> double random_number = roll(); // from 0...1
>
> if (random_number < .5)
> {
> x = 0;
> }
> }
> }
> ______________________________
>
--
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-05 16:36 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201205083241.121@kylheku.com> |
| In reply to | #2092 |
On 2020-12-05, olcott <NoOne@NoWhere.com> wrote: > I have refuted the halting problem proofs by correctly deciding the > "provably" impossible to decide input. > > Deciding halting on your example is probably not provably impossible. Sure ... all we need is that definition of H() (the simple H() which isn't trying to solve the general problem at all) yet which decides correctly when embedded in that supposedly decidable case. -- TXR Programming Language: http://nongnu.org/txr
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 11:04 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <aqudnSeWvvYzIFbCnZ2dnUU7-bednZ2d@giganews.com> |
| In reply to | #2096 |
On 12/5/2020 10:36 AM, Kaz Kylheku wrote:
> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>> I have refuted the halting problem proofs by correctly deciding the
>> "provably" impossible to decide input.
>>
>> Deciding halting on your example is probably not provably impossible.
>
> Sure ... all we need is that definition of H() (the simple H() which
> isn't trying to solve the general problem at all) yet which decides
> correctly when embedded in that supposedly decidable case.
>
void H_Hat(u32 P)
{
u32 Input_Halts = H(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
int main()
{
H((u32)H_Hat, (u32)H_Hat);
HALT;
}
_H_Hat()
[000005e0](01) 55 push ebp
[000005e1](02) 8bec mov ebp,esp
[000005e3](01) 51 push ecx
[000005e4](03) 8b4508 mov eax,[ebp+08]
[000005e7](01) 50 push eax
[000005e8](03) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) 51 push ecx
[000005ec](05) e87ffdffff call 00000370
[000005f1](03) 83c408 add esp,+08
[000005f4](03) 8945fc mov [ebp-04],eax
[000005f7](04) 837dfc00 cmp dword [ebp-04],+00
[000005fb](02) 7404 jz 00000601
[000005fd](02) ebfe jmp 000005fd
[000005ff](02) eb01 jmp 00000602
[00000601](01) f4 hlt
[00000602](02) 8be5 mov esp,ebp
[00000604](01) 5d pop ebp
[00000605](01) c3 ret
_main()
[00000610](01) 55 push ebp
[00000611](02) 8bec mov ebp,esp
[00000613](05) 68e0050000 push 000005e0
[00000618](05) 68e0050000 push 000005e0
[0000061d](05) e84efdffff call 00000370
[00000622](03) 83c408 add esp,+08
[00000625](01) f4 hlt
[00000626](01) 5d pop ebp
[00000627](01) c3 ret
Output_Debug_Trace() Trace_List.size(20)
[00000610](01) EMU_Level(0) 55 push ebp
[00000611](02) EMU_Level(0) 8bec mov ebp,esp
[00000613](05) EMU_Level(0) 68e0050000 push 000005e0
[00000618](05) EMU_Level(0) 68e0050000 push 000005e0
[0000061d](05) EMU_Level(0) e84efdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(1) 55 push ebp
[000005e1](02) EMU_Level(1) 8bec mov ebp,esp
[000005e3](01) EMU_Level(1) 51 push ecx
[000005e4](03) EMU_Level(1) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(1) 50 push eax
[000005e8](03) EMU_Level(1) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(1) 51 push ecx
[000005ec](05) EMU_Level(1) e87ffdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(2) 55 push ebp
[000005e1](02) EMU_Level(2) 8bec mov ebp,esp
[000005e3](01) EMU_Level(2) 51 push ecx
[000005e4](03) EMU_Level(2) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(2) 50 push eax
[000005e8](03) EMU_Level(2) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(2) 51 push ecx
[000005ec](05) EMU_Level(2) e87ffdffff call 00000370
----CALL [00000370]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
Number of Instructions Executed(2777)
--
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-05 11:16 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <nt2dnYKXs5PlXVbCnZ2dnUU7-b3NnZ2d@giganews.com> |
| In reply to | #2092 |
On 12/5/2020 10:57 AM, Andy Walker wrote:
> On 05/12/2020 15:54, olcott wrote:
>> I have refuted the halting problem proofs by correctly deciding the
>> "provably" impossible to decide input.
>
> This is wrong-headed. No instance of the HP can be proved to be
> undecidable; such a proof would prove that that instance didn't halt.
Both true and false are the wrong answer for H to return to H_Hat(),
that is what undecidable means, basically a yes/no question having no
correct yes/no answer.
void H_Hat(u32 P)
{
u32 Input_Halts = H(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
int main()
{
H((u32)H_Hat, (u32)H_Hat);
HALT;
}
Since I discovered (in 2016) that the above code (both mine and Linz's)
specifies infinite recursion the right answer is to not return true or
false to H_Hat. No one knew this before my discovery.
Infinitely Recursive input on HP Proofs
https://groups.google.com/g/comp.theory/c/NcFS02hKs1U/m/dhNDYvhFAAAJ
> That's why the actual halting status of "H" or "H_hat" for given input
> is of no interest; the only interest is that "H" gets the wrong answer,
> and so "H" is not a universal halt decider.
Here is the complete execution trace of the above code proving that H
gets the right answer.
_H_Hat()
[000005e0](01) 55 push ebp
[000005e1](02) 8bec mov ebp,esp
[000005e3](01) 51 push ecx
[000005e4](03) 8b4508 mov eax,[ebp+08]
[000005e7](01) 50 push eax
[000005e8](03) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) 51 push ecx
[000005ec](05) e87ffdffff call 00000370
[000005f1](03) 83c408 add esp,+08
[000005f4](03) 8945fc mov [ebp-04],eax
[000005f7](04) 837dfc00 cmp dword [ebp-04],+00
[000005fb](02) 7404 jz 00000601
[000005fd](02) ebfe jmp 000005fd
[000005ff](02) eb01 jmp 00000602
[00000601](01) f4 hlt
[00000602](02) 8be5 mov esp,ebp
[00000604](01) 5d pop ebp
[00000605](01) c3 ret
_main()
[00000610](01) 55 push ebp
[00000611](02) 8bec mov ebp,esp
[00000613](05) 68e0050000 push 000005e0
[00000618](05) 68e0050000 push 000005e0
[0000061d](05) e84efdffff call 00000370
[00000622](03) 83c408 add esp,+08
[00000625](01) f4 hlt
[00000626](01) 5d pop ebp
[00000627](01) c3 ret
Output_Debug_Trace() Trace_List.size(20)
[00000610](01) EMU_Level(0) 55 push ebp
[00000611](02) EMU_Level(0) 8bec mov ebp,esp
[00000613](05) EMU_Level(0) 68e0050000 push 000005e0
[00000618](05) EMU_Level(0) 68e0050000 push 000005e0
[0000061d](05) EMU_Level(0) e84efdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(1) 55 push ebp
[000005e1](02) EMU_Level(1) 8bec mov ebp,esp
[000005e3](01) EMU_Level(1) 51 push ecx
[000005e4](03) EMU_Level(1) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(1) 50 push eax
[000005e8](03) EMU_Level(1) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(1) 51 push ecx
[000005ec](05) EMU_Level(1) e87ffdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(2) 55 push ebp
[000005e1](02) EMU_Level(2) 8bec mov ebp,esp
[000005e3](01) EMU_Level(2) 51 push ecx
[000005e4](03) EMU_Level(2) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(2) 50 push eax
[000005e8](03) EMU_Level(2) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(2) 51 push ecx
[000005ec](05) EMU_Level(2) e87ffdffff call 00000370
----CALL [00000370]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
Number of Instructions Executed(2777)
--
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-05 11:46 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <X5qdnUqj_fj1WlbCnZ2dnUU7-RXNnZ2d@giganews.com> |
| In reply to | #2100 |
On 12/5/2020 11:38 AM, Andy Walker wrote:
> On 05/12/2020 17:16, olcott wrote:
>>>> I have refuted the halting problem proofs by correctly deciding the
>>>> "provably" impossible to decide input.
>>> This is wrong-headed. No instance of the HP can be proved to be
>>> undecidable; such a proof would prove that that instance didn't halt.
>> Both true and false are the wrong answer for H to return to H_Hat(),
>
> They are the wrong answer not because there is no correct
> answer but because "H" fails to find that correct answer. Spot the
> difference.
>
>> that is what undecidable means, basically a yes/no question having no
>> correct yes/no answer.
>
> That's not what "undecidable" means. Especially when, as in
> this case, there /is/ a correct yes/no answer [which you even claim
> to have found]. But "H" gets it wrong.
>
Is: "This sentence is not true" true or false?
The correct return value to H_Hat from H is not to return a value to
H_Hat and decide not halting.
void H_Hat(u32 P)
{
u32 Input_Halts = H(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
int main()
{
H((u32)H_Hat, (u32)H_Hat);
HALT;
}
_H_Hat()
[000005e0](01) 55 push ebp
[000005e1](02) 8bec mov ebp,esp
[000005e3](01) 51 push ecx
[000005e4](03) 8b4508 mov eax,[ebp+08]
[000005e7](01) 50 push eax
[000005e8](03) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) 51 push ecx
[000005ec](05) e87ffdffff call 00000370
[000005f1](03) 83c408 add esp,+08
[000005f4](03) 8945fc mov [ebp-04],eax
[000005f7](04) 837dfc00 cmp dword [ebp-04],+00
[000005fb](02) 7404 jz 00000601
[000005fd](02) ebfe jmp 000005fd
[000005ff](02) eb01 jmp 00000602
[00000601](01) f4 hlt
[00000602](02) 8be5 mov esp,ebp
[00000604](01) 5d pop ebp
[00000605](01) c3 ret
_main()
[00000610](01) 55 push ebp
[00000611](02) 8bec mov ebp,esp
[00000613](05) 68e0050000 push 000005e0
[00000618](05) 68e0050000 push 000005e0
[0000061d](05) e84efdffff call 00000370
[00000622](03) 83c408 add esp,+08
[00000625](01) f4 hlt
[00000626](01) 5d pop ebp
[00000627](01) c3 ret
Output_Debug_Trace() Trace_List.size(20)
[00000610](01) EMU_Level(0) 55 push ebp
[00000611](02) EMU_Level(0) 8bec mov ebp,esp
[00000613](05) EMU_Level(0) 68e0050000 push 000005e0
[00000618](05) EMU_Level(0) 68e0050000 push 000005e0
[0000061d](05) EMU_Level(0) e84efdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(1) 55 push ebp
[000005e1](02) EMU_Level(1) 8bec mov ebp,esp
[000005e3](01) EMU_Level(1) 51 push ecx
[000005e4](03) EMU_Level(1) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(1) 50 push eax
[000005e8](03) EMU_Level(1) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(1) 51 push ecx
[000005ec](05) EMU_Level(1) e87ffdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(2) 55 push ebp
[000005e1](02) EMU_Level(2) 8bec mov ebp,esp
[000005e3](01) EMU_Level(2) 51 push ecx
[000005e4](03) EMU_Level(2) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(2) 50 push eax
[000005e8](03) EMU_Level(2) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(2) 51 push ecx
[000005ec](05) EMU_Level(2) e87ffdffff call 00000370
----CALL [00000370]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
Number of Instructions Executed(2777)
--
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-05 11:50 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201205033846.582@kylheku.com> |
| In reply to | #2087 |
["Followup-To:" header set to comp.theory.]
On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.theory.]
>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>
>>>>>>> The same pattern of doing the opposite of whatever the halt decider
>>>>>>> decides is the same pattern of the liar paradox (if it is true that
>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>> provable is indeed unprovable then this contradicts its assertion making
>>>>>>> it untrue.
>>>>>>>
>>>>>>
>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>
>>>>>> The statement: "This Statement is False"
>>>>>>
>>>>>> Can not be assigned a truth value, as it is logically contradictory,
>>>>>
>>>>> In this exact same way Halts cannot return a correct halting decision to
>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>
>>>> - The Liar Paradox *does not* have a valid interpretation of its truth
>>>> value.
>>>>
>>>> That's a statement about reality.
>>>>
>>>> - Halts *cannot* return a correct value, sure
>>>>
>>>> That's a statement about a fantasy: the wish to have it return a correct
>>>> value, which doesn't come true.
>>>>
>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>
>>>> There is no paradox.
>>>>
>>>
>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>
>>>
>>> void H_Hat(u32 P)
>>> {
>>> u32 Input_Halts = H(P, P);
>>> if (Input_Halts)
>>> HERE: goto HERE;
>>> else
>>> HALT
>>> }
>>>
>>>
>>> int main()
>>> {
>>> H((u32)H_Hat, (u32)H_Hat);
>>> HALT;
>>> }
>>>
>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>>> Number of Instructions Executed(2777)
>>
>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>> value to indicate this. The whole show simply stopped.
>>
>> Therefore H did not decide anything.
>>
>> H must terminate by returning normally with a return value that
>> is true or false.
>>
>> You need a program like this:
>>
>> int main()
>> {
>> if (H((u32)H_Hat, (u32)H_Hat)) {
>> puts("H_Hat(H_Hat) halts!");
>> } else {
>> puts("H_Hat(H_Hat) does not hal!");
>> }
>>
>> return 0;
>> }
>>
>> This program must terminate, having printed either one of the two
>> messages. If it does so, then it is deemed to have successfully decided.
>
> I am working on this. This is actually just window dressing.
I am not able to agree that demonstrating that H has returned and which
value it has returned is just window dressing.
> It is a little tricky unwinding recursion cleanly.
Suppose that your execution machine were to generate a "recursion detected"
exception that is visible to H. The sysem doesn't jus stop, but H can
catch this exception, unwind to the topmost invocation and then return a
true or false value.
It's just not obvious how that helps.
> My execution trace already proved that Halts(H_Hat, H_Hat) is decidable.
The execution trace proves that it's possible to have an external
"bird's eye" view which can see that H trying to decide H_Hat(H_Hat)
hits runaway recursion. That external view can issue a diagnostic
to that effect (and then, optionally, stop everything).
The missing step is getting H itself to return a correct value.
It's obvious that we can run all the halt-deciding calculation in a
monitored machine which will stop it under various conditions like "loop
detected" or "too many instructions executed" or whatever we like.
But in all such cases, the halt-deciding calculation has failed to
decide. The function H has not terminated with a true or false return
value, as required.
--
TXR Programming Language: http://nongnu.org/txr
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 10:35 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <2sWdnQvV66NEK1bCnZ2dnUU7-YvNnZ2d@giganews.com> |
| In reply to | #2091 |
On 12/5/2020 5:50 AM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>>> ["Followup-To:" header set to comp.theory.]
>>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>>
>>>>>>>> The same pattern of doing the opposite of whatever the halt decider
>>>>>>>> decides is the same pattern of the liar paradox (if it is true that
>>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>>> provable is indeed unprovable then this contradicts its assertion making
>>>>>>>> it untrue.
>>>>>>>>
>>>>>>>
>>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>>
>>>>>>> The statement: "This Statement is False"
>>>>>>>
>>>>>>> Can not be assigned a truth value, as it is logically contradictory,
>>>>>>
>>>>>> In this exact same way Halts cannot return a correct halting decision to
>>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>>
>>>>> - The Liar Paradox *does not* have a valid interpretation of its truth
>>>>> value.
>>>>>
>>>>> That's a statement about reality.
>>>>>
>>>>> - Halts *cannot* return a correct value, sure
>>>>>
>>>>> That's a statement about a fantasy: the wish to have it return a correct
>>>>> value, which doesn't come true.
>>>>>
>>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>>
>>>>> There is no paradox.
>>>>>
>>>>
>>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>>
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Input_Halts = H(P, P);
>>>> if (Input_Halts)
>>>> HERE: goto HERE;
>>>> else
>>>> HALT
>>>> }
>>>>
>>>>
>>>> int main()
>>>> {
>>>> H((u32)H_Hat, (u32)H_Hat);
>>>> HALT;
>>>> }
>>>>
>>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>>>> Number of Instructions Executed(2777)
>>>
>>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>>> value to indicate this. The whole show simply stopped.
>>>
>>> Therefore H did not decide anything.
>>>
>>> H must terminate by returning normally with a return value that
>>> is true or false.
>>>
>>> You need a program like this:
>>>
>>> int main()
>>> {
>>> if (H((u32)H_Hat, (u32)H_Hat)) {
>>> puts("H_Hat(H_Hat) halts!");
>>> } else {
>>> puts("H_Hat(H_Hat) does not hal!");
>>> }
>>>
>>> return 0;
>>> }
>>>
>>> This program must terminate, having printed either one of the two
>>> messages. If it does so, then it is deemed to have successfully decided.
>>
>> I am working on this. This is actually just window dressing.
>
> I am not able to agree that demonstrating that H has returned and which
> value it has returned is just window dressing.
Whether the operating system reports this or the function reports this
is not a material detail.
>> It is a little tricky unwinding recursion cleanly.
>
> Suppose that your execution machine were to generate a "recursion detected"
> exception that is visible to H. The sysem doesn't jus stop, but H can
> catch this exception, unwind to the topmost invocation and then return a
> true or false value.
Yes and to do that I have to write exception handling from scratch.
I think that I have this almost completed. It captures the machine state
prior to simulation. I changed the EIP to point to clean up the stack
and return 0. It keeps track of the Halt Decider decision. All that I
have to do now is restore this original machine state such that the Halt
decider cleans up the stack and returns 0.
> It's just not obvious how that helps.
>
>> My execution trace already proved that Halts(H_Hat, H_Hat) is decidable.
>
> The execution trace proves that it's possible to have an external
> "bird's eye" view which can see that H trying to decide H_Hat(H_Hat)
> hits runaway recursion. That external view can issue a diagnostic
> to that effect (and then, optionally, stop everything).
That is what it currently does.
>
> The missing step is getting H itself to return a correct value.
>
Yes, I forget how long I have been working on that, maybe a week.
> It's obvious that we can run all the halt-deciding calculation in a
> monitored machine which will stop it under various conditions like "loop
> detected" or "too many instructions executed" or whatever we like.
> But in all such cases, the halt-deciding calculation has failed to
> decide. The function H has not terminated with a true or false return
> value, as required.
>
The global halt decider has correctly decided the "impossible to decide"
input. Soon the local halt decider will be able to do the same thing. As
soon as it does this I will rename DebugTrace() to Halts().
--
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-05 23:36 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201205152008.789@kylheku.com> |
| In reply to | #2095 |
On 2020-12-05, olcott <NoOne@NoWhere.com> wrote: > On 12/5/2020 5:50 AM, Kaz Kylheku wrote: >> >> Suppose that your execution machine were to generate a "recursion detected" >> exception that is visible to H. The sysem doesn't jus stop, but H can >> catch this exception, unwind to the topmost invocation and then return a >> true or false value. > > Yes and to do that I have to write exception handling from scratch. > I think that I have this almost completed. It captures the machine state > prior to simulation. I changed the EIP to point to clean up the stack > and return 0. It keeps track of the Halt Decider decision. All that I > have to do now is restore this original machine state such that the Halt > decider cleans up the stack and returns 0. However, note that Halts cannot throw (or pass through) any exception to its caller. If Halts, at any level of recursion, terminates other than by returning true or false, such as by leaking an exception, it has failed. So, in practicular, it cannot be that P calls Halts, which calls P, which calls Halts again, and the inner Halts throws an exception to the outer Halts. In this situation, the instrument and the test subject are too intertwined for correctness. -- TXR Programming Language: http://nongnu.org/txr
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 17:59 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <6_OdnTDikuVqg1HCnZ2dnUU7-XXNnZ2d@giganews.com> |
| In reply to | #2110 |
On 12/5/2020 5:36 PM, Kaz Kylheku wrote: > On 2020-12-05, olcott <NoOne@NoWhere.com> wrote: >> On 12/5/2020 5:50 AM, Kaz Kylheku wrote: >>> >>> Suppose that your execution machine were to generate a "recursion detected" >>> exception that is visible to H. The sysem doesn't jus stop, but H can >>> catch this exception, unwind to the topmost invocation and then return a >>> true or false value. >> >> Yes and to do that I have to write exception handling from scratch. >> I think that I have this almost completed. It captures the machine state >> prior to simulation. I changed the EIP to point to clean up the stack >> and return 0. It keeps track of the Halt Decider decision. All that I >> have to do now is restore this original machine state such that the Halt >> decider cleans up the stack and returns 0. > > However, note that Halts cannot throw (or pass through) any exception > to its caller. If Halts, at any level of recursion, terminates other > than by returning true or false, such as by leaking an exception, it has > failed. > > So, in practicular, it cannot be that P calls Halts, which calls P, > which calls Halts again, and the inner Halts throws an exception to > the outer Halts. In this case the global halt decider aborts main(). In the case of Halts calls P calls Halts, Halts restores its own initial state and returns the value of not_halting to main(). > In this situation, the instrument and the test subject are too > intertwined for correctness. > When we are talking about Turing machines the halt decider is simply a UTM that has been adapted to become a halt decider that watches every detail of the execution of its inputs. It decides not halting on the Turing machine equivalent of infinite recursion. -- 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-06 02:00 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201205175024.218@kylheku.com> |
| In reply to | #2111 |
["Followup-To:" header set to comp.theory.]
On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
> On 12/5/2020 5:36 PM, Kaz Kylheku wrote:
>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>> On 12/5/2020 5:50 AM, Kaz Kylheku wrote:
>>>>
>>>> Suppose that your execution machine were to generate a "recursion detected"
>>>> exception that is visible to H. The sysem doesn't jus stop, but H can
>>>> catch this exception, unwind to the topmost invocation and then return a
>>>> true or false value.
>>>
>>> Yes and to do that I have to write exception handling from scratch.
>>> I think that I have this almost completed. It captures the machine state
>>> prior to simulation. I changed the EIP to point to clean up the stack
>>> and return 0. It keeps track of the Halt Decider decision. All that I
>>> have to do now is restore this original machine state such that the Halt
>>> decider cleans up the stack and returns 0.
>>
>> However, note that Halts cannot throw (or pass through) any exception
>> to its caller. If Halts, at any level of recursion, terminates other
>> than by returning true or false, such as by leaking an exception, it has
>> failed.
>>
>> So, in practicular, it cannot be that P calls Halts, which calls P,
>> which calls Halts again, and the inner Halts throws an exception to
>> the outer Halts.
>
> In this case the global halt decider aborts main().
Anything that aborts main causes the Halts() function not to have
returned a true or false indication, and therefore not to have decided
anything.
A global abort could mean anything: it could mean that an infinite
loop was detected in Halts() (and is that function's fault) or that
it was detected in H_Hat (non-termination of H_Hat).
If the global machine is to be a halt decider, it needs to take the
required form: take two arguments (program and input) and return a yes
or no value. If that is done, then we can perpetrate the trick against
that global machine.
Of course the global machine is able to decide the halting of that
case; nobody has had taken the opportunity to defeat it by embedding it
in a H_Hat template, and feeding it the resulting configuration.
Of course if a H_Hat is attacking some Halt_Decider_A, it's possible
for some other Halt_Decider_B to detect the halting of that situation.
That is not controvertible in any way.
So that is to say, this situation is uninteresting:
void H_Hat(P)
{
if (Halts_X(P, P))
for(;;);
else
return;
}
main()
{
if (Halts_Y(H_Hat, H_Hat))
puts("H_Hat(H_Hat) halts");
else
puts("H_Hat(H_Hat) doesn't halt");
}
Halts_Y is not under attack. Halts_Y could be the virtual machine that
checks for infinite loops, whereas Halts_X is something else.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 20:17 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <cfGdndJSTbWAolHCnZ2dnUU7-KnNnZ2d@giganews.com> |
| In reply to | #2114 |
On 12/5/2020 8:00 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>> On 12/5/2020 5:36 PM, Kaz Kylheku wrote:
>>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>>> On 12/5/2020 5:50 AM, Kaz Kylheku wrote:
>>>>>
>>>>> Suppose that your execution machine were to generate a "recursion detected"
>>>>> exception that is visible to H. The sysem doesn't jus stop, but H can
>>>>> catch this exception, unwind to the topmost invocation and then return a
>>>>> true or false value.
>>>>
>>>> Yes and to do that I have to write exception handling from scratch.
>>>> I think that I have this almost completed. It captures the machine state
>>>> prior to simulation. I changed the EIP to point to clean up the stack
>>>> and return 0. It keeps track of the Halt Decider decision. All that I
>>>> have to do now is restore this original machine state such that the Halt
>>>> decider cleans up the stack and returns 0.
>>>
>>> However, note that Halts cannot throw (or pass through) any exception
>>> to its caller. If Halts, at any level of recursion, terminates other
>>> than by returning true or false, such as by leaking an exception, it has
>>> failed.
>>>
>>> So, in practicular, it cannot be that P calls Halts, which calls P,
>>> which calls Halts again, and the inner Halts throws an exception to
>>> the outer Halts.
>>
>> In this case the global halt decider aborts main().
>
> Anything that aborts main causes the Halts() function not to have
> returned a true or false indication, and therefore not to have decided
> anything.
That is not true:
int main()
{
HERE: goto HERE;
OutString("Hello World!\n");
HALT
}
_main()
[00000621](01) 55 push ebp
[00000622](02) 8bec mov ebp,esp
[00000624](02) ebfe jmp 00000624
[00000626](05) 6833020000 push 00000233
[0000062b](05) e8d0f9ffff call 00000000
[00000630](03) 83c404 add esp,+04
[00000633](01) f4 hlt
[00000634](01) 5d pop ebp
[00000635](01) c3 ret
Output_Debug_Trace() Trace_List.size(3)
[00000621](01) EMU_Level(0) 55 push ebp
[00000622](02) EMU_Level(0) 8bec mov ebp,esp
[00000624](02) EMU_Level(0) ebfe jmp 00000624
The PRIOR Instruction Specifies an Infinite Loop: Simulation Stopped:
> A global abort could mean anything: it could mean that an infinite
> loop was detected in Halts() (and is that function's fault) or that
> it was detected in H_Hat (non-termination of H_Hat).
>
> If the global machine is to be a halt decider, it needs to take the
> required form: take two arguments (program and input) and return a yes
> or no value. If that is done, then we can perpetrate the trick against
> that global machine.
>
> Of course the global machine is able to decide the halting of that
> case; nobody has had taken the opportunity to defeat it by embedding it
> in a H_Hat template, and feeding it the resulting configuration.
>
> Of course if a H_Hat is attacking some Halt_Decider_A, it's possible
> for some other Halt_Decider_B to detect the halting of that situation.
> That is not controvertible in any way.
>
> So that is to say, this situation is uninteresting:
>
> void H_Hat(P)
> {
> if (Halts_X(P, P))
> for(;;);
> else
> return;
> }
>
> main()
> {
> if (Halts_Y(H_Hat, H_Hat))
> puts("H_Hat(H_Hat) halts");
> else
> puts("H_Hat(H_Hat) doesn't halt");
> }
>
> Halts_Y is not under attack. Halts_Y could be the virtual machine that
> checks for infinite loops, whereas Halts_X is something else.
>
It isn't worth reviewing because it diverges from the primary point,
that H(Ĥ,Ĥ) is decidable as non-halting.
--
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-06 06:06 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201205215049.168@kylheku.com> |
| In reply to | #2115 |
["Followup-To:" header set to comp.theory.] On 2020-12-06, olcott <NoOne@NoWhere.com> wrote: > It isn't worth reviewing because it diverges from the primary point, > that H(Ĥ,Ĥ) is decidable as non-halting. Oh, there is no question that the particular H(Ĥ,Ĥ) is decidable! It not being decidable **by H**, though, is the problem. In your execution traces, H does not return with an answer. A decision machine **other than H** is stopping the show. When it does that, H stops prematurely, and so has not decided anything. The halting theorem does not assert that there are magic test cases that are undecidable by any decider. What it says is that there is no one decider that is universal: for every decider there are cases it can't deal with. It's possible that a test case which stumps decider H is trivially easy for another decider G. E.g. G just has to step the execution and look for a trivial loop, and it's done. Problem is G isn't H and therefore cannot report a result on behalf of H.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 10:42 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <hNednSKur7DvJVbCnZ2dnUU7-d_NnZ2d@giganews.com> |
| In reply to | #2091 |
On 12/5/2020 7:41 AM, Andy Walker wrote: > On 05/12/2020 11:50, Kaz Kylheku wrote: >> Suppose that your execution machine were to generate a "recursion >> detected" >> exception that is visible to H. The sysem doesn't jus stop, but H can >> catch this exception, unwind to the topmost invocation and then return a >> true or false value. > > If "H" is the usual putative halt-decider, then "H" can do no > such thing. "H" either is or is equivalent to a fully deterministic > Turing machine operating on a tape with known contents. If you want > to include what we might call exceptions in the execution, then "H" > itself has to generate them and use them to alter, in a deterministic > way, the contents of its tape and/or its state. If you want to run > "H" as a C program or near equivalent, then it has to run in a sandbox > of some form; and then "H_hat" is a similar program derived from "H" > in the usual way, equally running in a sandbox. What some monitoring > system might then do to "H" and "H_hat" is completely irrelevant. > > If you want to include a monitoring system, then that is part > of "H"; and then "H_hat" equally includes that system and uses it in > the same way. > > This is the generic problem with everything that PO is trying > to do. He is obsessed with what "H" and "H_hat" do. But that is > actually of no interest, and he can produce whatever traces he likes > of what [eg] "H(H_hat,H_hat)" does; no-one cares. All that matters > is that what "H" says "H_hat" does is different from what "H_hat" > actually does, which it is by the construction of "H_hat". Contrary > to assertions, there is no recursion, let alone "infinite recursion", > involved in this process /except/ as someone writing "H" chooses to > introduce it. "H" can't /call/ "H_hat"; "H_hat" is not supplied to > "H" as executable code but as source [tweaked from the source of "H"]. > "H" can, of course, choose to emulate [or even compile] "H_hat", as > any UTM can do, but that's a different matter. > >> It's just not obvious how that helps. > > Further, it's obvious that it doesn't help. If you go down > that road, then "H" is no longer the analysing pseudo-halt decider, > but is that embedded in an operating system operating in a sandbox; > and "H_hat" equally is a tweaked version of that, and if you want > to see from outside what "H" and "H_hat" do, you have to embed all > that in a monitoring external OS. You have gained nothing except > yet another layer of obfuscation. The mistake is continuing to > call the result "H" or "H_hat", as though the extra layer has not > been introduced. > > A [much] more precise notation would help, esp to maintain > distinctions between executables and sources, between programs and > subroutines, and between different versions of code. But no-one > else seems to want that, sadly. > I only skimmed the above and my reply is the at the TM level the halt decider is derived from a single UTM that has been adapted to become a halt decider. When we envision the sandbox idea implemented as Turing machines then this sandbox is merely a UTM that also carefully examines what its input does. -- 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-05 11:24 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <5JOdndnXndfEX1bCnZ2dnUU7-Y_NnZ2d@giganews.com> |
| In reply to | #2091 |
On 12/5/2020 11:08 AM, Mr Flibble wrote:
> On 05/12/2020 16:55, olcott wrote:
>> On 12/5/2020 7:58 AM, Malcolm McLean wrote:
>>> On Saturday, 5 December 2020 at 11:50:11 UTC, Kaz Kylheku wrote:
>>>>
>>>> It's obvious that we can run all the halt-deciding calculation in a
>>>> monitored machine which will stop it under various conditions like
>>>> "loop
>>>> detected" or "too many instructions executed" or whatever we like.
>>>> But in all such cases, the halt-deciding calculation has failed to
>>>> decide. The function H has not terminated with a true or false return
>>>> value, as required.
>>>>
>>> Yes. But the first point is that it is reasonable to run all programs
>>> under
>>> a simulator which terminates them when a tight infinite loop is
>>> detected.
>>> That's not really a computational theory argument, but it sets the
>>> scene.
>>> What PO is doing is not necessarily contrived.
>>>
>>> Additonaly, the supervisor is the same as "Halts". That muddies the
>>> waters
>>> even more, but doesn't fundamentally change things.
>>>
>>> The second point is that, if everything is being run under a supervisor,
>>> "Halts" can return a value to main when run directly, but be aborted by
>>> the supervisor when called from H_Hat. You'd have to write the
>>> supervisor
>>> carefully to avoid making it too obvious that this step is contrived,
>>> but the
>>> Linz challenge could be met.
>>>
>>> In a sense. Of course it is a cheat. But it's a new cheat, and that's
>>> all that
>>> any sensible person would ever have expected from these threads.
>>>
>>
>> This is not any sort of a cheat what-so-ever it is a direct refutation
>> of the Peter Linz halting problem undecidability proof:
>>
>> void H_Hat(u32 P)
>> {
>> u32 Input_Halts = H(P, P);
>> if (Input_Halts)
>> HERE: goto HERE;
>> else
>> HALT
>> }
>>
>> int main()
>> {
>> Input_Halts = H((u32)H_Hat, (u32)H_Hat);
>> Output("H_Hat(H_Hat) Halts =", Input_Halts);
>> HALT;
>> }
>
> Yet again you are failing to show how your halting decider decides an
> arbitrary program doesn't halt when given arbitrary input. Still nothing
> to see here.
>
> /Flibble
>
You continue to ignore the fact that once I have showed how to decide
the "provably" impossible to decide inputs that I have refuted all the
conventional halting problem proofs.
--
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-04 19:58 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <LpmdnUimmdXZdFfCnZ2dnUU7-bPNnZ2d@giganews.com> |
| In reply to | #2076 |
On 12/4/2020 7:13 PM, Ben Bacarisse wrote:
> Kaz Kylheku <563-365-8930@kylheku.com> writes:
>
>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>> On 12/3/2020 7:17 PM, Kaz Kylheku wrote:
>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 12/3/2020 6:26 PM, Kaz Kylheku wrote:
>>>>>> ["Followup-To:" header set to comp.theory.]
>>>>>> On 2020-12-03, olcott <NoOne@NoWhere.com> wrote:
>>>>>>> The key thing is that I correctly refuted the entire Ĥ pattern.
>>>>>>
>>>>>> Yes, but Linz anticipates your objection to the fixed pattern.
>>>>>
>>>>> I do not accept that.
>>>>
>>>> But he acknowledges the objection. He is granting that it's right,
>>>> with regard to that specific configuration given in the diagram!
>>>>
>>>> Again:
>>>>
>>>> Linz: "One may object to Definition 12.1, since we required that, to
>>>> solve the halting problem, H had to start and end in very specific
>>>> configurations."
>>>
>>> I don't see this.
>>> The specific configuration is that the halt decider begins executing at
>>> its beginning and ends with a yes or no answer. This is categorically
>>> every possibly correct configuration.
>>
>> By "configuration", I'm almost certain that Linz is referring to the
>> entire structure of his Figure 12.2, and not simply to its initial and
>> final states. He's not using the word "configuration" in the restricted
>> sense of "application configuration settings", which refer only to the
>> mutable state parts.
>
> I doubt that. He is using the term in a technical sense that is common
> in this field. He defines it early on (page 38 in an old edition) and
> uses it consistently throughout.
A configuration of a Turing machine is an ordered triple
(x, q, k) ∈ Σ∗ × K × N, where x denotes the string on the
tape, q denotes the machine’s current state, and k denotes
the position of the machine on the tape.
http://www.cs.cornell.edu/courses/cs4820/2013su/tm-notes.pdf
>> In other words, Linz obviously knows well that a fixed pattern for
>> fooling a halting decider is not sufficient. He's dealing with that very
>> objection. (He may not be doing it rigrously and with a full treatment,
>> but he's fully covered himself against accusations of ignorance or
>> neglect.)
>
> I disagree, but these threads are sapping my will to live!
> I would say that the pattern /is/ sufficient.
That looks like good news for the significance of my work.
> His disclaimer about configurations is much more narrow.
>
> Also, please note that this is not the "real" proof Linz offers. He
> presents this argument because of it's historical interest. There was
> no developed theory of computation and languages when Turing used this
> argument, so he could not prove the halting theorem the modern way.
> Linz's proof is a simple consequence of theorem 11.5 (if I recall
> correctly).
>
--
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-05 19:37 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <tZCdnd_R6_JUqFHCnZ2dnUU7-UHNnZ2d@giganews.com> |
| In reply to | #2082 |
On 12/5/2020 7:30 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 12/4/2020 7:13 PM, Ben Bacarisse wrote:
> <cut>
>>> I would say that the pattern /is/ sufficient.
>>
>> That looks like good news for the significance of my work.
>
> Is being wrong about something that matters better than being wrong
> about something incidental?
>
The only way that you can say that without flat out lying is to make
sure that you keep ignoring this proof that I am correct.
You cannot possibly point to any logical error because there are no
logical errors.
Actual debug trace of H() correctly deciding halting on H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = H(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
int main()
{
H((u32)H_Hat, (u32)H_Hat);
HALT;
}
_H_Hat()
[000005e0](01) 55 push ebp
[000005e1](02) 8bec mov ebp,esp
[000005e3](01) 51 push ecx
[000005e4](03) 8b4508 mov eax,[ebp+08]
[000005e7](01) 50 push eax
[000005e8](03) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) 51 push ecx
[000005ec](05) e87ffdffff call 00000370
[000005f1](03) 83c408 add esp,+08
[000005f4](03) 8945fc mov [ebp-04],eax
[000005f7](04) 837dfc00 cmp dword [ebp-04],+00
[000005fb](02) 7404 jz 00000601
[000005fd](02) ebfe jmp 000005fd
[000005ff](02) eb01 jmp 00000602
[00000601](01) f4 hlt
[00000602](02) 8be5 mov esp,ebp
[00000604](01) 5d pop ebp
[00000605](01) c3 ret
_main()
[00000610](01) 55 push ebp
[00000611](02) 8bec mov ebp,esp
[00000613](05) 68e0050000 push 000005e0
[00000618](05) 68e0050000 push 000005e0
[0000061d](05) e84efdffff call 00000370
[00000622](03) 83c408 add esp,+08
[00000625](01) f4 hlt
[00000626](01) 5d pop ebp
[00000627](01) c3 ret
Output_Debug_Trace() Trace_List.size(20)
[00000610](01) EMU_Level(0) 55 push ebp
[00000611](02) EMU_Level(0) 8bec mov ebp,esp
[00000613](05) EMU_Level(0) 68e0050000 push 000005e0
[00000618](05) EMU_Level(0) 68e0050000 push 000005e0
[0000061d](05) EMU_Level(0) e84efdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(1) 55 push ebp
[000005e1](02) EMU_Level(1) 8bec mov ebp,esp
[000005e3](01) EMU_Level(1) 51 push ecx
[000005e4](03) EMU_Level(1) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(1) 50 push eax
[000005e8](03) EMU_Level(1) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(1) 51 push ecx
[000005ec](05) EMU_Level(1) e87ffdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(2) 55 push ebp
[000005e1](02) EMU_Level(2) 8bec mov ebp,esp
[000005e3](01) EMU_Level(2) 51 push ecx
[000005e4](03) EMU_Level(2) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(2) 50 push eax
[000005e8](03) EMU_Level(2) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(2) 51 push ecx
[000005ec](05) EMU_Level(2) e87ffdffff call 00000370
----CALL [00000370]
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 | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2020-12-03 17:29 -0700 |
| Message-ID | <rqbvtr$d4v$1@dont-email.me> |
| In reply to | #2051 |
On 12/3/2020 11:18 AM, olcott wrote: > On 12/3/2020 12:00 PM, Jeff Barnett wrote: >> On 11/27/2020 4:44 PM, Jeff Barnett wrote: >>> I will present an interesting example for a working a working halt >>> detector to display its worthiness of the title. The code will be >>> presented in pseudo Lisp and can be translated into your favorite >>> language, e.g., C, TM, or even your favorite real Lisp. I don't think >>> there will be many takers or comments so I'm probably wasting my time. >>> >>> The halt function value is boolean i.e., T or NIL, and has one >>> mandatory argument, a function, followed by zero or more arguments >>> that are for the function. Thus, the outline of the halt detector is >>> >>> (define haltp (function &rest arguments) >>> ;; Value is t if (apply function arguments) is a finite, halting >>> ;; computation, and nil if it isn't. >>> your implementation of halts that produces a proper t or nil >>> value in >>> a finite amount of time.) >>> >>> (define main () >>> (if (haltp #checker) >>> (print "Conjecture crushed") >>> (print "Conjecture confirmed"))) >>> >>> (define checker () >>> ;; Loop through the positive integers looking for a counter example >>> ;; to the conjecture. If found, return nil. If conjecture is >>> true, we >>> ;; will loop forever. Is there a clever way to tell this will >>> happen? >>> (loop for n = 1 step 1 >>> unless (haltp #check1 n) >>> return nil)) >>> >>> (define check1 (n) >>> ;; N is an integer. We check the conjecture for n. If it's true, we >>> ;; return t. >>> (loop when (= n 1) Return t >>> do (if (evenp n) (setq n (/ n 2)) (setq n (+ (* 3 n) 1)))) >>> >>> Question: What does main print? There can hardly be a simpler >>> computation where halting or not halting is not obvious. Yet Erdos >>> said approximately "Mathematics is not yet ripe enough for such >>> questions." Your fame is ensured if you can shed some light on this >>> example. >> >> I am so disappointed in PO. I'd hoped he would take on the challenge, >> succeed at it, publish his paper, retire from Usenet, and die a happy >> man. Perhaps I should have included a Lisp manual though I thought he >> knew the language. After all he used to barrage the Lisp forum with >> all of his wisdom. > > Because of your reckless disregard for the truth** (you admitted to not > paying attention to the technical substance of what I have been saying) > you may not have noticed that I have provided a correct refutation of > the Peter Linz proof. > > ** The standard required for legal action against libel. Below I refute your silly nonsense and show you to be a freaking fool, but that's not news to anyone. This reply is to call your attention to changing the subject line of this thread. Aren't you the crybaby (sorry to all babies for the comparison) that used to whine "It's my thread and you can't do that off topic stuff ... whaaa, whaaa, etc." Bad Usenet move. I guess you don't know how to use the reply button in your news reader or maybe you tried to code it up yourself? If any of that is try, we have yet another example that you can't program very well, not even enough to hold an entry level job for any length of time. -- Jeff Barnett
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | comp.software-eng
csiph-web