Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #35634 > unrolled thread

Could H correctly decide that P never halts?

Back to article view | Back to comp.theory

Contents

  Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 10:19 -0500
    Re: Could H correctly decide that P never halts? wij <wyniijj@gmail.com> - 2021-07-03 08:25 -0700
      Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 10:32 -0500
        Re: Could H correctly decide that P never halts? Richard Damon <Richard@Damon-Family.org> - 2021-07-03 11:56 -0400
          Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 11:19 -0500
            Re: Could H correctly decide that P never halts? Bonita Montero <Bonita.Montero@gmail.com> - 2021-07-03 18:28 +0200
              Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 11:51 -0500
                Re: Could H correctly decide that P never halts? Bonita Montero <Bonita.Montero@gmail.com> - 2021-07-03 19:18 +0200
                  Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 12:19 -0500
                    Re: Could H correctly decide that P never halts? Bonita Montero <Bonita.Montero@gmail.com> - 2021-07-03 19:33 +0200
            Re: Could H correctly decide that P never halts? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-03 19:10 +0100
              Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 13:49 -0500
            Re: Could H correctly decide that P never halts? Richard Damon <Richard@Damon-Family.org> - 2021-07-03 14:29 -0400
    Re: Could H correctly decide that P never halts? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-03 17:25 +0100
      Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 11:49 -0500
        Re: Could H correctly decide that P never halts? Richard Damon <Richard@Damon-Family.org> - 2021-07-03 14:17 -0400
          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ] olcott <NoOne@NoWhere.com> - 2021-07-03 14:08 -0500
            Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-03 15:43 -0400
              Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 15:37 -0500
                Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-03 17:58 -0400
                  Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 17:20 -0500
                    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-03 18:55 -0400
                    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Mr Flibble <flibble@reddwarf.jmc> - 2021-07-03 23:57 +0100
                      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 18:13 -0500
                    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-03 19:04 -0400
                      Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 18:34 -0500
                        Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] Richard Damon <Richard@Damon-Family.org> - 2021-07-03 20:06 -0400
                          Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 19:26 -0500
                            Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] Richard Damon <Richard@Damon-Family.org> - 2021-07-03 21:21 -0400
                              Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 20:41 -0500
                                Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] Richard Damon <Richard@Damon-Family.org> - 2021-07-03 22:13 -0400
                                  Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 21:22 -0500
                                    Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] Richard Damon <Richard@Damon-Family.org> - 2021-07-03 23:24 -0400
                                      Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-03 22:32 -0500
                                        Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] Richard Damon <Richard@Damon-Family.org> - 2021-07-04 06:40 -0400
                                          Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] olcott <NoOne@NoWhere.com> - 2021-07-04 09:24 -0500
                                            Re: Could H correctly decide that P never halts? [ prerequisites to understanding me] Richard Damon <Richard@Damon-Family.org> - 2021-07-04 14:50 -0400
                Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) André G. Isaak <agisaak@gm.invalid> - 2021-07-03 19:14 -0600
                  Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 20:38 -0500
                    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) André G. Isaak <agisaak@gm.invalid> - 2021-07-03 22:14 -0600
                      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) André G. Isaak <agisaak@gm.invalid> - 2021-07-03 22:18 -0600
                      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-03 23:18 -0500
                        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) André G. Isaak <agisaak@gm.invalid> - 2021-07-04 00:50 -0600
                          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 09:15 -0500
                            Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) André G. Isaak <agisaak@gm.invalid> - 2021-07-04 10:31 -0600
                              Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 08:07 -0500
                            Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-04 11:24 -0700
                              Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) André G. Isaak <agisaak@gm.invalid> - 2021-07-04 13:00 -0600
                                Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 15:09 -0500
                                  Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-04 13:30 -0700
                                    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 08:23 -0500
                                      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-05 07:18 -0700
                                        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 09:31 -0500
                                          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 11:10 -0400
                                            Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 10:18 -0500
                                              Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 11:29 -0400
                                              Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 12:53 -0400
                                                Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 12:13 -0500
                                  Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) André G. Isaak <agisaak@gm.invalid> - 2021-07-04 14:55 -0600
                                    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) "dklei...@gmail.com" <dkleinecke@gmail.com> - 2021-07-04 18:03 -0700
                                      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 20:42 -0500
                                        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-04 22:31 -0400
                                        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 08:05 -0400
                                          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 08:40 -0500
                                            Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 12:13 -0400
                                      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Jeff Barnett <jbb@notatt.com> - 2021-07-04 23:20 -0600
                                        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-05 18:49 +0100
                                          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Jeff Barnett <jbb@notatt.com> - 2021-07-05 15:17 -0600
                                          Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-05 17:38 -0500
                                    Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-04 23:52 -0500
                                      Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 10:36 -0400
                                        Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 09:51 -0500
                                          Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 11:36 -0400
                              Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) olcott <NoOne@NoWhere.com> - 2021-07-05 08:18 -0500
                                Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 12:11 -0400
                            Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard) Richard Damon <Richard@Damon-Family.org> - 2021-07-04 15:02 -0400
        Re: Could H correctly decide that P never halts? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-03 21:20 +0100
          Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 16:21 -0500
            Re: Could H correctly decide that P never halts? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-04 01:23 +0100
              Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-03 19:30 -0500
                Re: Could H correctly decide that P never halts? [ already agreed ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-04 17:46 +0100
                  Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 12:00 -0500
                    Re: Could H correctly decide that P never halts? [ already agreed ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-05 02:04 +0100
                  Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 20:57 -0500
                    Re: Could H correctly decide that P never halts? [ already agreed ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-05 03:14 +0100
                      Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 21:28 -0500
                        Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-04 22:33 -0400
                        Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-04 22:09 -0500
                          Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 07:33 -0400
                            Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 08:38 -0500
                              Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 10:57 -0400
                                Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 09:59 -0500
                                  Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 11:34 -0400
                                  Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 13:16 -0400
                                    Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 12:48 -0500
                                      Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 14:36 -0400
                              Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 12:18 -0400
                        Re: Could H correctly decide that P never halts? [ already agreed ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-05 23:58 +0100
                          Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 19:54 -0500
                            Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 21:29 -0400
                            Re: Could H correctly decide that P never halts? [ already agreed ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-06 03:35 +0100
                              Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 22:30 -0500
                                Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-06 06:47 -0400
                                  Re: Could H correctly decide that P never halts? [ already agreed ] Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-06 04:15 -0700
                                Re: Could H correctly decide that P never halts? [ already agreed ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-06 13:23 +0100
                    Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 07:21 -0400
                      Re: Could H correctly decide that P never halts? [ halting criteria ] olcott <NoOne@NoWhere.com> - 2021-07-05 08:26 -0500
                        Re: Could H correctly decide that P never halts? [ halting criteria ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 10:50 -0400
                          Re: Could H correctly decide that P never halts? [ halting criteria ] olcott <NoOne@NoWhere.com> - 2021-07-05 09:56 -0500
                    Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 10:30 -0400
                      Re: Could H correctly decide that P never halts? [ already agreed ] olcott <NoOne@NoWhere.com> - 2021-07-05 09:33 -0500
                        Re: Could H correctly decide that P never halts? [ already agreed ] Richard Damon <Richard@Damon-Family.org> - 2021-07-05 11:02 -0400
                      Re: Could H correctly decide that P never halts? [ already agreed ] (correction) olcott <NoOne@NoWhere.com> - 2021-07-05 09:35 -0500
                        Re: Could H correctly decide that P never halts? [ already agreed ] (correction) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 12:38 -0400
                          Re: Could H correctly decide that P never halts? [ already agreed ] (correction) olcott <NoOne@NoWhere.com> - 2021-07-05 12:10 -0500
                            Re: Could H correctly decide that P never halts? [ already agreed ] (correction) Richard Damon <Richard@Damon-Family.org> - 2021-07-05 13:43 -0400
                          Re: Could H correctly decide that P never halts? [ Richard's excellent summation ] olcott <NoOne@NoWhere.com> - 2021-07-05 19:12 -0500
    Re: Could H correctly decide that P never halts? Siri Cruise <chine.bleu@yahoo.com> - 2021-07-03 11:01 -0700
      Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 13:15 -0500
        Re: Could H correctly decide that P never halts? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-03 21:09 +0100
          Re: Could H correctly decide that P never halts? [ incorrect question ] olcott <NoOne@NoWhere.com> - 2021-07-03 16:06 -0500
            Re: Could H correctly decide that P never halts? [ incorrect question ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-04 01:44 +0100
              Re: Could H correctly decide that P never halts? [ incorrect question ] olcott <NoOne@NoWhere.com> - 2021-07-03 19:59 -0500
                Re: Could H correctly decide that P never halts? [ incorrect question ] Mr Flibble <flibble@reddwarf.jmc> - 2021-07-04 02:34 +0100
                  Re: Could H correctly decide that P never halts? [ incorrect question ] olcott <NoOne@NoWhere.com> - 2021-07-03 20:46 -0500
                Re: Could H correctly decide that P never halts? [ incorrect question ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-04 17:45 +0100
      Re: Could H correctly decide that P never halts? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-03 19:15 +0100
        Re: Could H correctly decide that P never halts? olcott <NoOne@NoWhere.com> - 2021-07-03 13:58 -0500
      Re: Could H correctly decide that P never halts? Siri Cruise <chine.bleu@yahoo.com> - 2021-07-03 22:37 -0700
        Re: Could H correctly decide that P never halts? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-04 14:14 +0100

Page 1 of 7  [1] 2 3 4 5 6 7  Next page →

#35634 — Could H correctly decide that P never halts?

*Halting problem undecidability and infinitely nested simulation*
When the halt decider bases its halt status decision simulating its 
input then the conventional halting problem proof undecidability 
counter-example templates can be correctly decided as inputs that never 
halt. They will never halt because they specify infinitely nested 
simulation to any simulating halt decider.

Because a simulating halt decider must always abort the simulation of 
every input that never halts its halt deciding criteria must be adapted. 
[ Does the input halt on its input? ] must become [ Does the input halt 
without having its simulation aborted? ] This change is required because 
every input to a simulating halt decider either halts on its own or 
halts because its simulation has been aborted.

The standard pseudo-code halting problem template "proved" that the 
halting problem could never be solved on the basis that neither value of 
true (halting) nor false (not halting) could be correctly returned to 
the confounding input.

     // Simplified Linz Ĥ (Linz:1990:319)
     void P(u32 x)
     {
       u32 Input_Halts = H(x, x);
       if (Input_Halts)
         HERE: goto HERE;
     }

     int main()
     {
       u32 Input_Halts = H((u32)P, (u32)P);
       Output("Input_Halts = ", Input_Halts);
     }

This problem is overcome on the basis that a simulating halt decider 
would abort the  simulation of its input before ever returning any value 
to this input. It aborts the simulation of its input on the basis that 
its input specifies what is essentially infinite recursion (infinitely 
nested simulation) to any simulating halt decider.

The x86utm operating system was created so that the halting problem 
could be examined concretely in the high level language of C and x86. 
When examining the halting problem this way every detail can be 
explicitly specified. UTM tape elements are 32-bit unsigned integers.

H analyzes the (currently updated) stored execution trace of its x86 
emulation of P(P) after it simulates each instruction of input (P, P). 
As soon as a non-halting behavior pattern is matched H aborts the 
simulation of its input and decides that its input does not halt.

*This is the sound deductive inference (proof) that H(P,P)==0 is correct*

Premise(1) (axiom) Every computation that never halts unless its 
simulation is aborted is a computation that never halts. This verified 
as true on the basis of the meaning of its words.

Premise(2) (verified fact) The simulation of the input to H(P,P) never 
halts without being aborted is a verified fact on the basis of its x86 
execution trace. (shown below).

When the simulator determines whether or not it must abort the 
simulation of its input based on the behavior of its input the simulator 
only acts as an x86 emulator thus has no effect on the behavior of its 
input. This allows the simulator to always ignore its own behavior.

Conclusion(3) From the above true premises it necessarily follows that 
simulating halt decider H correctly reports that its input: (P,P) never 
halts.




Halting problem undecidability and infinitely nested simulation 
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [next] | [standalone]

#35635

On Saturday, 3 July 2021 at 23:19:16 UTC+8, olcott wrote:
> *Halting problem undecidability and infinitely nested simulation* 
> When the halt decider bases its halt status decision simulating its 
> input then the conventional halting problem proof undecidability 
> counter-example templates can be correctly decided as inputs that never 
> halt. They will never halt because they specify infinitely nested 
> simulation to any simulating halt decider. 
> 
> Because a simulating halt decider must always abort the simulation of 
> every input that never halts its halt deciding criteria must be adapted. 
> [ Does the input halt on its input? ] must become [ Does the input halt 
> without having its simulation aborted? ] This change is required because 
> every input to a simulating halt decider either halts on its own or 
> halts because its simulation has been aborted. 
> 
> The standard pseudo-code halting problem template "proved" that the 
> halting problem could never be solved on the basis that neither value of 
> true (halting) nor false (not halting) could be correctly returned to 
> the confounding input. 
> 
> // Simplified Linz Ĥ (Linz:1990:319) 
> void P(u32 x) 
> { 
> u32 Input_Halts = H(x, x); 
> if (Input_Halts) 
> HERE: goto HERE; 
> } 
> 
> int main() 
> { 
> u32 Input_Halts = H((u32)P, (u32)P); 
> Output("Input_Halts = ", Input_Halts); 
> } 
> 
> This problem is overcome on the basis that a simulating halt decider 
> would abort the simulation of its input before ever returning any value 
> to this input. It aborts the simulation of its input on the basis that 
> its input specifies what is essentially infinite recursion (infinitely 
> nested simulation) to any simulating halt decider. 
> 
> The x86utm operating system was created so that the halting problem 
> could be examined concretely in the high level language of C and x86. 
> When examining the halting problem this way every detail can be 
> explicitly specified. UTM tape elements are 32-bit unsigned integers. 
> 
> H analyzes the (currently updated) stored execution trace of its x86 
> emulation of P(P) after it simulates each instruction of input (P, P). 
> As soon as a non-halting behavior pattern is matched H aborts the 
> simulation of its input and decides that its input does not halt. 
> 
> *This is the sound deductive inference (proof) that H(P,P)==0 is correct* 
> 
> Premise(1) (axiom) Every computation that never halts unless its 
> simulation is aborted is a computation that never halts. This verified 
> as true on the basis of the meaning of its words. 
> 
> Premise(2) (verified fact) The simulation of the input to H(P,P) never 
> halts without being aborted is a verified fact on the basis of its x86 
> execution trace. (shown below). 
> 
> When the simulator determines whether or not it must abort the 
> simulation of its input based on the behavior of its input the simulator 
> only acts as an x86 emulator thus has no effect on the behavior of its 
> input. This allows the simulator to always ignore its own behavior. 
> 
> Conclusion(3) From the above true premises it necessarily follows that 
> simulating halt decider H correctly reports that its input: (P,P) never 
> halts. 
> 
> 
> 
> 
> Halting problem undecidability and infinitely nested simulation 
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
> 
> 
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
https://en.wikipedia.org/wiki/Halting_problem

[toc] | [prev] | [next] | [standalone]

#35636

On 7/3/2021 10:25 AM, wij wrote:
> On Saturday, 3 July 2021 at 23:19:16 UTC+8, olcott wrote:
>> *Halting problem undecidability and infinitely nested simulation*
>> When the halt decider bases its halt status decision simulating its
>> input then the conventional halting problem proof undecidability
>> counter-example templates can be correctly decided as inputs that never
>> halt. They will never halt because they specify infinitely nested
>> simulation to any simulating halt decider.
>>
>> Because a simulating halt decider must always abort the simulation of
>> every input that never halts its halt deciding criteria must be adapted.
>> [ Does the input halt on its input? ] must become [ Does the input halt
>> without having its simulation aborted? ] This change is required because
>> every input to a simulating halt decider either halts on its own or
>> halts because its simulation has been aborted.
>>
>> The standard pseudo-code halting problem template "proved" that the
>> halting problem could never be solved on the basis that neither value of
>> true (halting) nor false (not halting) could be correctly returned to
>> the confounding input.
>>
>> // Simplified Linz Ĥ (Linz:1990:319)
>> void P(u32 x)
>> {
>> u32 Input_Halts = H(x, x);
>> if (Input_Halts)
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> u32 Input_Halts = H((u32)P, (u32)P);
>> Output("Input_Halts = ", Input_Halts);
>> }
>>
>> This problem is overcome on the basis that a simulating halt decider
>> would abort the simulation of its input before ever returning any value
>> to this input. It aborts the simulation of its input on the basis that
>> its input specifies what is essentially infinite recursion (infinitely
>> nested simulation) to any simulating halt decider.
>>
>> The x86utm operating system was created so that the halting problem
>> could be examined concretely in the high level language of C and x86.
>> When examining the halting problem this way every detail can be
>> explicitly specified. UTM tape elements are 32-bit unsigned integers.
>>
>> H analyzes the (currently updated) stored execution trace of its x86
>> emulation of P(P) after it simulates each instruction of input (P, P).
>> As soon as a non-halting behavior pattern is matched H aborts the
>> simulation of its input and decides that its input does not halt.
>>
>> *This is the sound deductive inference (proof) that H(P,P)==0 is correct*
>>
>> Premise(1) (axiom) Every computation that never halts unless its
>> simulation is aborted is a computation that never halts. This verified
>> as true on the basis of the meaning of its words.
>>
>> Premise(2) (verified fact) The simulation of the input to H(P,P) never
>> halts without being aborted is a verified fact on the basis of its x86
>> execution trace. (shown below).
>>
>> When the simulator determines whether or not it must abort the
>> simulation of its input based on the behavior of its input the simulator
>> only acts as an x86 emulator thus has no effect on the behavior of its
>> input. This allows the simulator to always ignore its own behavior.
>>
>> Conclusion(3) From the above true premises it necessarily follows that
>> simulating halt decider H correctly reports that its input: (P,P) never
>> halts.
>>
>>
>>
>>
>> Halting problem undecidability and infinitely nested simulation
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>
>>
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
> 
> In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
> https://en.wikipedia.org/wiki/Halting_problem
> 

There is a huge gap in the reasoning of the halting problem proofs.
All of the conventional halting problem proofs simply assume that H
must return the correct halt status of P(P) to P. None of these
proofs considered the possibility that a simulating halt decider
would be required to abort its input before ever returning any value
to this input.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35638

On 7/3/21 11:32 AM, olcott wrote:
> On 7/3/2021 10:25 AM, wij wrote:
>>
>> In computability theory, the halting problem is the problem of
>> determining, from a description of an arbitrary computer program and
>> an input, whether the program will finish running, or continue to run
>> forever. Alan Turing proved in 1936 that a general algorithm to solve
>> the halting problem for all possible program-input pairs cannot exist.
>> https://en.wikipedia.org/wiki/Halting_problem
>>
> 
> There is a huge gap in the reasoning of the halting problem proofs.
> All of the conventional halting problem proofs simply assume that H
> must return the correct halt status of P(P) to P. None of these
> proofs considered the possibility that a simulating halt decider
> would be required to abort its input before ever returning any value
> to this input.
> 

But what does aborting the simulation have to do with returning the
answer to the caller. THEY ARE DIFFERENT.

You don't seem to be able to understand the fundamental Software
Engineering concept of execution context.

After H aborts the simulation, it needs to do something. By its
requriements, it needs to return that answer to its caller.

When it does, it tells that caller that it thinks that P(P) is
non-Halting, but when it does that to the caller P, that P then halts,
showing that the answer it gave was wrong.

The FUNDAMENTAL definition of Halting is what the machine does when run
as a machine with the given input. It is shown that P(P) does Halt (and
you admit this at times) thus P(P) IS a HALTING computation, by definition.

The non-Halting answer is wrong, by definition.

Any 'logic' that 'proves' otherwise is by definition wrong or at least
shows the logic is inconsistent.

[toc] | [prev] | [next] | [standalone]

#35640

On 7/3/2021 10:56 AM, Richard Damon wrote:
> On 7/3/21 11:32 AM, olcott wrote:
>> On 7/3/2021 10:25 AM, wij wrote:
>>>
>>> In computability theory, the halting problem is the problem of
>>> determining, from a description of an arbitrary computer program and
>>> an input, whether the program will finish running, or continue to run
>>> forever. Alan Turing proved in 1936 that a general algorithm to solve
>>> the halting problem for all possible program-input pairs cannot exist.
>>> https://en.wikipedia.org/wiki/Halting_problem
>>>
>>
>> There is a huge gap in the reasoning of the halting problem proofs.
>> All of the conventional halting problem proofs simply assume that H
>> must return the correct halt status of P(P) to P. None of these
>> proofs considered the possibility that a simulating halt decider
>> would be required to abort its input before ever returning any value
>> to this input.
>>
> 
> But what does aborting the simulation have to do with returning the
> answer to the caller. THEY ARE DIFFERENT.
> 

void P(u32 x)
{
   u32 Input_Halts = H(x, x);
   if (Input_Halts)
     HERE: goto HERE;
}

int main()
{
   u32 Input_Halts = H((u32)P, (u32)P);
   Output("Input_Halts = ", Input_Halts);
}

When the called is calling H in infinitely nested simulation

IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION

IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION

The simulating halt decider H must abort the simulation of its input in 
the computation H(P,P) before returning any value to P.

IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION

IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION

> You don't seem to be able to understand the fundamental Software
> Engineering concept of execution context.
> 
> After H aborts the simulation, it needs to do something. By its
> requriements, it needs to return that answer to its caller.
> 

H does return a value of 0 to main(). H does not return any value to the 
simulated P that calls H in infinitely nested simulation.

> When it does, it tells that caller that it thinks that P(P) is
> non-Halting, but when it does that to the caller P, that P then halts,
> showing that the answer it gave was wrong.
> 

Because a simulating halt decider must always abort the simulation of 
every input that never halts its halt deciding criteria must be adapted.

Does the input halt on its input?
must become
Does the input halt without having its simulation aborted?

This change is required because every input to a simulating halt decider 
either halts on its own or halts because its simulation has been aborted.

> The FUNDAMENTAL definition of Halting is what the machine does when run
> as a machine with the given input. It is shown that P(P) does Halt (and
> you admit this at times) thus P(P) IS a HALTING computation, by definition.
> 

That definition simply ignores simulating halt deciders. The fatal 
mistake of the halting problem proofs is they simply ignoring simulating 
halt deciders.

> The non-Halting answer is wrong, by definition.
> 

The non-halting answer is correct the definition must be adapted.

> Any 'logic' that 'proves' otherwise is by definition wrong or at least
> shows the logic is inconsistent.
> 

According to your incorrect reasoning a simulating halt decider must 
always report true because all of its inputs either halt own their own 
or are aborted.

Because people that are not dumber than a box of rocks do understand 
that computations that only halt because they were aborted are 
computations that never halt there is agreement that your reasoning is 
incorrect.

Ben and Kaz both agree. that computations that only halt because their 
simulation was aborted are non-halting computations.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35642

You are off-topic in comp.lang.c/c++.
Nothing what you say is especially related to C or C++.
Stop posting here.

[toc] | [prev] | [next] | [standalone]

#35644

On 7/3/2021 11:28 AM, Bonita Montero wrote:
> You are off-topic in comp.lang.c/c++.
> Nothing what you say is especially related to C or C++.
> Stop posting here.

It is 100% totally related to software engineering in C.
The first 8 pages of my paper are only about software engineering in C.

Halting problem undecidability and infinitely nested simulation

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35645

> It is 100% totally related to software engineering in C.

It's related to programming in general.
So you shouldn't post in groups related to specific languages.

[toc] | [prev] | [next] | [standalone]

#35646

On 7/3/2021 12:18 PM, Bonita Montero wrote:
>> It is 100% totally related to software engineering in C.
> 
> It's related to programming in general.
> So you shouldn't post in groups related to specific languages.
> 

It is a specific software engineering problem in the C programming 
language. The C source code is provided.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35647

>>> It is 100% totally related to software engineering in C.
>> It's related to programming in general.
>> So you shouldn't post in groups related to specific languages.

> It is a specific software engineering problem in the C programming 
> language. The C source code is provided.

You don't don't discuss any C/C++-specific issues.
comp.theory is the only NG that fits.
Stop posting in comp.lang.c/c++.
You're a off-topic-terrorist.

[toc] | [prev] | [next] | [standalone]

#35649

olcott <NoOne@NoWhere.com> writes:

> Ben and Kaz both agree. that computations that only halt because their
> simulation was aborted are non-halting computations.

I asked you to confirm that:

|| Every computation that halts, for whatever reason, is a halting
|| computation.

Your reply: "OK".  However you try to equivocate between the various
meaning of its/their simulation, you can't avoid this obvious fact.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#35654

On 7/3/2021 1:10 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> Ben and Kaz both agree. that computations that only halt because their
>> simulation was aborted are non-halting computations.
> 
> I asked you to confirm that:
> 
> || Every computation that halts, for whatever reason, is a halting
> || computation.
> 
> Your reply: "OK".  However you try to equivocate between the various
> meaning of its/their simulation, you can't avoid this obvious fact.
> 

On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
 > olcott <NoOne@NoWhere.com> writes:
 >
 >> Truism:
 >> Every simulation that would never stop unless Halts() stops
 >> it at some point specifies infinite execution.
 >
 > Any algorithm that implements this truism is, of course, a halting
 > decider.

Because a simulating halt decider must always abort the simulation of 
every input that never halts its halt deciding criteria must be adapted.

Does the input halt on its input? must become
Does the input halt without having its simulation aborted?

This change is required because every input to a simulating halt decider 
either halts on its own or halts because it has been aborted.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35653

On 7/3/21 12:19 PM, olcott wrote:
> On 7/3/2021 10:56 AM, Richard Damon wrote:
>> On 7/3/21 11:32 AM, olcott wrote:
>>> On 7/3/2021 10:25 AM, wij wrote:
>>>>
>>>> In computability theory, the halting problem is the problem of
>>>> determining, from a description of an arbitrary computer program and
>>>> an input, whether the program will finish running, or continue to run
>>>> forever. Alan Turing proved in 1936 that a general algorithm to solve
>>>> the halting problem for all possible program-input pairs cannot exist.
>>>> https://en.wikipedia.org/wiki/Halting_problem
>>>>
>>>
>>> There is a huge gap in the reasoning of the halting problem proofs.
>>> All of the conventional halting problem proofs simply assume that H
>>> must return the correct halt status of P(P) to P. None of these
>>> proofs considered the possibility that a simulating halt decider
>>> would be required to abort its input before ever returning any value
>>> to this input.
>>>
>>
>> But what does aborting the simulation have to do with returning the
>> answer to the caller. THEY ARE DIFFERENT.
>>
> 
> void P(u32 x)
> {
>   u32 Input_Halts = H(x, x);
>   if (Input_Halts)
>     HERE: goto HERE;
> }
> 
> int main()
> {
>   u32 Input_Halts = H((u32)P, (u32)P);
>   Output("Input_Halts = ", Input_Halts);
> }
> 
> When the called is calling H in infinitely nested simulation
> 
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> 
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> 
> The simulating halt decider H must abort the simulation of its input in
> the computation H(P,P) before returning any value to P.
> 
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> 
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> 

Let us ask what this P above actually is. IF as you claim it does NOT
include the H that it calls, what can it be.

It isn't a program, because if you actually try to complie and run this
program you will get an undefined symbol error when you try to link it.

It isn't a independently callable function that could be a computation,
as again, it is missing the definition of H.

Thus, asking if this P 'Halts' isn't really a valid question. It is like
asking does this P halt or not:

int P1(u32 x)
{
   while(foo(x)
   {
      x++;
   }
}

Tell me, can you determine if this P halts or not?

You will need to decide that this answer depends on what foo does.

This is EXACTLY the same as for the P above, what it does depends on
what H does, and thus H is PART of the definition of its behavior.

P without a definition of H isn't a computation. Since you are insisting
that P doesn't include H, it isn't a computation.

It also says that P is NOT the P of Linz etc, as those DO include their
copy of the H they are defined to work with. Thus you correspondence
claim is shown to be false.


>> You don't seem to be able to understand the fundamental Software
>> Engineering concept of execution context.
>>
>> After H aborts the simulation, it needs to do something. By its
>> requriements, it needs to return that answer to its caller.
>>
> 
> H does return a value of 0 to main(). H does not return any value to the
> simulated P that calls H in infinitely nested simulation.

But if it doesn't return that value to the P that calls H when P is run
as the top level machine, then H fails to be the required computation.

THAT P shows that H is wrong.

> 
>> When it does, it tells that caller that it thinks that P(P) is
>> non-Halting, but when it does that to the caller P, that P then halts,
>> showing that the answer it gave was wrong.
>>
> 
> Because a simulating halt decider must always abort the simulation of
> every input that never halts its halt deciding criteria must be adapted.
> 
> Does the input halt on its input?
> must become
> Does the input halt without having its simulation aborted?

WHY, The first question is STILL Valid, when we actually run P(I) as a
machine.

> 
> This change is required because every input to a simulating halt decider
> either halts on its own or halts because its simulation has been aborted.
> 

WRONG.

>> The FUNDAMENTAL definition of Halting is what the machine does when run
>> as a machine with the given input. It is shown that P(P) does Halt (and
>> you admit this at times) thus P(P) IS a HALTING computation, by
>> definition.
>>
> 
> That definition simply ignores simulating halt deciders. The fatal
> mistake of the halting problem proofs is they simply ignoring simulating
> halt deciders.
> 

No, it doesn't, unless simulating Halt Deciders aren't Halt Deciders,
the definition applies/

>> The non-Halting answer is wrong, by definition.
>>
> 
> The non-halting answer is correct the definition must be adapted.

No, P(P) HALTS. Thus BY DEFINITION, it is a halting computation.


> 
>> Any 'logic' that 'proves' otherwise is by definition wrong or at least
>> shows the logic is inconsistent.
>>
> 
> According to your incorrect reasoning a simulating halt decider must
> always report true because all of its inputs either halt own their own
> or are aborted.

No, that is YOUR incorrect reasoning. If the simulating Halt decider
correctly predicted that the machine will not halt, then when we
actually run that machine, it will not halt, that the answer can be
veriifed correct.

> 
> Because people that are not dumber than a box of rocks do understand
> that computations that only halt because they were aborted are
> computations that never halt there is agreement that your reasoning is
> incorrect.
> 
> Ben and Kaz both agree. that computations that only halt because their
> simulation was aborted are non-halting computations.
> 
> 

[toc] | [prev] | [next] | [standalone]

#35641

olcott <NoOne@NoWhere.com> writes:

>     void P(u32 x)
>     {
>       u32 Input_Halts = H(x, x);
>       if (Input_Halts)
>         HERE: goto HERE;
>     }

For H(P,P) to be correct one of these must apply:

  H(P,P) == 0 and P(P) does not halt, or
  H(P,P) != 0 and P(P) halts.

Neither is the case.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#35643

On 7/3/2021 11:25 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>>      void P(u32 x)
>>      {
>>        u32 Input_Halts = H(x, x);
>>        if (Input_Halts)
>>          HERE: goto HERE;
>>      }
> 
> For H(P,P) to be correct one of these must apply:
> 
>    H(P,P) == 0 and P(P) does not halt, or
>    H(P,P) != 0 and P(P) halts.
> 
> Neither is the case.
> 

Superficially it may seem that way until you realize (as you have 
already realized) that the halt criteria must be adapted for a 
simulating halt decider.

Because a simulating halt decider must always abort the simulation of 
every input that never halts its halt deciding criteria must be adapted.

Does the input halt on its input?
   must become
Does the input halt without having its simulation aborted?

This change is required because every input to a simulating halt decider 
either halts on its own or halts because its simulation has been aborted.

Halting problem undecidability and infinitely nested simulation

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35652

On 7/3/21 12:49 PM, olcott wrote:
> On 7/3/2021 11:25 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>>      void P(u32 x)
>>>      {
>>>        u32 Input_Halts = H(x, x);
>>>        if (Input_Halts)
>>>          HERE: goto HERE;
>>>      }
>>
>> For H(P,P) to be correct one of these must apply:
>>
>>    H(P,P) == 0 and P(P) does not halt, or
>>    H(P,P) != 0 and P(P) halts.
>>
>> Neither is the case.
>>
> 
> Superficially it may seem that way until you realize (as you have
> already realized) that the halt criteria must be adapted for a
> simulating halt decider.
> 

WHY? The standard definition works perfectly fine? Does P(I) Halt or Not
when it runs.

> Because a simulating halt decider must always abort the simulation of
> every input that never halts its halt deciding criteria must be adapted.

But it must CORRECTLY halt. As has been shown, H incorrectly aborts the
simulation of P because it doesn't take into account that this P WILL
Halt because H does incorrectly halt its simulation.
> 
> Does the input halt on its input?
>   must become
> Does the input halt without having its simulation aborted?
> 
> This change is required because every input to a simulating halt decider
> either halts on its own or halts because its simulation has been aborted.

But if it halts because the contained halt decider does abort its own
simulation of a copy of P, then it IS a halting computation.

> 
> Halting problem undecidability and infinitely nested simulation
> 
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
> 
> 
> 

[toc] | [prev] | [next] | [standalone]

#35656 — Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ]

On 7/3/2021 1:17 PM, Richard Damon wrote:
> On 7/3/21 12:49 PM, olcott wrote:
>> On 7/3/2021 11:25 AM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>>       void P(u32 x)
>>>>       {
>>>>         u32 Input_Halts = H(x, x);
>>>>         if (Input_Halts)
>>>>           HERE: goto HERE;
>>>>       }
>>>
>>> For H(P,P) to be correct one of these must apply:
>>>
>>>     H(P,P) == 0 and P(P) does not halt, or
>>>     H(P,P) != 0 and P(P) halts.
>>>
>>> Neither is the case.
>>>
>>
>> Superficially it may seem that way until you realize (as you have
>> already realized) that the halt criteria must be adapted for a
>> simulating halt decider.
>>
> 
> WHY? The standard definition works perfectly fine? Does P(I) Halt or Not
> when it runs.
> 
>> Because a simulating halt decider must always abort the simulation of
>> every input that never halts its halt deciding criteria must be adapted.
> 
> But it must CORRECTLY halt. As has been shown, H incorrectly aborts the
> simulation of P because it doesn't take into account that this P WILL
> Halt because H does incorrectly halt its simulation.
>>
>> Does the input halt on its input?
>>    must become
>> Does the input halt without having its simulation aborted?
>>
>> This change is required because every input to a simulating halt decider
>> either halts on its own or halts because its simulation has been aborted.
> 
> But if it halts because the contained halt decider does abort its own
> simulation of a copy of P, then it IS a halting computation.
> 

This may be simply too difficult for you to understand.

When a simulating halt decider only simulates its input until it detects 
that its input exhibits non-halting behavior then

We can know that this simulating halt decider has no effect what-so-ever 
on the behavior of this input.

This also means that while a simulating halt decider is examining the 
behavior of its input it can safely ignore its own behavior.

When this simulating halt decider does detect an infinite execution 
behavior pattern then it can correctly stop simulating its input and 
report that its input does not halt.


>>
>> Halting problem undecidability and infinitely nested simulation
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>
>>
>>
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35657 — Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ]

On 7/3/21 3:08 PM, olcott wrote:
> On 7/3/2021 1:17 PM, Richard Damon wrote:
>> On 7/3/21 12:49 PM, olcott wrote:
>>> On 7/3/2021 11:25 AM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>>       void P(u32 x)
>>>>>       {
>>>>>         u32 Input_Halts = H(x, x);
>>>>>         if (Input_Halts)
>>>>>           HERE: goto HERE;
>>>>>       }
>>>>
>>>> For H(P,P) to be correct one of these must apply:
>>>>
>>>>     H(P,P) == 0 and P(P) does not halt, or
>>>>     H(P,P) != 0 and P(P) halts.
>>>>
>>>> Neither is the case.
>>>>
>>>
>>> Superficially it may seem that way until you realize (as you have
>>> already realized) that the halt criteria must be adapted for a
>>> simulating halt decider.
>>>
>>
>> WHY? The standard definition works perfectly fine? Does P(I) Halt or Not
>> when it runs.
>>
>>> Because a simulating halt decider must always abort the simulation of
>>> every input that never halts its halt deciding criteria must be adapted.
>>
>> But it must CORRECTLY halt. As has been shown, H incorrectly aborts the
>> simulation of P because it doesn't take into account that this P WILL
>> Halt because H does incorrectly halt its simulation.
>>>
>>> Does the input halt on its input?
>>>    must become
>>> Does the input halt without having its simulation aborted?
>>>
>>> This change is required because every input to a simulating halt decider
>>> either halts on its own or halts because its simulation has been
>>> aborted.
>>
>> But if it halts because the contained halt decider does abort its own
>> simulation of a copy of P, then it IS a halting computation.
>>
> 
> This may be simply too difficult for you to understand.
> 
> When a simulating halt decider only simulates its input until it detects
> that its input exhibits non-halting behavior then
> 
> We can know that this simulating halt decider has no effect what-so-ever
> on the behavior of this input.
> 

Right, but it DOES have an affect on its caller, which you neglect to
take into account.

Also, until its decision is actually PROVED correct, then the fact that
it aborted its simulation does not by itself actually prove that the
decision was correct and the input was actually non-halting.

> This also means that while a simulating halt decider is examining the
> behavior of its input it can safely ignore its own behavior.

It can ignore 'its own', but not other instances of itself. If is sees a
copy of itslef (even if the same exact source code executing at the same
addresses, but in a different execution context). then because that
decier CAN AND WILL affect the execution of the machine it is simulating
(the caller of that copy) it MUST include its behavior.

Fundamentally, you are missing the important Software Engineering
concept of exectution context. The exact same code executing under
different contexts needs to be considered as different identities.

> 
> When this simulating halt decider does detect an infinite execution
> behavior pattern then it can correctly stop simulating its input and
> report that its input does not halt.
> 
> 
It has INCORRECTLY detected an infinite execution because it has failed
to take into account the actions of the copy of H within its simulation.

It is starting by ASSUMING that H doesn't abort its simulation. As soon
as it decides that maybe it should abort its own simulation, it needs to
feed that change of condition back into its logic about what it has
seen. Since it is contemplating aborting its own simulation, it needs to
take into account that other copies might do the same. Failure to do so
leads to faulting reasoning and wrong answers.

[toc] | [prev] | [next] | [standalone]

#35660 — Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard)

On 7/3/2021 2:43 PM, Richard Damon wrote:
> On 7/3/21 3:08 PM, olcott wrote:
>> On 7/3/2021 1:17 PM, Richard Damon wrote:
>>> On 7/3/21 12:49 PM, olcott wrote:
>>>> On 7/3/2021 11:25 AM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>>        void P(u32 x)
>>>>>>        {
>>>>>>          u32 Input_Halts = H(x, x);
>>>>>>          if (Input_Halts)
>>>>>>            HERE: goto HERE;
>>>>>>        }
>>>>>
>>>>> For H(P,P) to be correct one of these must apply:
>>>>>
>>>>>      H(P,P) == 0 and P(P) does not halt, or
>>>>>      H(P,P) != 0 and P(P) halts.
>>>>>
>>>>> Neither is the case.
>>>>>
>>>>
>>>> Superficially it may seem that way until you realize (as you have
>>>> already realized) that the halt criteria must be adapted for a
>>>> simulating halt decider.
>>>>
>>>
>>> WHY? The standard definition works perfectly fine? Does P(I) Halt or Not
>>> when it runs.
>>>
>>>> Because a simulating halt decider must always abort the simulation of
>>>> every input that never halts its halt deciding criteria must be adapted.
>>>
>>> But it must CORRECTLY halt. As has been shown, H incorrectly aborts the
>>> simulation of P because it doesn't take into account that this P WILL
>>> Halt because H does incorrectly halt its simulation.
>>>>
>>>> Does the input halt on its input?
>>>>     must become
>>>> Does the input halt without having its simulation aborted?
>>>>
>>>> This change is required because every input to a simulating halt decider
>>>> either halts on its own or halts because its simulation has been
>>>> aborted.
>>>
>>> But if it halts because the contained halt decider does abort its own
>>> simulation of a copy of P, then it IS a halting computation.
>>>
>>
>> This may be simply too difficult for you to understand.
>>
>> When a simulating halt decider only simulates its input until it detects
>> that its input exhibits non-halting behavior then
>>
>> We can know that this simulating halt decider has no effect what-so-ever
>> on the behavior of this input.
>>
> 
> Right, but it DOES have an affect on its caller, which you neglect to
> take into account.
> 

If a simulating halt decider H ALWAYS merely simulates its input until 
it detects that its input matches an infinite execution behavior pattern 
then H can always ignore its own behavior when it is analyzing the halt 
status of its input.

Even though you have been very very annoying this last couple of message 
exchanges were very very helpful in that they forced me to make my 
explanations much much more clear. As a result of this I am very 
thankful for your reviews.

> Also, until its decision is actually PROVED correct, then the fact that
> it aborted its simulation does not by itself actually prove that the
> decision was correct and the input was actually non-halting.
> 

Of course it doesn't

>> This also means that while a simulating halt decider is examining the
>> behavior of its input it can safely ignore its own behavior.
> 
> It can ignore 'its own', but not other instances of itself. 

It can always ignore it own behavior and it can do this by screening out 
machine address ranges to be ignored. H ignores all of its own behavior 
and the behavior or every operating system function.

> If is sees a
> copy of itslef (even if the same exact source code executing at the same
> addresses, but in a different execution context). then because that
> decier CAN AND WILL affect the execution of the machine it is simulating
> (the caller of that copy) it MUST include its behavior.
> 

It is only the outer-most H that aborts the simulation of its input 
(only the outer H has seen the longest execution trace) and it only does 
this after its input has totally proven that it is never ever going to 
halt unless it is aborted.

> Fundamentally, you are missing the important Software Engineering
> concept of exectution context. The exact same code executing under
> different contexts needs to be considered as different identities.
> 

Not at all. It is a verifiable fact that every H only simulates its 
input until its input has proven beyond all possible doubt that it is 
never ever going to halt unless aborted by some H.

>>
>> When this simulating halt decider does detect an infinite execution
>> behavior pattern then it can correctly stop simulating its input and
>> report that its input does not halt.
>>
>>
> It has INCORRECTLY detected an infinite execution because it has failed
> to take into account the actions of the copy of H within its simulation.
> 

void P(u32 x)
{
   u32 Input_Halts = H(x, x);
   if (Input_Halts)
     HERE: goto HERE;
}

There are no copies. There are nested invocations that all share the 
same machine code in the same way that recursive invocations share the 
same machine code. Nested simulations are really nothing more than a 
slightly more complex case of recursive invocation.

> It is starting by ASSUMING that H doesn't abort its simulation. As soon
> as it decides that maybe it should abort its own simulation, it needs to

H only aborts its simulation after it has 100% perfect proof that it must.

> feed that change of condition back into its logic about what it has
> seen. Since it is contemplating aborting its own simulation, it needs to
> take into account that other copies might do the same. Failure to do so
> leads to faulting reasoning and wrong answers.
> 

As soon as the input to H meets the infinite recursion criteria H stops 
its simulation.



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#35663 — Re: Could H correctly decide that P never halts? [ Why can H ignore its own behavior? ](my thanks to Richard)

On 7/3/21 4:37 PM, olcott wrote:
> On 7/3/2021 2:43 PM, Richard Damon wrote:
>> On 7/3/21 3:08 PM, olcott wrote:
>>> On 7/3/2021 1:17 PM, Richard Damon wrote:
>>>> On 7/3/21 12:49 PM, olcott wrote:
>>>>> On 7/3/2021 11:25 AM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>>        void P(u32 x)
>>>>>>>        {
>>>>>>>          u32 Input_Halts = H(x, x);
>>>>>>>          if (Input_Halts)
>>>>>>>            HERE: goto HERE;
>>>>>>>        }
>>>>>>
>>>>>> For H(P,P) to be correct one of these must apply:
>>>>>>
>>>>>>      H(P,P) == 0 and P(P) does not halt, or
>>>>>>      H(P,P) != 0 and P(P) halts.
>>>>>>
>>>>>> Neither is the case.
>>>>>>
>>>>>
>>>>> Superficially it may seem that way until you realize (as you have
>>>>> already realized) that the halt criteria must be adapted for a
>>>>> simulating halt decider.
>>>>>
>>>>
>>>> WHY? The standard definition works perfectly fine? Does P(I) Halt or
>>>> Not
>>>> when it runs.
>>>>
>>>>> Because a simulating halt decider must always abort the simulation of
>>>>> every input that never halts its halt deciding criteria must be
>>>>> adapted.
>>>>
>>>> But it must CORRECTLY halt. As has been shown, H incorrectly aborts the
>>>> simulation of P because it doesn't take into account that this P WILL
>>>> Halt because H does incorrectly halt its simulation.
>>>>>
>>>>> Does the input halt on its input?
>>>>>     must become
>>>>> Does the input halt without having its simulation aborted?
>>>>>
>>>>> This change is required because every input to a simulating halt
>>>>> decider
>>>>> either halts on its own or halts because its simulation has been
>>>>> aborted.
>>>>
>>>> But if it halts because the contained halt decider does abort its own
>>>> simulation of a copy of P, then it IS a halting computation.
>>>>
>>>
>>> This may be simply too difficult for you to understand.
>>>
>>> When a simulating halt decider only simulates its input until it detects
>>> that its input exhibits non-halting behavior then
>>>
>>> We can know that this simulating halt decider has no effect what-so-ever
>>> on the behavior of this input.
>>>
>>
>> Right, but it DOES have an affect on its caller, which you neglect to
>> take into account.
>>
> 
> If a simulating halt decider H ALWAYS merely simulates its input until
> it detects that its input matches an infinite execution behavior pattern
> then H can always ignore its own behavior when it is analyzing the halt
> status of its input.

No it can't. Because the fact that H does abort it simulation does
affect the code that we simulated CALLING that H.

You are making a BIG assertion here with ZERO proof.

The clear counter example is that if we REALLY look at what would happen
to Linz H^. Given that your H is stipulated to return the non-Halting
answer, H^ (here called P) will clearly halt. UTM(P,P) will finish in
finite time. THEREFORE, H did not NEED to abort its simulation. Yes, it
is programmed to do so, but it is wrong in doing it.

If you change H to not abort, you now have a DIFFERENT machine P,
because Turing Machines contain ALL of the code that they exectute (if
you want to claim otherwise PROVE IT). Thus any anlaysis done with a P
using a non-aborting H is irrelevenent to the P that uses an aborting H.

> 
> Even though you have been very very annoying this last couple of message
> exchanges were very very helpful in that they forced me to make my
> explanations much much more clear. As a result of this I am very
> thankful for your reviews.
> 
>> Also, until its decision is actually PROVED correct, then the fact that
>> it aborted its simulation does not by itself actually prove that the
>> decision was correct and the input was actually non-halting.
>>
> 
> Of course it doesn't

WHy not. P(P) Does Halt. You have traced it to do so. It is simple to
analytically prove this too with the simple fact of inspection of the
code with the stipulation that H(P,P) returns 0.

Give an ACTUAL proof that it is correct.

Note, your traces sren't one because you make the analysis based on the
incorrect assumption that you can ignore the actions of the decider in
analyizing the trace. Your 'rules' ignore that H WILL abort the simulation.
> 
>>> This also means that while a simulating halt decider is examining the
>>> behavior of its input it can safely ignore its own behavior.
>>
>> It can ignore 'its own', but not other instances of itself. 
> 
> It can always ignore it own behavior and it can do this by screening out
> machine address ranges to be ignored. H ignores all of its own behavior
> and the behavior or every operating system function.


Yes, you can do it, but you get improper results. You have not shown ANY
Logical ground for you 'claim' that you can ignore the behavior of the
copy of H within P in anylizing P. ZERO.

Please show an ACTUAL proof that this if valid, starting from well
accepted properties of machines, with sound analyitical steps. Or even a
reputable source that makes this same claim under these conditions.

IT WON'T EXIST.

> 
>> If is sees a
>> copy of itslef (even if the same exact source code executing at the same
>> addresses, but in a different execution context). then because that
>> decier CAN AND WILL affect the execution of the machine it is simulating
>> (the caller of that copy) it MUST include its behavior.
>>
> 
> It is only the outer-most H that aborts the simulation of its input
> (only the outer H has seen the longest execution trace) and it only does
> this after its input has totally proven that it is never ever going to
> halt unless it is aborted.

But, if the outer-most H is modified (without changing the H that is
inside P) to be just a simulatior, then it is seen that P will halt.
Thus it was WRONG to decide that it was non-halting.

BAD LOGIC, BAD LOGIC.

> 
>> Fundamentally, you are missing the important Software Engineering
>> concept of exectution context. The exact same code executing under
>> different contexts needs to be considered as different identities.
>>
> 
> Not at all. It is a verifiable fact that every H only simulates its
> input until its input has proven beyond all possible doubt that it is
> never ever going to halt unless aborted by some H.
> 


NOT PROVEN, decieded with unsound logic. FAIL.

SOME H, yes, an H that is part of the logic of P will incorrectly abort
the simulation of a copy of P and allow P to come to a halt.

Since this is PART of P, that lets that decision be part of the reason
that P is a halting computation.
Just like this one:

for(int i=0; isLessThan(i, 5); i++) continue;

>>>
>>> When this simulating halt decider does detect an infinite execution
>>> behavior pattern then it can correctly stop simulating its input and
>>> report that its input does not halt.
>>>
>>>
>> It has INCORRECTLY detected an infinite execution because it has failed
>> to take into account the actions of the copy of H within its simulation.
>>
> 
> void P(u32 x)
> {
>   u32 Input_Halts = H(x, x);
>   if (Input_Halts)
>     HERE: goto HERE;
> }
> 
> There are no copies. There are nested invocations that all share the
> same machine code in the same way that recursive invocations share the
> same machine code. Nested simulations are really nothing more than a
> slightly more complex case of recursive invocation.

If no copies, then NOT the H^ of Linz and not even the equivalent of a
proper Turing Machine.

You have YET to prove that claim.

> 
>> It is starting by ASSUMING that H doesn't abort its simulation. As soon
>> as it decides that maybe it should abort its own simulation, it needs to
> 
> H only aborts its simulation after it has 100% perfect proof that it must.

Maybe YOU think it is 100% certain, but you are using unsound logic and
wrong.

This is PROVEN by the fact that even YOU have demonstarted the P(P) when
run as the top level machine Halts.

Halting != non-Halting

> 
>> feed that change of condition back into its logic about what it has
>> seen. Since it is contemplating aborting its own simulation, it needs to
>> take into account that other copies might do the same. Failure to do so
>> leads to faulting reasoning and wrong answers.
>>
> 
> As soon as the input to H meets the infinite recursion criteria H stops
> its simulation.
> 
> 
> 

WRONG. As soom as H incorrectly matches the incorrect criteria it
incorrectly halts P and gives the wrong answer.

You can't be much more wrong there.

[toc] | [prev] | [next] | [standalone]

Page 1 of 7  [1] 2 3 4 5 6 7  Next page →

Back to top | Article view | comp.theory

csiph-web