Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Re: Happy Thanksgiving to all (Ben is proven wrong by the actual facts)

55 views
Skip to first unread message

olcott

unread,
Dec 1, 2020, 10:25:50 PM12/1/20
to
On 11/30/2020 7:40 PM, Ben Bacarisse wrote:
> I replied in a similar way elsewhere after I wrote this, but since this
> contains a short summary of where we stand, I think I'll post it
> anyway.
>
> olcott "Ĥ does not copy its input" <No...@NoWhere.com> writes:
>
>> On 11/29/2020 7:42 PM, Ben Bacarisse wrote:
> <cut>
>>> It does part of the
>>> simulation, but in parallel with detecting when to stop. This is how
>>> you declare the wrong answer to be right -- it only halts because the
>>> detector stopped it. The trouble is, halting is halting. The "because"
>>> does not enter into it.
>>
>> Sure it does and you already agreed:
>>
>> On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
>>> A computation that would not halt if its simulation were not
>>> halted is indeed a non-halting computation.
>
> You keep quoting this, apparently unaware of what it means. With a
> student, I'd write an example and ask some questions, but you don't
> answer questions and you don't want to learn so all I can do is write an
> explanation for anyone who wants to read it.
>
> You presented Halts (the details don't matter at this stage) and I
> presented
>
> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>
> You informed the world that Halts(Confound_Halts, Confound_Halts)
> returns false, and that this is correct because of your weird definition
> of what a non-halting computation is. You quote this remark from me as
> apparently agreeing with some or all of this.
>
> But the computation in question does not fit what I said.
> Confound_Halts(Confound_Halts) is /not/ a computation that would run
> forever unless its simulation were halted. Its simulation would not
> need to be halted. It halts of its own accord as soon a Halts returns
> false.

Here is the actual execution trace proving that you are factually
incorrect.

void Confound_Halts(u32 P)
{
if (DebugTrace(P, P))
while (1);
}


int main()
{
DebugTrace((u32)Confound_Halts, (u32)Confound_Halts);
HALT;
}


_Confound_Halts()
[0000053c](01) 55 push ebp
[0000053d](02) 8bec mov ebp,esp
[0000053f](03) 8b4508 mov eax,[ebp+08]
[00000542](01) 50 push eax
[00000543](03) 8b4d08 mov ecx,[ebp+08]
[00000546](01) 51 push ecx
[00000547](05) e8f0fdffff call 0000033c
[0000054c](03) 83c408 add esp,+08
[0000054f](02) 85c0 test eax,eax
[00000551](02) 740b jz 0000055e
[00000553](05) ba01000000 mov edx,00000001
[00000558](02) 85d2 test edx,edx
[0000055a](02) 7402 jz 0000055e
[0000055c](02) ebf5 jmp 00000553
[0000055e](01) 5d pop ebp
[0000055f](01) c3 ret

_main()
[0000056c](01) 55 push ebp
[0000056d](02) 8bec mov ebp,esp
[0000056f](05) 683c050000 push 0000053c
[00000574](05) 683c050000 push 0000053c
[00000579](05) e8befdffff call 0000033c
[0000057e](03) 83c408 add esp,+08
[00000581](01) f4 hlt
[00000582](01) 5d pop ebp
[00000583](01) c3 ret

Output_Debug_Trace() [00010b24] size(72) capacity(65536)
[0000056c](01) 55 push ebp
[0000056d](02) 8bec mov ebp,esp
[0000056f](05) 683c050000 push 0000053c
[00000574](05) 683c050000 push 0000053c
[00000579](05) e8befdffff call 0000033c ----CALL [0000033c]
[0000053c](01) 55 push ebp
[0000053d](02) 8bec mov ebp,esp
[0000053f](03) 8b4508 mov eax,[ebp+08]
[00000542](01) 50 push eax
[00000543](03) 8b4d08 mov ecx,[ebp+08]
[00000546](01) 51 push ecx
[00000547](05) e8f0fdffff call 0000033c ----CALL [0000033c]
[0000053c](01) 55 push ebp
[0000053d](02) 8bec mov ebp,esp
[0000053f](03) 8b4508 mov eax,[ebp+08]
[00000542](01) 50 push eax
[00000543](03) 8b4d08 mov ecx,[ebp+08]
[00000546](01) 51 push ecx
[00000547](05) e8f0fdffff call 0000033c ----CALL [0000033c]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:




--
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

olcott

unread,
Dec 2, 2020, 12:12:17 PM12/2/20
to
On 12/1/2020 9:40 PM, Chris M. Thomasson wrote:
> [...]
>
> Think of something like:
>
> <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;
>         }
>     }
> }
> ______________________________
>
>
> Will this halt or not?


That does not matter.

>>> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }

What matters is that the above code is computationally equivalent to the
Peter Linz:

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

When I show that the computational equivalent of the Linz Ĥ is
decidable, then then Linz proof is refuted.

olcott

unread,
Dec 2, 2020, 12:39:24 PM12/2/20
to
On 12/2/2020 11:17 AM, Malcolm McLean wrote:
> H_Hat is decideable. It either halts or it doesn't. However it's not decideable
> by H. That is the challenge, to get consistent results from running H(H_Hat, H_Hat)
> and running H_Hat(H_Hat) on its own.

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine

Here is H_Hat (computational equivalent to the Linz Ĥ) being correctly
decided by DebugTrace() (computational equivalent to the Linz H).


