(1) Halts() begins simulating H_Hat(H_Hat).
(2) Halts() maintains an execution trace of its simulation of H_Hat(H_Hat).
(3) Halts() examines the execution trace of its simulation of
H_Hat(H_Hat) immediately after it simulates each H_Hat(H_Hat) instruction.
(4) Halts() determines that H_Hat(H_Hat) would never terminate unless
Halts() stops simulating it.
(5) Halts() Terminates its simulation of H_Hat(H_Hat).
(6) Halts() Reports not halting for H_Hat(H_Hat).
(7) Halts() stops executing.
Its really not that hard.
On 3/16/2021 12:26 PM, Kaz Kylheku wrote:
On 2021-03-16, olcott <NoOne@NoWhere.com> wrote:
On 3/16/2021 8:45 AM, Kaz Kylheku wrote:
On 2021-03-15, olcott <NoOne@NoWhere.com> wrote:
On 3/15/2021 3:18 PM, Kaz Kylheku wrote:
When Test() is called with H_Hat as input this is not the
pathological
self-reference error. This does not derive infinite recursion.
I don't follow this at all, sorry. What I'm saying is that I expect >>>>>> these two to generate generate identical code, except for some
details of function address:
void Test(u32 P)
{
u32 Input_Halts = Halts(P, P);
...
void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
...
and I also mentioned that calls to either of these can be
completely inlined into main, so there is no difference.
The runaway recursion is detected inside Halts(P, P), is it not?
What happens if we call this from main:
Test((u32) Test);
That now has a "pathological" self-reference inside Test, right?
so that should now be aborted.
Yes I think that you "got it" now.
Ah, okay; we are back full tilt on that hapless global decider program. >>>>
Unfortunately, although having multiple modes caused communication
problems, the local mode is the one which is compatible with the
concept of a function and Turing machine.
You might remember the discussion from months ago about this; I
conceded
that local decider is a function because it isn't informed by global
state, only by instruction traces which it calculates itself.
At that time I wrote off the global mode as incorrect and
not worthy of further consideration.
To reiterate my position:
The global mode leaks information so that functions are no longer
pure computations based on just their arguments.
This is not the case when the global halt decider is a function of the
global UTM that is simulating every input. Its only input is the Turing
machine descriptions thus making its halting decision a function of
these finite strings. The UTM is an aspect of itself.
OK, if the enire program as a whole is the input to a global decider,
then whenever we produce different programs for different things---like
calling H_Hat directly, or calling some Tests function---those are
completely different inputs.
Those inputs look like compiled C programs which contain functions, but
that means nothing. Only the global decider is a function.
The entities inside the input like Halts or H_Hat are not functions.
Their behavior changes based on the exact configuration of the overall
input. E.g. sometimes Halts returns 0, and sometimes not, for apparently
the same input.
In that case, it's not clear what the global decider is exactly doing;
its results don't make any clear statement about H_Hat or Halts.
This adapted UTM would simply simulate the execution of its input until
its input halts on its own or its halt decider determines that its input would never halt on its own and stops simulating it. In order for the
UTM to see what its input does it must keep track of an execution trace
of its input. This UTM / halt decider is a pure function of its inputs.
That's what explains that Halts(P, P) can return in one situation
and be aborted in another. Its behavior is influenced by some global
information about events that have happened or not happened previously >>>> to its invocation.
Which the global UTM aspect of the global halt decider would have as a
part of its own internal state.
The problem is that the theory requires Halts(P, P) to be TM.
Halts(P, P) is just a fragment of a tape of some master TM, so loosely
to speak.
No it is operating system level functionality that is provided to its sub-processes (the simulated inputs) just like "C" printf must call the operating system for support.
If you present this to academia, you will get the same feedback, if
I have to make what I am proposing perfectly clear before I ever present >>> it to academia. They are not going to have the patience for endless
reviews.
things even get that far. If Halts(H_Hat, H_Hat) demonstrably returns 0 >>>> in one program run, that proves that H_Hat(H_Hat) cannot be infinitely >>>> recursive:
It <is> infinitely recursive and the halt decider would have decided
But it obviously isn't, when you yourself have a test case where
Halts(H_Hat, H_Hat) cheerfully returns 0.
On 3/14/2021 5:11 PM, Kaz Kylheku wrote:
On 2021-03-14, olcott <NoOne@NoWhere.com> wrote:
So you agree that an input program that only halts because the halt
decider stops simulating it <is> a non-halting computation?
If we are sure that the decision to stop it was correct (it is not actually a halting program that was prematurely stopped) we may
pronounce it non-halting.
You are requiring people (people who know what a function is) to accept
execution traces which show that Halts(H_Hat, H_Hat) terminates in
a finite number of steps, returning 0.
Then you're asking the same people to accept that H_Hat(H_Hat),
which calls Halts(H_Hat, H_Hat) and returns if that returns 0,
is infinitely recursive.
People that believe that computations that only halt because their
execution was aborted by the halt decider are halting computations can
simply be dismissed as incorrect.
For H_Hat(H_Hat) to recursive at all (let alone infinitely), it
cannot be the case that Halts(H_Hat, H_Hat) calculates zero in a finite
number of steps.
Sure it can, you already agreed to this.
On 3/14/2021 5:11 PM, Kaz Kylheku wrote:
On 2021-03-14, olcott <NoOne@NoWhere.com> wrote:
So you agree that an input program that only halts because the halt
decider stops simulating it <is> a non-halting computation?
If we are sure that the decision to stop it was correct (it is not actually a halting program that was prematurely stopped) we may
pronounce it non-halting.
So you're asking rational people to accept all three of these:
1. Halts is a computational function. Therefore
Halts(H_Hat, H_Hat) is Turing computation.
It either terminates, or doesn't; if it terminates,
it always terminates in the same state.
2. Halts(H_Hat, H_Hat) returns 0.
People that believe that computations that only halt because their
execution was aborted by the halt decider are halting computations can
simply be dismissed as incorrect.
3. Halts(H_Hat, H_Hat) doesn't return.
I never said this.
that if sneaky things were not being done behind its back. The
counter-example case that you and others cite is always a case of sneaky >>> things being done behind the halt decider's its back.
Nope; the thing is being done in the open: integrating the decider into
another function to create H_Hat.
None of these "sneaky things" do anything so cude as your own sneaky
things, namely destroy the concept of a function.
When people are only presented with a global halt decider based on
adapting a global UTM this issue will never occur to them.
it's obviously calling a function which calculates 0 in a
finite number of steps. So then if you turn around with a different
program run in which H_Hat is suddenly diagnosed as infinitely
recursive
because it calls Halts(H_Hat, H_Hat), that's a huge red flag that you
have something unsavory going on. Questions will be asked.
People that believe that computations that only halt because their
execution was aborted by the halt decider are halting computations can
simply be dismissed as incorrect.
I specifically don't believe that though; I believe that when your
decider says "simulation halted due to runaway recursion" or whatever,
a runaway recursion was intercepted. I take that at face value.
Likewise, when Halts(P, P) returns 0, I take that to be a real halting
computation.
The problem is you have gamed things so that the same code (which is
supposed to be a function whose behavior depends only on its arguments)
is sometimes runaway recursive and sometimes isn't.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 293 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 211:15:25 |
| Calls: | 6,619 |
| Calls today: | 1 |
| Files: | 12,168 |
| Messages: | 5,317,308 |