Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2650
| 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
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
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