void H_Hat(u32 P)
{
u32 Aborted = DebugTrace(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}


int main()
{
DebugTrace((u32)H_Hat, (u32)H_Hat);
HALT;
}


_H_Hat()
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354
[00000595](03) 83c408 add esp,+08
[00000598](03) 8945fc mov [ebp-04],eax
[0000059b](04) 837dfc00 cmp dword [ebp-04],+00
[0000059f](02) 7403 jz 000005a4
[000005a1](01) f4 hlt
[000005a2](02) eb02 jmp 000005a6
[000005a4](02) ebfe jmp 000005a4
[000005a6](02) 8be5 mov esp,ebp
[000005a8](01) 5d pop ebp
[000005a9](01) c3 ret

_main()
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
[000005bc](05) 6884050000 push 00000584
[000005c1](05) e88efdffff call 00000354
[000005c6](03) 83c408 add esp,+08
[000005c9](01) f4 hlt
[000005ca](01) 5d pop ebp
[000005cb](01) c3 ret


Output_Debug_Trace() [00010bd3] size(80) capacity(65536)
[000005b4](01) 55 push ebp
[000005b5](02) 8bec mov ebp,esp
[000005b7](05) 6884050000 push 00000584
[000005bc](05) 6884050000 push 00000584
[000005c1](05) e88efdffff call 00000354 ----CALL [00000354]
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
[00000584](01) 55 push ebp
[00000585](02) 8bec mov ebp,esp
[00000587](01) 51 push ecx
[00000588](03) 8b4508 mov eax,[ebp+08]
[0000058b](01) 50 push eax
[0000058c](03) 8b4d08 mov ecx,[ebp+08]
[0000058f](01) 51 push ecx
[00000590](05) e8bffdffff call 00000354 ----CALL [00000354]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:



olcott

unread,
Dec 2, 2020, 5:20:11 PM12/2/20
to
On 12/2/2020 3:45 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2020-12-02, olcott <No...@NoWhere.com> wrote:
>> On 12/2/2020 2:11 PM, Richard Damon wrote:
>>> On 12/2/20 2:12 PM, olcott wrote:
>>>> On 12/2/2020 12:42 PM, Richard Damon wrote:
>>>
>>>>> Which means your H_Hat isn't the equivalent of Linz H_Hat, as DebugTrace
>>>>> is nothing like H in Linz.
>>>>>
>>>>
>>>> You keep (intentionally?) forgetting that the ⊢* (wildcard) state
>>>> transitions explicitly specify that the code can be any damn thing that
>>>> correctly decides halting on its inputs:
>>>>
>>>>     The input to H will be the description (encoded in some form)
>>>>     of M, say WM, as well as the input w. The requirement is then
>>>>     that, given any (WM, w), the Turing machine H will halt with
>>>>     either a yes or no answer.
>>>>
>>>>     H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>>>     H.q0 wMw ⊢* H.no    if M applied to w [would] not halt.
>>>>     (Linz 1990:318)
>>>>
>>>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>>> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
>>>> Lexington/Toronto: D. C. Heath and Company.
>>>>
>>>>
>>>
>>> BUT it MUST end up at H.no or H.yes at the end, or it fails to meet the
>>> requirements. 'Aborting' the calling machine is a failure to reach one
>>> of those two states.
>>>
>>> That is a FATAL flaw in your 'equivalence'. You don't give the answer.
>>>
>>> Yes, you can do whatever computation you want on the way to get there,
>>> but you MUST get to one of the two output states of H, and when you get
>>> to those states, H^ will then get the answer and proceed.
>>>
>>
>> This <is> a "no" (would not halt) at the operating system level:
>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>
> It's possible to develop a test case which terminates and yet which
> coaxes your machine into hitting the above situation.
>
> I believe you have successfully articulated a known and obvious flaw in
> the pseudo-code illustrations that are used in halting proof sketches
> for teaching.
>
> A program of the form
>
> Program(P)
> {
> if (Halts(P, P))
> Loop { }
> else
> return;
> }
>
> does suffer from trivial runaway recursion, if:
>
> - the Halts function simply calls P(P); and
>
> - Halts is invoked at the top-level as Halts(Program, Program).
>
> This allows Halts to, instead of directly calling P(P), to execute P(P)
> with a stepwise monitor that detects the trivial recursion, such
> as using the criterion that no conditional branch instructions are
> being execued in between the unconditional among a couple of functions.
>
> The simplified exmaples used in textbooks have teaching value.
> It is much more difficult to understand halting through the details of
> Turing's tape machines, compared to the illustrative pseudo-code in
> a higher level language.
>
> But any bright undergraduate student can see from those pseudo-code
> examples how the technique generalizes, and how the Program can be
> manipulated to thwart the monitored-execution tactics.
>
> For instance:
>
> Program(P)
> {
> if (ComplicatedComputation(P))
> Dummy_Function_Foo();
> else
> Dummy_Function_Bar();
>
> if (Halts(P, P))
> Loop { }
> else
> return;
> }
>
> the runaway recursion is still there, but now there are many
> instructions in the code path, including conditional ones.
> The trivial recursion detector will not work.

This is no longer a proof that the halting problem us undecidable. It is
merely evidence that solving the halting problem may be difficult.

> The underlying problem is that if the Halts function executes P, either
> directly or through a controlled virtual machine (it doesn't matter), it
> exposes itself to the possibility of non-termination.
>
> If P(P) fails to terminate, and does so in any manner that the virtual
> machine does not handle, then Halts will fail to terminate, and in so
> doing, it will fail to decide. So that is to say, actually executing the
> to-be-analyzed code is extremely risky. It is only useful for catching
> certain cases that are known to occur within a bounded number of
> instructions.
>
> The technique you are using is only good for showing that the strawman
> cases used in the proof sketches have some flaws, and those examples
> cannot be taken literally as the basis for the halting theorem.
>

It directly refutes the computational equivalent of the Linz proof based
on the Linz Ĥ. The Ĥ template <is> decidable. I could write it up on
that basis.

> But that is already obvious; you've put a lot of effort into
> not discovering anything new.
>

Please cite sources for this claim.

You are the very first one that did not simply claim that I am incorrect
on the basis of either a flat out lie or woeful ignorance.

Your claim is that I am correct, yet this is not of great significance.

I will not accept that my work is of inconsequential significance until
I see a specific citation that can be validated.

> (If you don't believe me, why don't you write up what you have so far
> and try to get it published: cite some papers about Halting which use
> pseudo-code examples and argue about how those perform trivial recursion
> which can be detected.)

olcott

unread,
Dec 3, 2020, 1:32:50 PM12/3/20
to
On 12/3/2020 12:18 PM, Kaz Kylheku wrote:
> On 2020-12-03, olcott <No...@NoWhere.com> wrote:
>> On 12/2/2020 7:22 PM, Kaz Kylheku wrote:
>>> The thing to do would be to search for published articles or books
>>> on the halting problem, compile a list of them and see if they are going
>>> wrong in the above way.
>>
>> So then you have no such citation. You are merely going by how obvious
>> it is after the fact of my proof.
>
> If you want to publish an article which exposes issues with the manner
> of presentation of the halting problem in various literature, the onus
> is on you to hunt down the specific pieces literature that you wish to
> target, read all of them, and determine what issues are present in which
> piece.
>

It seems then that your assessment of the significance of my work is
based on "shooting from the hip" rather any degree of academic rigor.

At least (unlike everyone else) when a clear proof is presented you give
a straight up honest assessment and do not resort to any degree of
dishonestly and subterfuge.

I really really, appreciate that. Your review was the threshold that I
was waiting for before I move on to the next level of review. I had to
make sure that my words could be understood before I could proceed.

I did apparently at least correctly refute the Linz proof. That by
itself would qualify for publication somewhere.

Dishonesty and subterfuge:
Ben even claimed that the difference between two literally identical
programs was so great that it is dishonest of me to call them by the
same name.

On 11/30/2020 7:40 PM, Ben Bacarisse wrote:
> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }

void Confound_Halts(u32 P)
{
if (DebugTrace(P, P))
while (1);
}

On 12/2/2020 8:15 PM, Ben Bacarisse wrote:
>> void Confound_Halts(u32 P)
>> {
> <I won't even show the body of this function>
>> }
>
> I don't care what it does. What's more I won't discuss it, other than
> to say that it is dishonest to try to confuse the debate by re-writing
> the function I wrote without changing the name.

olcott

unread,
Dec 7, 2020, 7:19:23 PM12/7/20
to
On 12/7/2020 5:54 PM, Ben Bacarisse wrote:
> Anton Shepelev <anto...@gmail.com> writes:
>
>> Andy Walker:
>>
>>> If you add a "supervisor" program of some sort to
>>> detect all that, then that supervisor is part of a new,
>>> more powerful "Halts", call it "Halts+", and then the
>>> usual method generates a "P+" that "Halts+" gets wrong.
>>> That "Halts+" may be able to decide "P(P)" is of no
>>> interest; what matters is that it gets "P+(P+) wrong.
>>> The well-known result is thus that for any purported halt
>>> decider, there is an easy example of a program that it
>>> fails to decide correctly. What that program in fact does
>>> is irrelevant; it could go either way, depending on
>>> exactly how the pseudo-decider goes wrong.
>>
>> That prompts an experiment: Pete Olcott provides a halt
>> decider, and you provide a program that will fool it.
>
> I've presented that challenge to him and he did in fact respond. He has
> also inadvertently confirmed the facts needed to show that his response
> is incorrect about the confounding example I supplied! In summary, I
> asked him to
>
> Show a function F such that F(P, I) is true if, and only if, P(I) is a
> finite computation and false otherwise.
>
> He replied with
>
> bool Halts(u32 P, u32 I)
> {
> bool Halted = false;
> bool Aborted = false;
> while (!Halted && !Aborted)
> {
> Halted = DebugStep(P, I);
> Aborted = Needs_To_Be_Aborted();
> }
> return !Aborted;
> }
>
> and as I am sure everyone (including PO) expected I replied with
>
> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>
> making the the confounding example for Halts the computation
> Confound_Halts(Confound_Halts) whose halting status is not correctly
> returned by the function call Halts(Confound_Halts, Confound_Halts).
>
> In the ensuing exchange he said both:
>
> "Halts(Confound_Halts, Confound_Halts) returns false."
> Message-ID: <2aidnV9e3qQaOCDC...@giganews.com>
>
> and
>
> "The input to Halts is only finite because..."
> Message-ID: <6eSdnYuLBrIuVFzC...@giganews.com>
>

Message ID's are useless to me when I click on them my newsreader thinks
that I want to send an email. I need date-time-stamps.


int main()
{
Confound_Halts((u32)Confound_Halts);
HALT;
}

int main()
{
Halts((u32)Confound_Halts, (u32)Confound_Halts);
HALT;
}

Both of the above executions are decided as infinitely recursive by the
following criteria:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

I posted the full execution trace proving this.

olcott

unread,
Dec 8, 2020, 9:41:41 PM12/8/20
to
On 12/8/2020 7:28 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 12/7/2020 7:55 PM, Ben Bacarisse wrote:
>
>>> I asked for a
>>> function with well-defined behaviour which you were not able to produce.
>>
>> I PROVIDED IT AND YOU IGNORED IT
>
> Don't be silly. I've explained, using your own words no less, why is
> fails to meet the specification.
>
> I see you have some new friends to talk to about this stuff. You don't
> need me anymore.
>

You disparaged my work using dishonesty and subterfuge.
This is NOT a finite computation:

void Confound_Halts(u32 P)
{
if (Halts(P, P))
while (1);
}

int main()
{
Confound_Halts((u32)Confound_Halts);
HALT;
}

It is aborted according to this criteria:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

_Confound_Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c
[0000064c](03) 83c408 add esp,+08
[0000064f](02) 85c0 test eax,eax
[00000651](02) 740b jz 0000065e
[00000653](05) ba01000000 mov edx,00000001
[00000658](02) 85d2 test edx,edx
[0000065a](02) 7402 jz 0000065e
[0000065c](02) ebf5 jmp 00000653
[0000065e](01) 5d pop ebp
[0000065f](01) c3 ret

_main()
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](05) 683c060000 push 0000063c
[00000674](05) e8c3ffffff call 0000063c
[00000679](03) 83c404 add esp,+04
[0000067c](01) f4 hlt
[0000067d](01) 5d pop ebp
[0000067e](01) c3 ret

