Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #26137 > unrolled thread
| Started by | Jeff Barnett <jbb@notatt.com> |
|---|---|
| First post | 2020-11-27 16:44 -0700 |
| Last post | 2020-12-05 00:41 -0700 |
| Articles | 20 on this page of 70 — 10 participants |
Back to article view | Back to comp.theory
Halting test example Jeff Barnett <jbb@notatt.com> - 2020-11-27 16:44 -0700
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-03 11:00 -0700
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 ] Jeff Barnett <jbb@notatt.com> - 2020-12-03 12:18 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 13:23 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] Jeff Barnett <jbb@notatt.com> - 2020-12-03 12:44 -0700
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 Kylheku <563-365-8930@kylheku.com> - 2020-12-03 20:21 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 14:48 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-03 22:58 +0000
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) Daniel Pehoushek <pehoushek1@gmail.com> - 2020-12-03 18:20 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Jeff Barnett <jbb@notatt.com> - 2020-12-03 21:23 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-04 19:49 -0800
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) Richard Damon <Richard@Damon-Family.org> - 2020-12-04 17:18 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 17:07 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Richard Damon <Richard@Damon-Family.org> - 2020-12-04 18:31 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 18:05 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Richard Damon <Richard@Damon-Family.org> - 2020-12-04 19:43 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 01:59 +0000
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) Andy Walker <anw@cuboid.co.uk> - 2020-12-05 16:57 +0000
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) Andy Walker <anw@cuboid.co.uk> - 2020-12-05 17:38 +0000
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) Andy Walker <anw@cuboid.co.uk> - 2020-12-05 13:41 +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) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-12-05 05:58 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 10:55 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2020-12-05 17:08 +0000
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-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) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-05 01:13 +0000
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) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-06 01:30 +0000
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 ](Kaz) Richard Damon <Richard@Damon-Family.org> - 2020-12-05 21:06 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ] Jeff Barnett <jbb@notatt.com> - 2020-12-03 17:29 -0700
Re: Halting test example olcott <NoOne@NoWhere.com> - 2020-12-03 18:52 -0600
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-03 21:09 -0700
Re: Halting test example olcott <NoOne@NoWhere.com> - 2020-12-03 22:15 -0600
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-04 10:13 -0700
Re: Halting test example olcott <NoOne@NoWhere.com> - 2020-12-04 11:17 -0600
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-05 00:41 -0700
Page 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
| 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 | #26483 |
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 | Andy Walker <anw@cuboid.co.uk> |
|---|---|
| Date | 2020-12-05 16:57 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqge58$rba$1@gioia.aioe.org> |
| In reply to | #26479 |
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.
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. That's "H", not "H" running
under some monitor [which would need itself to be part of "H"].
IOW, the point of the HP is not that some instances cannot be
decided, but that any proposed algorithm [equivalently: program] gets
the answer wrong [if it gives an answer at all]. You are in danger of
falling into the same trap that you fell into with Goedel; for any
given set of axioms, there is a proposition that is undecidable /within
those axioms/ [with the usual caveats]. That does not say anything
about whether the proposition is undecidable more generally, only that
the axioms are not powerful enough.
> Deciding halting on your example is probably not provably
> impossible.
Of course it's not provably impossible. Whether you're talking
about Goldbach or Collatz, the conjecture may in fact /be/ unprovable,
but you can't prove it so, for that would be a proof of truth =><=.
But note that it is known [Conway] that there is no algorithm to solve
generalised Collatz problems. Indeed, there are lots of problems for
which it is known that no algorithm is possible [equivalently, that
no proof can be found within ordinary arithmetic. For some perhaps
surprising examples, see [eg]
https://en.wikipedia.org/wiki/Busy_beaver#Related_functions
[esp sections 2.1.1, 2.1.2 and 2.4].
> Once everyone agrees that I have correctly decided the provable
> impossible to decide input, [...]
You will be waiting a long time for /anyone/ competent to agree
with that, let alone everyone.
--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Ascher
[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 | #26486 |
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 | Andy Walker <anw@cuboid.co.uk> |
|---|---|
| Date | 2020-12-05 17:38 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqggin$228$1@gioia.aioe.org> |
| In reply to | #26490 |
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.
--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Ascher
[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 | #26492 |
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 | #26467 |
["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 | Andy Walker <anw@cuboid.co.uk> |
|---|---|
| Date | 2020-12-05 13:41 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqg2ln$15u3$1@gioia.aioe.org> |
| In reply to | #26475 |
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.
--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Ascher
[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 | #26476 |
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 | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2020-12-05 05:58 -0800 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <b969db10-16b7-4971-9e15-df77255e0eb0n@googlegroups.com> |
| In reply to | #26475 |
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.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 10:55 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <OMqdnfiekPcdJlbCnZ2dnUU7-WnNnZ2d@giganews.com> |
| In reply to | #26477 |
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;
}
Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> |
|---|---|
| Date | 2020-12-05 17:08 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <%7PyH.108883$9J69.67283@fx21.ams4> |
| In reply to | #26485 |
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
--
😎
[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 | #26489 |
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-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 | #26475 |
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 | #26482 |
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 | #26519 |
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 | #26521 |
["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 | #26528 |
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 | #26532 |
["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 | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2020-12-05 01:13 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <87360lt5pv.fsf@bsb.me.uk> |
| In reply to | #26432 |
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. > 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. 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). -- Ben.
[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 | #26451 |
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]
Page 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
Back to top | Article view | comp.theory
csiph-web