Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2654
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Newsgroups | comp.theory, comp.lang.c, comp.lang.c++, comp.software-eng |
| Subject | Re: A UTM halt decider <is> a pure function of its inputs (HP undecidability) |
| Followup-To | comp.theory |
| Date | 2021-03-30 15:03 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20210330075406.357@kylheku.com> (permalink) |
| References | (19 earlier) <hqidnTrQ-oVUE__9nZ2dnUU7-eudnZ2d@giganews.com> <20210329202056.955@kylheku.com> <uc-dnTZHvsKqPf_9nZ2dnUU7-Y_NnZ2d@giganews.com> <20210329211550.916@kylheku.com> <oLydnQPuAMc8rv79nZ2dnUU7-VPNnZ2d@giganews.com> |
Cross-posted to 4 groups.
Followups directed to: comp.theory
On 2021-03-30, olcott <NoOne@NoWhere.com> wrote: > On 3/30/2021 12:28 AM, Kaz Kylheku wrote: >> On 2021-03-30, olcott <NoOne@NoWhere.com> wrote: >>> Without changing the definition of H^ in the tiniest little bit I have >>> shown that it specifies infinite recursion: >> >> That is untrue. >> >> What H^ specifies depends on the nature of H, because the bulk of H^ is >> the sub-function H. > > http://www.liarparadox.org/Peter_Linz_HP(Pages_318-319).pdf > > Whenever H is a simulator then H^ <is> infinitely recursive never > reaching the appended loop states whether or not the simulator always > returns a value of true or false. H is not required to be a simulator. If H simply executes its input, we know that it fails to decide due to runaway recursion: the input calls the decider, which executes its input, which calls the decider. This is freshman-level obvious. The first materials I ever read about the halting problem spelled this out, for the dummies. > Never has had any effect on halting problem undecidability Not returning is completely, utterly relevant to undecidability. The undecidability of halting means that a decision function can only decide at most a subset of the possible cases, not all of them. Outside of the subset which it decides, it misbehaves in one of several ways: it either returns the wrong answer, or fails to halt, or else something else, like failing due to a division by zero or similar problem. Runaway recursion falls under "fails to halt"; it's a failed case. > because no halt decider would ever return any value to H^. Except in your program, where a "pure function" sometimes returns a value and sometimes doesn't, for the same pair of visible arguments! -- 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: A UTM halt decider <is> a pure function of its inputs (HP undecidability) olcott <NoOne@NoWhere.com> - 2021-03-30 09:20 -0500 Re: A UTM halt decider <is> a pure function of its inputs (HP undecidability) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-30 15:03 +0000
csiph-web