Output_Debug_Trace() Trace_List.size(17)
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](05) 683c060000 push 0000063c
[00000674](05) e8c3ffffff call 0000063c // CALL
Confound_Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c // CALL Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c // CALL Halts()
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:



olcott

unread,
Dec 8, 2020, 10:57:18 PM12/8/20
to
On 12/8/2020 9:28 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 12/8/2020 7:28 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 12/7/2020 7:55 PM, Ben Bacarisse wrote:
>>>
>>>>> I asked for a
>>>>> function with well-defined behaviour which you were not able to produce.
>>>>
>>>> I PROVIDED IT AND YOU IGNORED IT
>>>
>>> Don't be silly. I've explained, using your own words no less, why is
>>> fails to meet the specification.
>>>
>>> I see you have some new friends to talk to about this stuff. You don't
>>> need me anymore.
>>>
>>
>> You disparaged my work using dishonesty and subterfuge.
>
> I am trying to disparage it as honestly and openly as possible: it is
> utter garbage.
>
>> This is NOT a finite computation:
>>
>> void Confound_Halts(u32 P)
>> {
>> if (Halts(P, P))
>> while (1);
>> }
>>
>> int main()
>> {
>> Confound_Halts((u32)Confound_Halts);
>> HALT;
>> }
>
> Still posting incomplete examples, I see. What are you hiding?
>
>> It is aborted according to this criteria:
>
> A computation that stops, for whatever reason, is a finite computation.
>
>> On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
>>> A computation that would not halt if its simulation were not
>>> halted is indeed a non-halting computation.
>
> There is no simulator in your example.

The example was executed by a simulator as I have said many hundreds of
times in the last few weeks.

> The simulation of a non-halting
> computation does not halt, and the simulation of a halting one does not
> need to be aborted.

It is a simulation that [would not halt if its simulation was not
halted] thus providing the simulator its criterion measure to stop
simulating this otherwise infinite computation and decide not halting.

olcott

unread,
Dec 9, 2020, 10:17:14 AM12/9/20
to
On 12/9/2020 8:22 AM, Ben Bacarisse wrote:
> Anton Shepelev <anto...@gmail.com> writes:
>
>> I wrote:
>>
>>> OK, let us make a bargain: that sometime in 2021 Pete has
>>> his groundbreaking reasearch published in one of the three
>>> or five respectable computer-science magazines that we
>>> offer.
>>
>> Pardon my English: I meant journals, not magazines.
>
> Except he has no intention of publishing in a proper journal. The usual
> intent of Usenet cranks is to get attention, and PO is no exception.

Stop baselessly disparaging me and my work.

Point out an error in the following or admit that you cannot because
there are none.

Last night your basis was contradicting your own words:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.
>

The following is shown to be decided on the basis of the above criteria:

