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


Groups > comp.theory > #24447

Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ]

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ]
Date 2020-10-26 03:10 +0000
Organization A noiseless patient Spider
Message-ID <877drd4r85.fsf@bsb.me.uk> (permalink)
References <4-idnf07o54augvCnZ2dnUU7-f_NnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> Generic system to overcome the halting problem proofs
>
> We can ask the halt deciding question in a way that allows the input
> program to do the opposite of whatever the halt decider decides:
> "Does this input program halt on its input (yes or no)?"
>
> Or we can ask the halt deciding question in such a way where it is
> impossible for the input program to do the opposite of what the halt
> decider decides:
>
> Did the UTM halt decider have to stop executing its subordinate UTM to
> prevent its own infinite execution?

This either gives the same result as the above (in which case the same
example defeats it) or it does not give the same result and thus does
not address the halting problem at all.  (Or, I should say, both -- it
can be wrong in both ways).

> The UTM halt decider executes its subordinate UTM one state transition
> at a time until it decides that it must stop the execution of its
> subordinate UTM or its subordinate UTM has terminated normally.
>
> The halt decider UTM transitions to one of two final states
> ((qn)) or ((qy)) indicating its decision.

Reader beware.  Peter Olcott either does not know what a UTM is or he
wilfully misuses the term as often as he can.  This is an example: the
final state of a UTM has nothing to do with the final state of the TM
being interpreted.

> Here is the same thing as a conventional software function:
> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>
> Specific details of overcoming the Peter Linz Halting problem proof
> The following code is based on the Peter Linz H and Ĥ
> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>
> I created the x86utm operating system on the basis of a very excellent x86 emulator. The x86 emulator is written in "C" and has been adapted to
> run on Linux and Windows.
>
> x86 language ≡ von Neumann architecture ≡ UTM

And there's another misuse of the term.

> x86utm operating system is written in C++ and provides a way to
> functions written in "C" to be converted into virtual machines that
> are executed in their own process context. The x86 machine language is
> the the description language of these UTM equivalents and can be
> directly executed in x86utm.

And another three.

> main() executes H() and
> Aborted_Because_Non_Halting_Behavior_Detected(M, M)) in the process
> context of x86utm. Aborted_Because_Non_Halting_Behavior_Detected(M,
> M)) creates a whole new process context to execute H_Hat() in a
> DebugTrace() DebugStep() mode. All of this is fully operational.

but mysteriously hidden!

> // M has the machine address of H_Hat()
> void H_Hat(u32 M)
> {
>   if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
>     MOV_EAX_0  // Execution of M(N) has been aborted

This comment is wrong.

>   else
>   {
>     MOV_EAX_1  // M(N) has halted

And this one too.

>     HERE: goto HERE;
>   }
>   HALT
> }
>
> // M and N have the machine address of H_Hat()
> void H(u32 M, u32 N)
> {
>   if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))

And this function call is wrong in general, but since you call H with
both M and N the same, you can get away with it.

>     MOV_EAX_0  // Execution of M(N) has been aborted
>   else
>     MOV_EAX_1  // M(N) has halted
>   HALT
> }
>
> int main()
> {
>   u32 M = (u32)H_Hat;
>   H(M, M);   // MOV_EAX_0
>   HALT
> }
>
> Continuing from above: H_Hat() executes another instance of
> Aborted_Because_Non_Halting_Behavior_Detected(M, M) in its own process
> context which creates another process context to execute a second
> instance of H_Hat().
>
> As soon as the second H_Hat() would execute

> Aborted_Because_Non_Halting_Behavior_Detected(M, M) a second time from
> the same machine address the first instance of
> Aborted_Because_Non_Halting_Behavior_Detected(M, M) recognizes that
> H_Hat() is infinitely recursive. // 2018-12-13 @7:00 PM solution
>
> This first instance stops executing H_Hat() which has invoked the
> second instance of Aborted_Because_Non_Halting_Behavior_Detected(M, M)
> which is executing the second instance of H_Hat().
>
> The outer Aborted_Because_Non_Halting_Behavior_Detected(M, M) has
> terminated the whole process tree (or hierarchy of UTMs executing
> other UTMs) before the second instance has returned a value.
>
> Although I have this complete detailed description of exactly how H()
> correctly decides halting on H_Hat()

This description makes no mention of H and, in fact, H gets the answer
wrong.  Why?

First, for the result of H(H_Hat, H_Hat) to be correct it must indicate
the halting status of the computation.  H can be wrong about every other
computation but not about this one.  Indeed, H can even indicate
different things for various different computations -- "took too many
step to halt", "executed more than 42 instructions", "jumped back more
times than forwards", "aborted", whatever.  The only requirement is that
it indicate halting in the case of H(H_Hat, H_Hat).  (I'm labouring this
point because Pater Olcott has refused to be 100^ clear about the
meaning of H's result.)

So what really happens?  Well, no matter how complicated Peter Olcott
tries to make the action of
Aborted_Because_Non_Halting_Behavior_Detected appear, the expressions

  Aborted_Because_Non_Halting_Behavior_Detected(M, M)

in H_Hat, and, if corrected, (though it does not matter in this case)

  Aborted_Because_Non_Halting_Behavior_Detected(M, N)

in H must have the same value.

Now, if that value is true, then H(H_Hat, H_Hat) is just

    MOV_EAX_0
    HALT

indicating that H_Hat(H_Hat) is a non halting computation (that's the
0).  But H_Hat(H_Hat) is in fact just

     MOV_EAX_0
     HALT

And when Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) is
false, H(H_Hat, H_Hat) is just

    MOV_EAX_1
    HALT

indicating that H_Hat(H_Hat) is a halting computation when in fact it is

    MOV_EAX_1
    HERE: goto HERE;

> the code for this has not been written.

No surprise there.  Sadly, Peter Olcott can't post the version he
claimed to have fully encoded as actual Turing machines almost two years
because it doesn't exist.  I suspect this version will never exist
either.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] olcott <NoOne@NoWhere.com> - 2020-10-25 20:33 -0500
  Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-26 03:10 +0000
  Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] André G. Isaak <agisaak@gm.invalid> - 2020-10-26 08:18 -0600
    Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] olcott <NoOne@NoWhere.com> - 2020-10-26 12:52 -0500
      Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] André G. Isaak <agisaak@gm.invalid> - 2020-10-26 12:12 -0600
        Re: Making the Halting Problem Decidable [ Includes deciding the Peter Linz proof counter-example ] olcott <NoOne@NoWhere.com> - 2020-10-26 14:05 -0500

csiph-web