Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
It is known that a correct halt decider must return false (in this case)[V3]
11 views
Skip to first unread message
olcott
Nov 21, 2020, 7:03:19 PM11/21/20
to
(1) It is known that the UTM simulation of a machine's Turing machine
description is equivalent to directly executing it.
01 void H_Hat(u32 P)
02 {
03 if (Halts(P, P))
04 HERE: goto HERE;
05 else
06 HALT
07 }
08 bool Halts(u32 P, u32 I)
09 {
10 bool Halted = false;
11 bool Aborted = false;
12 while (!Halted && !Aborted)
13 {
14 Halted = DebugStep(P, I);
15 Aborted = Needs_To_Be_Aborted();
16 }
17 return !Aborted;
18 }
19 int main()
20 {
21 u32 P = (u32)H_Hat;
22 Halts(P, P);
23 HALT;
24 }
(2) It is known that the above code is infinitely recursive if Halts()
acts like a UTM (by having its line 15 disabled) and simulates its input
returning true if and only if its input halts.
(3) On the basis of (1) and (2) It is known that a correct halt decider
for H_Hat (without line 15 disabled) must return false.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
description is equivalent to directly executing it.
01 void H_Hat(u32 P)
02 {
03 if (Halts(P, P))
04 HERE: goto HERE;
05 else
06 HALT
07 }
08 bool Halts(u32 P, u32 I)
09 {
10 bool Halted = false;
11 bool Aborted = false;
12 while (!Halted && !Aborted)
13 {
14 Halted = DebugStep(P, I);
15 Aborted = Needs_To_Be_Aborted();
16 }
17 return !Aborted;
18 }
19 int main()
20 {
21 u32 P = (u32)H_Hat;
22 Halts(P, P);
23 HALT;
24 }
(2) It is known that the above code is infinitely recursive if Halts()
acts like a UTM (by having its line 15 disabled) and simulates its input
returning true if and only if its input halts.
(3) On the basis of (1) and (2) It is known that a correct halt decider
for H_Hat (without line 15 disabled) must return false.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
Mr Flibble
Nov 21, 2020, 7:49:15 PM11/21/20
to
/Flibble
--
¬
0 new messages