This input to the Microsoft C compiler produces a COFF object file that
is directly emulated by an x86 emulator.

void Confound_Halts(u32 P)
{
if (Halts(P, P))
while (1);
}


#define HALT __asm hlt
int main()
{
Halts((u32)Confound_Halts, (u32)Confound_Halts);
HALT;
}

_Confound_Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c
[0000064c](03) 83c408 add esp,+08
[0000064f](02) 85c0 test eax,eax
[00000651](02) 740b jz 0000065e
[00000653](05) ba01000000 mov edx,00000001
[00000658](02) 85d2 test edx,edx
[0000065a](02) 7402 jz 0000065e
[0000065c](02) ebf5 jmp 00000653
[0000065e](01) 5d pop ebp
[0000065f](01) c3 ret

_main()
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](05) 683c060000 push 0000063c
[00000674](05) 683c060000 push 0000063c
[00000679](05) e8cefdffff call 0000044c
[0000067e](03) 83c408 add esp,+08
[00000681](01) f4 hlt
[00000682](01) 5d pop ebp
[00000683](01) c3 ret

Output_Debug_Trace() Trace_List.size(18)
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](05) 683c060000 push 0000063c
[00000674](05) 683c060000 push 0000063c
[00000679](05) e8cefdffff call 0000044c // CALL Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c // CALL Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c // CALL Halts()
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

Every time that the same function is called from the same machine
address a second time without any control flow instructions in-between
is a case of infinite recursion.

This is shown at execution trace lines 12-19 above.

olcott

unread,
Dec 9, 2020, 10:41:40 AM12/9/20
to
On 12/9/2020 9:25 AM, Malcolm McLean wrote:
> On Wednesday, 9 December 2020 at 14:55:58 UTC, olcott wrote:
>> On 12/9/2020 6:54 AM, Malcolm McLean wrote:
>>> On Wednesday, 9 December 2020 at 12:30:12 UTC, Leo wrote:
>>>> On 12/9/20 2:46 PM, Anton Shepelev wrote:
>>>>> I wrote:
>>>>>
>>>>>> OK, let us make a bargain: that sometime in 2021 Pete has
>>>>>> his groundbreaking reasearch published in one of the three
>>>>>> or five respectable computer-science magazines that we
>>>>>> offer.
>>>>>
>>>>> Pardon my English: I meant journals, not magazines.
>>>>>
>>>> While the chance of him tricking a magazine employee is higher, I think
>>>> even random magazines would not accept his "research".
>>>>
>>> There are some journals which publish almost anything. But normally
>>> they are trying to claw their way up the academic hierarchy, because
>>> they know that if they can get a reputation, they will attract more papers,
>>> and can charge a larger publication fee (even respectable journals often
>>> charge publication fees).
>>>
>>> I think even they might draw the line at publishing a solution to the
>>> halting problem. However re-title it "Notes on halting in a Turing-like
>>> supervised system" and it would fly through.
>>>
>> Since I am objectively correct why are you even talking this way?
>>
> The "halting problem" is deceptively named. It's not a problem in computing
> science. It's a known and well-established result that precedes even the
> invention of the electronic computer. You might as well offer to build a
> perpetual motion machine.
>
> It's got this in common with perpetual motion machines. Just as everybody
> with a high school science education has heard of perpetual motion,
> every geek has heard of the "halting problem".
>
> So even a journal which publishes almost anything, because its business
> model is to charge publication fees to people who have been rejected
> everywhere else, might draw the line at publishing a solution to the halting
> problem.
>
> What you have done is to expose the fact that the "paradox" proof requires
> H and H_Hat to be Turing machines. If you allow a supervisor program to
> intervene and halt runaway recursion, that's a way out of the paradox, but
> you've broken one of the rules.
>

I have not frigging broken the rules.
When my system is adapted to be performed using Turing machines we
merely execute the program under test using a UTM that has been adapted
to use my method of halt deciding.

The key innovation of my system of defining a halt decider is the
application of this halt deciding criteria:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

Notice that in both of the above quotes future tense is used:
[would not halt]

As soon as the above halt deciding criteria is met the simulator can
stop its simulation and report not-halting. This criteria correctly
decides: {Linz, Sipser, Kozen and Hofcroft}.

olcott

unread,
Dec 9, 2020, 11:16:49 PM12/9/20
to
On 12/9/2020 10:35 AM, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
>> The "halting problem" is deceptively named. It's not a problem in computing
>> science.
>
> It is a problem in computer science; it's only deceptively named from
> outside the field. Computer science is rife with decision problems and
> halting is just another of these. It's just what they are called.
>
>> What you have done is to expose the fact that the "paradox" proof requires
>> H and H_Hat to be Turing machines.
>
> I don't like calling it a "paradox" proof. The commonly presented
> argument is just a shorthand for a diagonal argument.
>
> And it does not require anything to be a TM. The same argument can be
> presenting in all sorts or models. It can even be done in a model that
> uses a Turing-complete C-like notation.
>
>> If you allow a supervisor program to
>> intervene and halt runaway recursion, that's a way out of the paradox, but
>> you've broken one of the rules.
>
> But it doesn't give you a way out! Buried in the supervisor is code
> that has to decide "runaway recursion" and this code is subject to the
> same argument. Either "runaway recursion" will exclude many
> computations that need to be halted, or it will incorrectly include many
> that are about to halt in their own.
>

When a master UTM simulates the {Linz, Sipser, Kozen} counter-example it
terminates them because of infinite recursion before they every receive
any return value.

// Ben Bacarisse from comp.theory
void Confound_Halts(u32 P)
{
if (Halts(P, P))
while (1);
}

int main()
{
HERE: goto HERE;
Confound_Halts((u32)Confound_Halts);
Halts((u32)Confound_Halts, (u32)Confound_Halts);
}

From the perspective of this master UTM all three lines of main()
specify infinite execution.

// Michael Sipser
u32 D(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
return 0; // Indicating not halts
else
return 1; // Indicating halts
}

http://www.liarparadox.org/sipser_165.pdf
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)

http://www.liarparadox.org/kozen_233.pdf
The Kozen computation is identical to the Peter Linz computation merely
swapping function names Linz.H is swapped for Kozen.K and Linz.Ĥ is
swapped for Kozen.N

Kozen, Dexter 1997. Automata and Computability. New York:
Springer-Verlag. (231-234).

olcott

unread,
Dec 10, 2020, 9:50:23 AM12/10/20
to
On 12/10/2020 5:41 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> Think of this is simpler terms:
>> I have an x86 emulator that aborts infinite loops and infinite
>> recursion.
>
> A ridiculously trivial claim. You really need to take care with your
> language.
>

You are a master of deception of avoiding the point:

Stop baselessly disparaging me and my work.

Point out an error in the following or admit that you cannot because
there are none.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.
>

The following is shown to be decided on the basis of the above criteria:

This input to the Microsoft C compiler produces a COFF object file that
is directly emulated by an x86 emulator.


