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