XPost: comp.theory, sci.logic, sci.math
On 9/5/2021 5:37 PM, Mike wrote:
On 05/09/2021 22:36, Richard Damon wrote:
On 9/5/21 4:13 PM, olcott wrote:
On 9/5/2021 3:02 PM, Malcolm McLean wrote:
On Sunday, 5 September 2021 at 04:55:50 UTC+1, olcott wrote:
On 9/4/2021 6:25 PM, Malcolm McLean wrote:
On Saturday, 4 September 2021 at 23:54:50 UTC+1, olcott wrote:
On 9/4/2021 5:41 PM, Richard Damon wrote:
When int main() { H1(P,P); } returns a different value than
int main() { H(P,P); } we know that (P,P) is a pathological input. >>>>>>>>
You may want to call it that, but it is still a LEGAL input, that H >>>>>>>> needs to get right and be a Computation for.
None-the-less I just refuted Rice's theorem.
H and H1 are different machines? Or is H1 the same machine as H but >>>>>> run under a simulating halt decider?
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H1((u32)P, (u32)P));
}
H1 is identical to H.
H1 simulates P(P) that calls H(P,P)
H simulates P(P) that calls H(P,P)
This creates a dependency relationship between H1 and H that does not >>>>> exist in reverse.
Either way, the idea is that we have two machines / set ups and we >>>>>> run
the input <P><P> on both. If the results coincide, then obviously
that
is the halting status of P<P>. If they differ, then we've identified >>>>>> "pathological input". That is an "interesting characteristic" of a >>>>>> Turing
machine so Rice's theorem falls.
Nice try. Unfortunately it's not so easy.
int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
Output("Input_Halts = ", H1((u32)P, (u32)P));
}
Input_Halts = 0
Input_Halts = 1
So all Ps are identical, and H and H1 have identical code, but
different
names and different machine addresses.
We know that H/H1 looks for address on the call stack to detect runaway >>>> recursion. The best explanation I can think of for these results is
that H/H1
uses its own address as the initial call to examine. Therefore
behaviour can
diverge.
Am I correct?
The most that I boiled it down to so far is the master slave
relationship between H1 and H.
The master UTM / halt decider H1 can see everything that it simulates:
(a) P begins
(b) P calls H(P,P)
(c) H returns to P
(d) P returns to main() where it was simulated by H1.
The master UTM / halt decider H can see everything that it simulates:
(a) P begins
(b) P calls H(P,P)
(c) P begins
(e) P calls H(P,P)
Then H(P,P) aborts its simulation of its input.
Neither P nor H can see H1 at all.
But since both are looking at the Machine P(P), why do they see
different execution traces.
I'd guess:
- when H1 is the halt decider, trace entries for H1 are hidden, but
trace entries within H are visible. So the trace shows all sorts of conditional branches etc. in H and so H1 correctly doesn't decide
"infinite recursion".
Not exactly. Every halt decider can see each user-instruction that it simulates. When it recursively simulates itself is ignores all operating
system code including itself for two reasons:
(1) It knows that all operating system code halts
(2) It can ignore its own behavior because it knows that while it
remains in pure simulation mode it can have no effect on the behavior of
the code that it is simulating. This last part seems to be beyond
Richard's intellectual capacity.
- when H is the halt decider, trace entries for H are hidden. So the trace doesn't show all the conditional branches, causing PO's "infinite recursion" test to match, and so H incorrectly decides "non halting", aborting the emulation earlier than in the previous H1 scenario.
Pathological Input to a halt decider is stipulated to mean any input
that was defined to do the opposite of whatever its corresponding halt
decider decides as Sipser describes:
Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to M
is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)
I already explained this.
When the halt decider makes sure to have no effect on the behavior of
otherwise pathological inputs that it simulates it can ignore its own
behavior in its halt status decision. When it can ignore its own
behavior in its halt status decision the "pathological" aspect of the pathological input has been removed.
If so, it's kind of funny that the H1 scenario is what you and everybody
else have been telling PO for a year - if the emulation P(P) IS ALLOWED
TO CONTINUE NATURALLY, IT TERMINATES.
int main { H1(P,P) } correctly decides that its input halts entirely on
the basis that H(P,P) called from P correctly decides that its input
never halts.
Well, that's just a guess. You'd think PO would /know/ the answer, as
it's his code! But his wording above "..The most that I boiled it down
to so far is..." suggests he's still trying to figure it out!
Mike.
That means that P isn't a computation, and due to how it is built, that
means that H has to not be a computation, since P doesn't do anything
outside of its copy of H to make it not a Computation.
If H isn't a Computation, it isn't qualifited to be a Decider.
You just proved that YOU FAIL.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)