void Confound_Halts(u32 P)
{
if (Halts(P, P))
while (1);
}

#define HALT __asm hlt

int main()
{
Confound_Halts((u32)Confound_Halts);
HALT;
}


_Confound_Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c
[0000064c](03) 83c408 add esp,+08
[0000064f](02) 85c0 test eax,eax
[00000651](02) 740b jz 0000065e
[00000653](05) ba01000000 mov edx,00000001
[00000658](02) 85d2 test edx,edx
[0000065a](02) 7402 jz 0000065e
[0000065c](02) ebf5 jmp 00000653
[0000065e](01) 5d pop ebp
[0000065f](01) c3 ret

_main()
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](05) 683c060000 push 0000063c
[00000674](05) e8c3ffffff call 0000063c
[00000679](03) 83c404 add esp,+04
[0000067c](01) f4 hlt
[0000067d](01) 5d pop ebp
[0000067e](01) c3 ret

Output_Debug_Trace() Trace_List.size(17)
[0000066c](01) 55 push ebp
[0000066d](02) 8bec mov ebp,esp
[0000066f](05) 683c060000 push 0000063c
[00000674](05) e8c3ffffff call 0000063c // CALL
Confound_Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c // CALL Halts()
[0000063c](01) 55 push ebp
[0000063d](02) 8bec mov ebp,esp
[0000063f](03) 8b4508 mov eax,[ebp+08]
[00000642](01) 50 push eax
[00000643](03) 8b4d08 mov ecx,[ebp+08]
[00000646](01) 51 push ecx
[00000647](05) e800feffff call 0000044c // CALL Halts()
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

Every time that the same function is called from the same machine
address a second time without any control flow instructions in-between
is a case of infinite recursion.
This is shown at execution trace lines 12-19 above.

olcott

