olcott
2020-12-14 21:56:55 UTC
<snip>
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.
...in 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.
André
You already know that is pure bullshit or the term "partialThe 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 innercaller even though it must sometimes abort the
simulations of inner infinite invocations of itself.
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.
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.
thing as a program which is sometimes a decider and
sometimes isn't.
André
decider" would not exist. What motive do you have for saying
things that you know are pure bullshit?
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.
André
infinitely recursive invocations <do> return a result to their
caller. That sounds nutty to me.
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.
André
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.
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...
André
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.
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.
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.
André
So in other words when a partial decider correctly determines thatdecider 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.
André
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.
<sarcasm>
That makes perfect sense to me.
</sarcasm>
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.
02 {
03 u32 Input_Halts = DebugTrace(P, P);
04 if (Input_Halts)
05 HERE: goto HERE;
06 else
07 HALT
08 }
Halts((u32)H_Hat,(u32)H_Hat) is correctly decided** as not halting
because it aborts the invocation of itself on line 03.
intended to be distinct functions?
** Halts returns the correct halting determination.
(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(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!
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.
at a few of my words to contrive some lame basis for a rebuttal that
Halts(H_Hat, H_Hat) is only a finite computation because it aborts the
A computation that would not halt if its simulation were not
halted is indeed a non-halting computation.
halted is indeed a non-halting computation.
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 haltingwhich is a slightly more subtle requirement of H_Hat.
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;
else
HALT
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("[Input_Would_Halt] =", Input_Would_Halt);
HALT;
}
I finally renamed my internal DebugTrace() to Halts() now that it
finally does return its correct halting decision to main().
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.
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-graphtwo arguments that are visible at the C source code level.
graph of all control flow, the C level does not provide this.
https://en.wikipedia.org/wiki/Directed_graph
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
doing.
My program calls H_Hat(H_Hat), showing that it halts, and then
$ ./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 thecomplicated virtual machine. In my program, I reveal everything I'm
doing.
My program calls H_Hat(H_Hat), showing that it halts, and then
$ ./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.
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 (;;)
fflush(stdout);
} else {
return;
}
}
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!");
else
puts("H_Hat(H_Hat) doesn't halt!");
return 0;
}
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 (;;)
fflush(stdout);
} else {
return;
}
}
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!");
else
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
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein