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


Groups > comp.software-eng > #2650

Re: Refuting the halting problem proofs with fully operational code (It is not that hard.)

From Kaz Kylheku <563-365-8930@kylheku.com>
Newsgroups comp.theory, comp.software-eng
Subject Re: Refuting the halting problem proofs with fully operational code (It is not that hard.)
Followup-To comp.theory
Date 2021-03-16 19:12 +0000
Organization A noiseless patient Spider
Message-ID <20210316115933.537@kylheku.com> (permalink)
References (19 earlier) <20210316061548.403@kylheku.com> <9fSdncnjp4ZJWs39nZ2dnUU7-avNnZ2d@giganews.com> <20210316100627.299@kylheku.com> <_5SdnUYjON_4ac39nZ2dnUU7-QnNnZ2d@giganews.com> <jcSdnb84BfUwZs39nZ2dnUU7-UPNnZ2d@giganews.com>

Cross-posted to 2 groups.

Followups directed to: comp.theory

Show all headers | View raw


On 2021-03-16, olcott <NoOne@NoWhere.com> wrote:
>
> (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.

Firstly, why don't these same (1) ... (7) steps play out when we have this:

   main()
   {
      H_Hat((u32) H_Hat);
   }

Here, H_Hat calls Halts(P, P). Thus

  (1) Halts() begins simulating H_Hat(H_Hat)

  (2) Halts()  maintains an execution trace ...

  etc.

Secondly, step (4) is wrong. H_Hat(H_Hat) does terminate; it terminates
spontaneously when it gets a 0 from Halts. The execution trace is
incomplete/incorrect, causing (4) to make the wrong conclusion.

The trace is incomplete because Halts is not tracing into the
Halts(P, P) call that H_Hat is making.

Halts is *pretending* that Halts(P, P) is just a transparent P(P).

But that is not true; and moments later, Halts itself "behaves opposite"
to that by returning 0 from a Halts(P, P) invocation.

Your Halts is a pathological liar, basically.

That's your entire trick:

1. Whenever H_Hat calls Halts, your contraption switches Halts(P, I)
   into being just a transparent P(I) call.

2. When Halts is called directly without going through H_Hat,
   Halts is the real function, containing decision-making logic,
   and not just P(I) call.

3. Whenever Halts simulates H_Hat calling Halts, the situation is
   again like (1): it is assumed that Halts(P, I) is just P(I).


-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Back to comp.software-eng | Previous | Next — Previous in thread | Find similar | Unroll thread


Thread

Re: Refuting the halting problem proofs with fully operational code (argument reframed on Ben's suggestion) olcott <polcott2@gmail.com> - 2021-03-14 13:17 -0500
  Re: Refuting the halting problem proofs [...]. (I dare you to find the error) olcott <NoOne@NoWhere.com> - 2021-03-15 09:09 -0500
    Re: Refuting the halting problem proofs [...]. (I dare you to find the error) olcott <NoOne@NoWhere.com> - 2021-03-15 10:11 -0500
  Re: Refuting the halting problem proofs with fully operational code (It is not that hard.) olcott <NoOne@NoWhere.com> - 2021-03-16 13:40 -0500
    Re: Refuting the halting problem proofs with fully operational code (It is not that hard.) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-16 19:12 +0000

csiph-web