unread,
Dec 10, 2020, 10:35:55 AM12/10/20
to
On 12/10/2020 9:18 AM, André G. Isaak wrote:
> On 2020-12-10 07:44, olcott wrote:
>> On 12/10/2020 12:54 AM, André G. Isaak wrote:
>>> On 2020-12-09 21:48, olcott wrote:
>>>> On 12/9/2020 10:36 PM, André G. Isaak wrote:
>>>>> On 2020-12-09 11:04, olcott wrote:
>>>>>> On 12/9/2020 10:52 AM, Kaz Kylheku wrote:
>>>>>>> On 2020-12-09, olcott <No...@NoWhere.com> wrote:
>>>>>>>> On 12/9/2020 5:43 AM, Anton Shepelev wrote:
>>>>>>>>> Ben Bacarisse to Anton Shepelev about Pete Olcott:
>>>>>>>>>
>>>>>>>>>>> That prompts an experiment: Pete Olcott provides a halt
>>>>>>>>>>> decider, and you provide a program that will fool it.
>>>>>>>>>>
>>>>>>>>>> I've presented that challenge to him and he did in fact
>>>>>>>>>> respond.
>>>>>>>>>
>>>>>>>>> OK, let us make a bargain: that sometime in 2021 Pete has
>>>>>>>>> his groundbreaking reasearch published in one of the three
>>>>>>>>> or five respectable computer-science magazines that we
>>>>>>>>> offer. The losing side sends the winner a book that he
>>>>>>>>> wants.  If Pete wins, he will get about 15 books for free.
>>>>>>>>> If he loses, he shall have to buy a book for each of us :-)
>>>>>>>>> He has more than a year, so I think it a fair bargain.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> I would be happy with a fair and honest review based on paying
>>>>>>>> close
>>>>>>>> attention to what I say and staying sharply focused on the point
>>>>>>>> at hand.
>>>>>>>
>>>>>>> The problem you're going to run into is getting a correct
>>>>>>> return value out of the Halts function.
>>>>>>>
>>>>>>> You've built a system which can tell that the overall situation his
>>>>>>> runaway recursion. Somehow you hope that this can inform Halts
>>>>>>> so that Halts can return the correct value, thereby refuting proofs
>>>>>>> which rely on the impossibility of that event.
>>>>>>>
>>>>>>> However, in a nutshell, the issue is this:
>>>>>>>
>>>>>>>     Even if Halts has access to a "magic oracle" which knows
>>>>>>>     the halting answer for every <P, I> pair, Halts still cannot
>>>>>>>     return the right answer for <H_Hat, H_Hat>.
>>>>>>>
>>>>>>> If Halts asks the magic oracle, "does H_Hat(H_Hat) halt?",
>>>>>>> the oracle will give it the correct answer.
>>>>>>>
>>>>>>> However, how can Halts return that answer? Halts is itself
>>>>>>> embedded in
>>>>>>> H_Hat, which intercepts the answer and behaves in a contradicting
>>>>>>> manner. That is inescapable.
>>>>>>
>>>>>> Even when Halts is embedded within H_Hat the master UTM based halt
>>>>>> decider sees this and decides halting correctly anyway. To do this
>>>>>> it must stop simulating its infinitely recursive input of H_Hat()
>>>>>> calling its embedded Halts().
>>>>>
>>>>> Linz's proof states that for every putative halt decider H, one can
>>>>> derive a program H_Hat such that H(H_Hat, H_Hat) cannot be
>>>>> correctly decided.
>>>>>
>>>>
>>>> Yes and I prove {Linz, Sipser, and Kozen} are wrong about this.
>>>>
>>>>> Don't you see that your "Master UTM" isn't even attempting to
>>>>> perform the computation equivalent to H(H_Hat, H_Hat); it is
>>>>> performing the computation H(main, NULL) which is something
>>>>> entirely different.
>>>>>
>>>>
>>>> I have fully operational code to prove that is ridiculous.
>>>>
>>>> Actual debug trace of H() deciding halting on H_Hat()
>>>>
>>>> Input to Microsoft C compiler, output is from generated COFF object
>>>> file. Execution trace is from an x86 emulator.
>>>>
>>>> #define HALT __asm hlt
>>>>
>>>> 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)   55                  push ebp
>>>> [00000611](02)   8bec                mov ebp,esp
>>>> [00000613](05)   68e0050000          push 000005e0
>>>> [00000618](05)   68e0050000          push 000005e0
>>>> [0000061d](05)   e84efdffff          call 00000370       ----CALL
>>>> [00000370]
>>>> [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       ----CALL
>>>> [00000370]
>>>> [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       ----CALL
>>>> [00000370]
>>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>>>> Number of Instructions Executed(2777)
>>>>
>>>> Every time that the same function is called from the same machine
>>>> address a second time without any control flow instructions
>>>> in-between is a case of infinite recursion. This is shown at
>>>> execution trace lines 13-21 above.
>>>
>>> Except, as has been noted by others, your trace is incomplete.
>> I could provide 142 more pages of detail and this extra detail would
>> not change a thing.
>>
>>>>> When you add this "master UTM" to your system and claim that this
>>>>> is your actual halt detector, your H_Hat needs to be derived from
>>>>> that master UTM. It would need to do everything that your master
>>>>> UTM does (including your weird automatic invocation of Halts(main)
>>>>> etc), but at the point where your master UTM returns 'halts', it
>>>>> would need to enter an infinite loop.
>>>>
>>>> I have fully operational code to prove that is ridiculous.
>>>
>>> I don't think you grasp how proofs work. Proofs have premises and
>>> conclusions. Code traces do not. Your "fully operational code"
>>> doesn't even remotely address my objection above.
>>
>> A code trace <is> a formal proof of the execution of the x86 language.
>
> No, a code trace is not a formal proof of anything.

A code trace is a totally complete proof of what the code actually does
on its input.

>>>>> You'd need to then invoke your master UTM with an input of the
>>>>> above H_Hat, H_Hat (not of main, NULL). If you don't do this, your
>>>>> alleged 'solution' has nothing to do with Linz's proof.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> Think of this is simpler terms:
>>>> I have an x86 emulator that aborts infinite loops and infinite
>>>> recursion.
>>>
>>> Which *claims* to do this. You have not proven that it actually does
>>> this reliably,
>>
>> Sure I have immediately above you just didn't bother to pay attention
>> or the x86 language is over your head.
>
> The problem is that there *are* conditional branches between the above
> calls. You just don't show them. There must be because your 'halt
> detector' makes a decision as to whether to abort at any given call.
> That involves a conditional branch.

THE MOST IMPORTANT WORDS THAT I HAVE EVER SAID ON THIS SUBJECT:
THE MOST IMPORTANT WORDS THAT I HAVE EVER SAID ON THIS SUBJECT:
THE MOST IMPORTANT WORDS THAT I HAVE EVER SAID ON THIS SUBJECT:

All conditional branches that are in the halt decider and not in the
user code can be correctly ignored within the context of the following
halt deciding criteria:

Notice the future tense of: [would not halt]

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

> And those same conditional branches also guarantee that Halts(H_Hat,
> H_Hat) will in fact halt, despite your claim to the contrary.
> Halts(H_Hat, H_Hat) would have aborted its input and halted using the
> exactly the same mechanism that your "global" decider uses had the
> global decider not aborted it prematurely.
>
> You are under the misguided impression that by calling some piece of
> code part of the 'operating system', that it somehow ceases to be part
> of a computation which calls upon it. That is simply not the case.
>
>>> nor have you shown that this has any relevance to Linz given that you
>>> are not deriving your H_Hat from your halt decider correctly.
>
> No comment on the above?
>
> André
>

I already addressed what you said.

olcott

unread,
Dec 10, 2020, 11:12:09 AM12/10/20
to
On 12/10/2020 9:55 AM, André G. Isaak wrote:
> It isn't a proof of anything. It illustrates what a particular run of a
> piece of software does. It doesn't in any way demonstrate that the
> results it produces are correct (i.e. produce the correct result for the
> problem the software purports to solve).

The execution trace does prove that it applied its criteria to its input
correctly.

>>>>>>> You'd need to then invoke your master UTM with an input of the
>>>>>>> above H_Hat, H_Hat (not of main, NULL). If you don't do this,
>>>>>>> your alleged 'solution' has nothing to do with Linz's proof.
>>>>>>>
>>>>>>> André
>>>>>>>
>>>>>>
>>>>>> Think of this is simpler terms:
>>>>>> I have an x86 emulator that aborts infinite loops and infinite
>>>>>> recursion.
>>>>>
>>>>> Which *claims* to do this. You have not proven that it actually
>>>>> does this reliably,
>>>>
>>>> Sure I have immediately above you just didn't bother to pay
>>>> attention or the x86 language is over your head.
>>>
>>> The problem is that there *are* conditional branches between the
>>> above calls. You just don't show them. There must be because your
>>> 'halt detector' makes a decision as to whether to abort at any given
>>> call. That involves a conditional branch.
>>
>> THE MOST IMPORTANT WORDS THAT I HAVE EVER SAID ON THIS SUBJECT:
>> THE MOST IMPORTANT WORDS THAT I HAVE EVER SAID ON THIS SUBJECT:
>> THE MOST IMPORTANT WORDS THAT I HAVE EVER SAID ON THIS SUBJECT:
>>
>> All conditional branches that are in the halt decider and not in the
>> user code can be correctly ignored within the context of the following
>> halt deciding criteria:
>
> That is simply false, no matter how many times you repeat it.

There are two steps to proving that that my statement is correct:
(1) Verifying that this is correct halt deciding criteria.
(2) Verifying that the input meets this criteria.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

The only reason that people believe that I am incorrect is that they
never bothered to verify the above two steps.

> The Halt
> Decider is being used as *input* to itself, so every branch which is
> part of the Halt Decider is also part of the computation performed by
> it's input. If you ignore these calls, then your "halt decider" is not
> actually evaluating the input that it is being given.
>>
>> Notice the future tense of: [would not halt]
>
> "would not halt" is not future tense.
>
> And Halts(H_Hat, H_Hat) *would* have halted had your global 'decider'
> not aborted it, so it doesn't meet the below criterion anyways.
>
> > On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> >> A computation that would not halt if its simulation were not
> >> halted is indeed a non-halting computation.
>
> André

olcott

unread,
Dec 12, 2020, 11:51:14 PM12/12/20
to
On 12/10/2020 2:26 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 12/10/2020 5:41 AM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> Think of this is simpler terms:
>>>> I have an x86 emulator that aborts infinite loops and infinite
>>>> recursion.
>>>
>>> A ridiculously trivial claim. You really need to take care with your
>>> language.
>>>
>>
>> You are a master of deception of avoiding the point:
>
> I am just pointing out you need to say what you mean. Having an x86
> emulator that aborts infinite loops and infinite recursion is trivial
> and (I hope) not what you think you have.
>

Having an equivalent computation to the {Linz, Sipser} H correctly
deciding the Linz Ĥ, the Sipser D and the Kozen N is what I have.

olcott

unread,
Dec 14, 2020, 12:20:25 AM12/14/20
to
On 12/13/2020 7:14 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 12/10/2020 2:26 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 12/10/2020 5:41 AM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> Think of this is simpler terms:
>>>>>> I have an x86 emulator that aborts infinite loops and infinite
>>>>>> recursion.
>>>>>
>>>>> A ridiculously trivial claim. You really need to take care with your
>>>>> language.
>>>>>
>>>>
>>>> You are a master of deception of avoiding the point:
>>>
>>> I am just pointing out you need to say what you mean. Having an x86
>>> emulator that aborts infinite loops and infinite recursion is trivial
>>> and (I hope) not what you think you have.
>>
>> Having an equivalent computation to the {Linz, Sipser} H correctly
>> deciding the Linz Ĥ, the Sipser D and the Kozen N is what I have.
>
> Which you will be (finally) posting today?
>

I just finished the programming of this.
I wanted to get it complete on the anniversary of its creation.

olcott

unread,
Dec 15, 2020, 7:23:59 PM12/15/20
to
On 12/15/2020 5:59 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 12/13/2020 7:14 AM, Ben Bacarisse wrote:
>>> Code for contex:
>>>
>>> bool Halts(u32 P, u32 I)
>>> {
>>> bool Halted = false;
>>> bool Aborted = false;
>>> while (!Halted && !Aborted)
>>> {
>>> Halted = DebugStep(P, I);
>>> Aborted = Needs_To_Be_Aborted();
>>> }
>>> return !Aborted;
>>>
>>> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>>>
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 12/12/2020 5:20 PM, Ben Bacarisse wrote:
> <cut>
>>>>> As far as my original point is concerned you have already said that Halts
>>>>> does not meet the challenge. You've agreed that
>>>>>
>>>>> (a) Halts(Confound_Halts, Confound_Halts) is false, and
>>>>> (b) Confound_Halts(Confound_Halts) is a finite computation.
>>>>
>>>> (b) Confound_Halts(Confound_Halts) IS NOT A FINITE COMPUTATION
>>>
>>> I am aware that you have said both. What you have not done is retract
>>> what you said before*, namely that the input to halts is a finite
>>> computation. You can't expect to get away with saying both, you need to
>>> say that you were wrong before.
>
> This is the first point that needs to be resolved. Were you wrong when
> you described the computation passed to Halts as finite? You qualified
> it -- "it's only finite because...", but I'd still be dead even if I were
> only dead because I jumped off a cliff.
>
> Anyway, it seems you are now adamant that, despite what you said before,
> Confound_Halts(Confound_Halts) is not a finite computation. There are
> only two ways that that can happen. Reminder:
>
> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>
> (1) Halts(Confound_Halts, Confound_Halts) returns true when called in
> the above function; or
>
> (2) Halts(Confound_Halts, Confound_Halts) does not return when called in
> the above function.
>
> Either way, Halts does not meet the specification given in the
> challenge.
>
>> The infinitely recursive invocation of Halts() by Confound_Halts()
>> never returns anything to Confound_Halts()
>
> OK that's excellently clear. Thank you. So Halts fails to meet the
> challenge because of (2) rather than (1)*. Do you want to have another
> go at meeting the challenge:
>
> Show a function F such that F(P, I) is true if, and only if, P(I) is a
> finite computation and false otherwise.
>
> Unless it is not obvious, these words mean that any candidate function
> must return in finite time no matter what arguments it is passed and
> regardless of the context of the call.
>
> * It occurs to me that you might think that a viable answer to this
> challenge might be a function that returns something in some contexts
> and does not return in others, even when given exactly the same
> arguments in both cases. I'm discounting that because it's obviously
> not allowed by the challenge wording, and you confirmed that no such
> trickery is taking place long ago in the reply to, IIRC, Mike Terry.
>

Here is the architecture that I am working on physically implementing in
the x86utm (x86 based universal Turing machine equivalent) operating
system.

Whenever a function is called by Halts() and it would not halt Halts()
returns 0. This is like wrapping a possible divide by zero error with a
try-catch block, the otherwise abnormal termination is caught.

// This part is fully operational
int main()
{
u32 Input_Halts = Halts((u32)Confound_Halts, (u32)Confound_Halts);
Output("Input_Halts = ", Input_Halts);
}

Whenever a function is not called by Halts() and it would not halt the
halt deciding operating system reports a "non-halting" error. This is
like divide by zero error that is NOT wrapped with a try-catch block,
the program abnormally terminates:

int main()
{
HERE: goto HERE;
}

int main()
{
Confound_Halts((u32)Confound_Halts);
}

This is the universal not-halting decision criteria:

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
> A computation that would not halt if its simulation were not
> halted is indeed a non-halting computation.

On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

The halting decision criteria is simply that the input has actually halted.

olcott

unread,
Dec 15, 2020, 8:46:32 PM12/15/20
to
(3) When Halts(Confound_Halts, Confound_Halts) is called by main() this
is similar to wrapping a divide by zero error with a try catch block.
Halts() returns a value of 0 or 1.

When Confound_Halts(Confound_Halts) is called by main() this is similar
to divide by zero error that has not been caught by a try-catch block.
The operating system abnormally terminates the application with an
[infinite execution] @ machine address fatal error.

>>> Either way, Halts does not meet the specification given in the
>>> challenge.
>>>
>>>> The infinitely recursive invocation of Halts() by Confound_Halts()
>>>> never returns anything to Confound_Halts()
>>>
>>> OK that's excellently clear. Thank you. So Halts fails to meet the
>>> challenge because of (2) rather than (1)*. Do you want to have another
>>> go at meeting the challenge:
>>>
>>> Show a function F such that F(P, I) is true if, and only if, P(I) is a
>>> finite computation and false otherwise.
>>>
>>> Unless it is not obvious, these words mean that any candidate function
>>> must return in finite time no matter what arguments it is passed and
>>> regardless of the context of the call.
>>>
>>> * It occurs to me that you might think that a viable answer to this
>>> challenge might be a function that returns something in some contexts
>>> and does not return in others, even when given exactly the same
>>> arguments in both cases. I'm discounting that because it's obviously
>>> not allowed by the challenge wording, and you confirmed that no such
>>> trickery is taking place long ago in the reply to, IIRC, Mike Terry.
>>>
>>
>> Here is the architecture that I am working on physically
>> implementing...
>
> I'm not interested in that. Can I take it that you agree you have not
> met the challenge? I'm sure everyone else will take your non-reply in
> that way but I'd rather you were explicit about it.
>

Your challenge was a false dichotomy as pointed out above.

olcott

unread,
Dec 16, 2020, 10:59:09 PM12/16/20
to
On 12/16/2020 7:48 AM, Malcolm McLean wrote:
> So this is reasonable. Everything is run under a supervisor which detects
> non-stopping behaviour and aborts. Halts catches the detection when
> called at top level. When not called at top level, the supervisor catches
> the detection.
>
> So it looks superficially as if Halts at top level is a pure function. That's as
> much as anyone sane would expect or demand. Halts can't be really a
> pure function because it changes its behaviour when called from Confound_
> Halts() . It must interact with the supervisor in some way. But that is quite well
> hidden, and the supervisor set-up sounds innocuous enough at first sight.After
> all, you need some framework for running Turing machines, and for stopping
> them when they get caught in infinite loops (or exceed the patience of
> the user).

The global Halts merely examines the execution trace of each and every
user specified x86 instruction that is executed by the x86utm operating
system.

Since the global Halts() is an intrinsic part of this operating system
its behavior is a function of the sequence of all of the simulated user
specified instructions. This would seem to make it a pure function of
its inputs.

Local Halts() is the same situation except that its scope is the
sequence of simulated user specified x86 instructions that it began the
invocation of.

> You haven't met Ben's challenge because of this

When Ben expects the infinite invocation of any function to return a
value to its caller Ben is nuts.

olcott

unread,
Dec 17, 2020, 10:08:08 AM12/17/20
to
On 12/17/2020 8:34 AM, Ben Bacarisse wrote:
> Richard Damon <Ric...@Damon-Family.org> writes:
>
>> On 12/16/20 11:28 PM, olcott wrote:
>>> On 12/16/2020 10:24 PM, Kaz Kylheku wrote:
>>>> On 2020-12-17, olcott <No...@NoWhere.com> wrote:
>>>>> On 12/16/2020 7:51 PM, Kaz Kylheku wrote:
>>>>>> If the progression is caused by an infinite recursion of a function
>>>>>> with the same paraemters, then all of the simulation levels are
>>>>>> indistinguishable. No UTM knows how many levels are above,
>>>>>> and each one has the same number of identical levels below.
>>>>>>
>>>>>> That's it.
>>>>>>
>>>>>
>>>>> If we allowed the infinite recursion to infinitely recur this would be
>>>>> true. We cut off the otherwise infinite recursion at three.
>>>>>
>>>>>> While it is possible to break that, by doing so you break the
>>>>>> premise that we have a pure function.
>>>>>>
>>>>>
>>>>> Halts() is a function of its inputs.
>>>>
>>>> Unfortunately "inputs" no longer refers to "those argument things
>>>> between the parentheses that we are painstakingly keeping the same".
>>>>
>>>
>>> I think that may be simply because you have a narrow minded view of
>>> inputs as some fixed sized set of objects.
>>>
>>> You are ruling out all dynamically generated inputs.
>>>
>>
>> He is talking about inputs in a functional programming sense. Which
>> include the formal arguments and any globals that the routine has access
>> to.
>
> So sad. Two years after having something we'd be "interested" in (in
> the sense of being impossible) it's come down a trick he's sworn up and
> down that he's not doing. You can't pretend that the same function does
> two things with a TM because H^ will contain a full copy of the decider,
> dodgy internal state and all. The key thing that has permitted this
> confusion (or possibly this deliberate deception) is to ignore
> representations.
>
> The halting problem is about whole computations, not fragments, and
> passing the whole computation encoded as a string makes that clear.
>
> And still there is claimed impossible code, because whatever code makes
> the "outer" assessment must get an infinite number of cases wrong. We
> won't get to see that, though. In fact, I doubt it even exists except
> for a couple of special cases.
>

All that I have to do to refute the {Linz, Sipser, and Kozen} proofs is
to show how Halts decides their {Ĥ, D, and N} counter examples as a
function of their sequence of instructions that Halts simulates. A
simulator has access to the sequence of instructions that it simulates.

A partial halt decider that correctly decides the counter-example basis
of the conventional halting problem proofs is sufficient to refute these
proofs.

olcott

unread,
Dec 19, 2020, 3:17:14 PM12/19/20
to
On 12/18/2020 6:13 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 12/17/2020 8:35 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 12/16/2020 6:25 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 12/15/2020 7:11 PM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 12/15/2020 5:59 PM, Ben Bacarisse wrote:
>>>>>>>>>
>>>>>>>>>> On 12/13/2020 7:14 AM, Ben Bacarisse wrote:
> Code for contex:
>
> bool Halts(u32 P, u32 I)
> {
> bool Halted = false;
> bool Aborted = false;
> while (!Halted && !Aborted)
> {
> Halted = DebugStep(P, I);
> Aborted = Needs_To_Be_Aborted();
> }
> return !Aborted;
>
> void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
>
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>> The infinitely recursive invocation of Halts() by Confound_Halts()
>>>>>>>>>> never returns anything to Confound_Halts()
>>>>>>>>>
>>>>>>>>> OK that's excellently clear.
>>>>>
>>>>> You are perfectly clear. Halts fails to meet the conditions set out in
>>>>> the challenge by not returning a value:
>>>>>
>>>>> Show a function F such that F(P, I) is true if, and only if, P(I) is a
>>>>> finite computation and false otherwise.
>>>>>
>>>>> Not returning a value, even if only in some contexts, makes it a fail.
> <cut>
>>
>> I just proved how it does perrectly meet its conditions.
>
> Don't be silly. The specification:
>
> Show a function F such that F(P, I) is true if, and only if, P(I) is a
> finite computation and false otherwise.
>
> requires that the function return a value, regardless of context.
>

This definition of a Halt decider seems to address your objections.
It turns out that in this case the innermost Halts() is the one that
makes the halt decision thus could return this same decision to its
outer invocations.

This seems to also address the objections of Kaz and Malcolm in that it
is a pure function of its inputs and does not require any global data.

bool Halts(u32 P, u32 I)
{
static u32* local_execution_trace_list;
bool Halted = false;
bool Aborted = false;
while (!Halted && !Aborted)
{
// EIP points to the next instruction to be simulated
PushBack(local_execution_trace_list, EIP);
Halted = DebugStep(P, I);
if (!Halted)
Aborted = Needs_To_Be_Aborted(local_execution_trace_list);
}
return !Aborted;

olcott

unread,
Dec 19, 2020, 6:40:31 PM12/19/20
to
On 12/19/2020 4:32 PM, Kaz Kylheku wrote:
> On 2020-12-19, olcott <No...@NoWhere.com> wrote:
>> The fact that Halts() does correctly return false for this input
>> void H_Hat(u32 P)
>> {
>> u32 Input_Halts = Halts(P, P);
>> if (Input_Halts)
>> HERE: goto HERE;
>> else
>> HALT
>> }
>> means that Halts() is a decider for this input.
>
> No, it means that Halts is not a pure function of two immutable
> arguments, but some kind of swindle.
>

bool Halts(u32 P, u32 I)
{
static u32* local_execution_trace_list;
bool Halted = false;
bool Aborted = false;
while (!Halted && !Aborted)
{
// EIP points to the next instruction to be simulated
PushBack(local_execution_trace_list, EIP);
Halted = DebugStep(P, I);
if (!Halted)
Aborted = Needs_To_Be_Aborted(local_execution_trace_list);
}
return !Aborted;
}

Purely functional programming consists of ensuring that functions,
inside the functional paradigm, will only depend on their arguments,
regardless of any global or local state.
https://en.wikipedia.org/wiki/Purely_functional_programming

I think that it would seem to be OK for it to dynamically construct an
internal state as the basis for returning its value as long as it would
always dynamically construct this internal state exactly the same way
for the exact same inputs.

In other words when there is a unique immutable mathematical mapping
from the inputs to the constructed internal state to the return value
then the function still corresponds to a mathematical function.

The portion that decides not-halting:
Aborted = Needs_To_Be_Aborted(local_execution_trace_list);
is a pure function of its inputs.

The portion that provides these inputs to the not-halting decider
requires keeping track of the sequence of instructions that it has
simulated.
0 new messages