Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Unix will self-destruct in five seconds... 4... 3... 2... 1...

programming / comp.lang.asm.x86 / Re: Refuting the {Linz, Sipser and Kozen} HP Proofs (deciders within

Subject: Re: Refuting the {Linz, Sipser and Kozen} HP Proofs (deciders within
From: olcott
Newsgroups: comp.theory,, comp.lang.asm.x86
Organization: A noiseless patient Spider
Date: Mon, 14 Dec 2020 21:56 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
From: (olcott)
Newsgroups: comp.theory,,comp.lang.asm.x86
Subject: Re: Refuting the {Linz, Sipser and Kozen} HP Proofs (deciders within
Date: Mon, 14 Dec 2020 15:56:55 -0600
Organization: A noiseless patient Spider
Lines: 347
Approved: - comp.lang.asm.x86 moderation team.
Message-ID: <>
References: <>
<rr2j08$4ur$> <>
<rr2oq2$ao3$> <>
<rr2tlk$c32$> <>
<rr2vb1$mhs$> <>
<rr30u4$2ba$> <>
<rr340r$l9i$> <>
<rr34ok$rof$> <>
<rr36c2$7dk$> <>
<rr39me$tev$> <>
<rr7tvl$h7a$> <>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info:; posting-host="7f19e0d1116082fd360d82ac1fedadb4";
logging-data="28288"; mail-complaints-to=""; posting-account="U2FsdGVkX1+G1G05Vd9k4rkQ5B6nAWyjY8bp83+m4qg="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Cancel-Lock: sha1:TaFvV8RB28V3YgqOz97nFSADf6E=
View all headers
On 12/14/2020 2:02 PM, Kaz Kylheku wrote:
On 2020-12-14, olcott <> wrote:
On 12/14/2020 9:32 AM, Malcolm McLean wrote:
On Monday, 14 December 2020 at 15:16:13 UTC, olcott wrote:
On 12/14/2020 8:48 AM, André G. Isaak wrote:
On 2020-12-14 07:25, olcott wrote:
On 12/12/2020 2:37 PM, André G. Isaak wrote:
On 2020-12-12 13:01, olcott wrote:
On 12/12/2020 1:40 PM, André G. Isaak wrote:
On 2020-12-12 12:25, olcott wrote:
On 12/12/2020 1:13 PM, André G. Isaak wrote:
On 2020-12-12 12:08, olcott wrote:
On 12/12/2020 1:00 PM, André G. Isaak wrote:
On 2020-12-12 11:26, olcott wrote:
On 12/12/2020 12:08 PM, André G. Isaak wrote:
On 2020-12-12 10:45, olcott wrote:
On 12/12/2020 11:40 AM, André G. Isaak wrote:
On 2020-12-12 10:38, olcott wrote:
On 12/12/2020 11:12 AM, André G. Isaak wrote:
On 2020-12-12 09:24, olcott wrote:


The outermost Halts() always returns a value to its
caller even though it must sometimes abort the
simulations of inner infinite invocations of itself.

And since it claims to be simulating those inner
instances and to abort those instances only in cases
where they would not otherwise halt, it is asserting that
there *are* inputs to Halts() which will not halt. Ergo,
it is asserting that Halts() is *not* a decider. those cases where it does not halt and return a
value to its caller Halts() is not a decider. On those
invocations of Halts() where it does halt and return a
value to its caller it is a decider.

A program is either a decider or it isn't. There's no such
thing as a program which is sometimes a decider and
sometimes isn't.


You already know that is pure bullshit or the term "partial
decider" would not exist. What motive do you have for saying
things that you know are pure bullshit?

A partial decider is not a decider. More importantly, it is
not a "sometimes decider".

A partial decider makes a correct decision for a particular
class of inputs but may fail to halt for other inputs.

Your program sometimes halts and sometimes doesn't for the
*same* inputs. So you cannot even claim your program is a
partial decider, let alone an actual decider.


So in other words you "believe" against logic that some
infinitely recursive invocations <do> return a result to their
caller. That sounds nutty to me.

How you can possibly get that idea from what I wrote is utterly
beyond me.

I am saying that anything which has the possibility of getting
caught in infinite recursion cannot return a result and
therefore cannot constitute a decider.


Except in those cases that it has not been caught in infinite
recursion and does return a result to its caller.

Alternatively a function that can and does correctly detect
infinite recursion on itself and return its decision to its
caller does not count.

Basically you are saying that it is wrong all of the time even
though it is right some of the time.

No. I am saying that it is not a decider. A decider *must* return
a result for *all* inputs. That's the definition of 'decider'.
Something that only returns results in some instances is not a
decider. I don't know how I can make this any clearer...


The way that you are defining it when a function does correctly
decide that it has been infinitely invoked that even though this
decision is correct it does not count.

Since a partial decider <is> a decider for some inputs and not for
other inputs, then this same idea can be extended to some
invocations and not all invocations, otherwise correctly deciding
infinite recursion does not count even when the decision is correct.

A partial decider is not a decider any more than a half-dollar is a
dollar. A partial decider is something that correctly decides some
cases, not something which is a decider in some cases. Things are
either deciders or they aren't.

A partial decider that decides the {Linz, Sipser, Kozen}
counter-examples refutes these three proofs.

That a program correctly decides some cases does not make it a
decider in those cases. You could call it a partial decider, but
not a decider.

However, in the case of your program, you can't even call it that
because it sometimes returns and other times does not return *on
the same input*. A partial decider is something which decides some
set of inputs and fails to decide another, *disjoint* set of
inputs. Something which gets different results for the same input
isn't even a function, let alone a decider or partial decider.


So in other words when a partial decider correctly determines that
it has been invoked in infinite recursion it must fix the bug in
this infinitely recursive invocation so that it can report its
infinitely recursive invocation to its infinitely recursive caller,
that is no longer infinitely recursive because it fixed this bug.

That makes perfect sense to me.

No, I did not say that. You need to make at least some effort to read
for comprehension. I said that something which can be caught in
infinite recursion is *not* a decider. This is getting rather
tedious. Something that correctly decides some cases but not others
could be a partial decider, but not if it decides the *same* input in
some cases but not others.

01 void H_Hat(u32 P)
02 {
03 u32 Input_Halts = DebugTrace(P, P);
04 if (Input_Halts)
05 HERE: goto HERE;
06 else
08 }

Halts((u32)H_Hat,(u32)H_Hat) is correctly decided** as not halting
because it aborts the invocation of itself on line 03.

You've switched back from using Halts() to using DebugTrace(). Are these
intended to be distinct functions?

** Halts returns the correct halting determination.

According to your way of defining a decider:
(a) Halts is not a decider even though it correctly decides.
(b) Halts would be a decider if it aborted the infinite recursion of
any other function besides itself.

That is ridiculous!
Look, a decider is a type of *function*. To be a function, something
must consistently map the same input to the same result, but that isn't
what you get above. Assuming that your DebugTrace() and Halts() are
intended to be the same, you are claiming that

Halts(H_Hat, H_Hat)

returns false. This means Halts(H_Hat, H_Hat) is a finite computation.

But by returning false is is also claiming that the instance of
Halts(H_Hat, H_Hat) invoked from within H_Hat must be aborted as a
non-halting function.

This is a contradiction.
As I have said very many times (no one notices because they only glance
at a few of my words to contrive some lame basis for a rebuttal that
would fool the gullible):

Halts(H_Hat, H_Hat) is only a finite computation because it aborts the
otherwise infinite recursion of its input 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.

If Halts aborts itself, is it halted or aborted? That's the question.

Halts() simulates H_Hat() that invokes Halts() in infinite recursion.
Halts() stops simulating H_Hat() including its infinite recursive
invocation of Halts(), returning its non-halting decision to main()
where it is output.

If we say "halted" then H_Hat inverts whatever result it returns,

It is not possible for an aborted function to invert any damn thing.

and :Halts" is wrong. If we say "aborted" then "Halts" isn't a function,
which is a slightly more subtle requirement of H_Hat.

Certainly an at least partial halt decider that bases its halting
decision by looking for patterns of behavior of its inputs can stop
simulating this input as soon as it detects any non-halting pattern.

It does not make any damn difference if it detects an infinite loop, or
infinite recursion. It also does not make any damn difference which
function is involved in infinite recursion. As long as Halts() detects
the non-halting behavior of its input then it can stop simulating this
input and report non-halting.

void H_Hat(u32 P)
    u32 Input_Halts = Halts(P, P);
    if (Input_Halts)
      HERE: goto HERE;

int main()
    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
    Output("[Input_Would_Halt] =", Input_Would_Halt);

I finally renamed my internal DebugTrace() to Halts() now that it
finally does return its correct halting decision to main().

Your techique is suspicious, because you're transcribing the pseudo-code
from the usual halting proofs into the higher level C language, but then
are messing with the execution at a lower level. The mapping between the
C language and abstract concepts like "pure function of certain
arguments" only depends on certain conventions being upheld in the
machine language translation, and the expected execution model for which
the translation is made.

At the TM level is is merely the execution of a TM on a finite string, in this case the TM a a halt decider based on a UTM.

It is not the details of the C/x86 implementation that are important it is whether or not the architecture of the C/x86 implementation maps to a TM solution.

Halts is not a pure function, or else not a pure function of the
two arguments that are visible at the C source code level.

We need the mapping to the x86 level so that we have a complete di-graph graph of all control flow, the C level does not provide this.

I have a similar C program for GNU/Linux which doesn't require any
complicated virtual machine. In my program, I reveal everything I'm

My program calls H_Hat(H_Hat), showing that it halts, and then
it shows that Halts(H_Hat, H_Hat) decides correctly:

   $ ./fakehalt
   Got here so H_Hat(H_Hat) halted!
   H_Hat(H_Hat) halts!

Source of fakehalt.c follows. Note that Halts does not rely on any
mutating global state or anything. The subterfuge is that because
Halts uses debugging introspection to inspect the machine state, it is
not simply a function of the declared arguments.  My Halts is a function
of the entire call stack, and using that call stack it can tell that
it's being called directly from main, with no H_Hat involved.

I don't currently need to look at the stack. I merely examine the complete sequence of every x86 instruction that has been executed in user code.

In any case it does not matter what the Hell that I do as long as there are no inputs that are provably undecidable.

You must be perpetrating the moral equivalent of this trick in your
code. This will be easily shown when you reveal all the end-to-end
processing details.

#include <stdio.h>
#include <execinfo.h>

typedef void (*fun_t)(void *data);
typedef int (*decider_t)(fun_t, void *data);

int Halts(fun_t, void *);

void H_Hat(void *data)
   if (Halts((fun_t) data, data)) {
     for (;;)
   } else {

int Halts(fun_t fun, void *data)
   void *buffer[10];
   int i, ncallers = backtrace(buffer, 10);

   (void) fun;
   (void) data;

   for (i = 0; i < ncallers; i++)
     if (buffer[i] >= (void *) H_Hat && buffer[i] < (void *) Halts)
       return 0;

   return 1;

int main(void)
   H_Hat((void *) H_Hat);

   puts("Got here so H_Hat(H_Hat) halted!");

   if (Halts(H_Hat, (void *) H_Hat))
     puts("H_Hat(H_Hat) halts!");
     puts("H_Hat(H_Hat) doesn't halt!");

   return 0;

Copyright 2020 Pete Olcott

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

o Re: Refuting the {Linz, Sipser and Kozen} HP Proofs (deciders within

By: olcott on Mon, 14 Dec 2020

rocksolid light 0.7.2