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


Groups > comp.theory > #27069

Re: HALT has to solve NON_HALTING TMs but has to HALT itself!

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


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