Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Path | csiph.com!aioe.org!opIzC+UpU1FF0qsNaB+JHA.user.gioia.aioe.org.POSTED!not-for-mail |
|---|---|
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
| Newsgroups | comp.theory |
| Subject | Re: HALT has to solve NON_HALTING TMs but has to HALT itself! |
| Date | Tue, 15 Dec 2020 20:44:03 +0000 (UTC) |
| Organization | Aioe.org NNTP Server |
| Lines | 24 |
| Message-ID | <20201215123748.481@kylheku.com> (permalink) |
| References | <9d72637f-0382-4596-bbb4-36fbde2f2355n@googlegroups.com> |
| NNTP-Posting-Host | opIzC+UpU1FF0qsNaB+JHA.user.gioia.aioe.org |
| X-Complaints-To | abuse@aioe.org |
| User-Agent | slrn/1.0.3 (Linux) |
| X-Notice | Filtered by postfilter v. 0.9.2 |
| Xref | csiph.com comp.theory:27069 |
Show key headers only | View raw
On 2020-12-15, Graham Cooper <grahamcooper7@gmail.com> wrote: > Doesn't matter, if halt hangs on a spurious program test > then that program hangs too so we KNOW its halt value > with incremental processing time! You can't externally tell the difference between a machine that truly hangs forever, and a machine that terminates, but has not yet done so: it just requires more time and steps. Only using internal reasoning---by observing some internal behavior, or deducing it from analyzing the code---can you tell that something hangs forever. Like, "aha, here is a trivial endless loop, which is provably reached from the starting point in no more than 300 steps". This is the same as the halting problem. The halting theorem says that there can be no universal algorithm for deciding, in a finite number of steps, whether a given machine will halt. Thus when you say "if halt hangs ... that program hals too ... so we KNOW its halt value", you are necessarily taking the perspective that we have a magic oracle that allows us to know. We do not have an algorithm (Turing computation) to be able to KNOW; not for any arbitary machine.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-15 07:19 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2020-12-15 20:15 +0000
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-15 20:44 +0000
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-15 14:56 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-16 17:04 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 01:40 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-17 12:02 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 19:58 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-17 21:39 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 22:18 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-17 23:23 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-17 23:30 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Jeff Barnett <jbb@notatt.com> - 2020-12-15 15:00 -0700
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-15 22:13 +0000
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-15 23:12 +0000
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Graham Cooper <grahamcooper7@gmail.com> - 2020-12-15 15:23 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-16 00:39 +0000
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! olcott <NoOne@NoWhere.com> - 2020-12-15 17:26 -0600
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! "dklei...@gmail.com" <dkleinecke@gmail.com> - 2020-12-15 16:01 -0800
Re: HALT has to solve NON_HALTING TMs but has to HALT itself! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-16 00:15 +0000
csiph-web