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


Groups > comp.theory > #34010

Re: Infinitely Recursive input on HP Proofs

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Infinitely Recursive input on HP Proofs
Date 2021-05-20 12:57 +0100
Organization A noiseless patient Spider
Message-ID <87fsyhvcre.fsf@bsb.me.uk> (permalink)
References (13 earlier) <15406379-420c-4c32-b713-be57e31901ban@googlegroups.com> <87sg2l2ma2.fsf@bsb.me.uk> <356dndvIucnMWT_9nZ2dnUU7-bmdnZ2d@giganews.com> <87eee43mgf.fsf@bsb.me.uk> <IO6dnYnAp8SQjT79nZ2dnUU7-IPNnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> Ĥ(<Ĥ>) Input <Ĥ> only halts because its simulator stopped simulating
> it precisely meeting the criteria of a non-halting computation
> therefore Ĥ correctly decides that its input <Ĥ> is a non-halting
> computation.

Garbage.  So many errors it's almost impossible to reply.  Let me have a
go.

> Ĥ(<Ĥ>) Input <Ĥ> only halts

Inputs don't halt or not halt.  Inputs are strings.  TM's halt or don't
halt when presented with input strings.

> because its simulator stopped simulating
> it precisely meeting the criteria of a non-halting computation

It's called the silly-non-halting criterion.  You refused to pick a name
so I picked that one.  Call the criterion something that it is not is
dishonest.

> therefore Ĥ correctly decides

H^ is not a decider.

> that its input <Ĥ> is a non-halting computation.

<H^> is not even a computation.  It's a string, and it's not even a
string representing a computation.

The facts:

(a) UTM^([UTM^]) is not a finite computation.  The "hat" construction
    means that a pure simulator will not halt on it's "hat" version.

(b) Your partial decider, D, is a UTM that also scans for the
    silly-non-halting pattern.  It is not a UTM.

(c) D^([D^]) is a finite computation.

(d) D(<[D^], [D^]>) gives the wrong result for the halting problem but,
    according to you, the correct result or the silly-non-halting
    problem.

You see?  If you don't abuse names and language it's easy to keep things
clear and simple.

Notation: M(s) is the computation that results from Turing machine M
applied to string s.  [M] is the string encoding of a TM M.  <x, y> is
the encoding of a pair of strings.  <[M], s> is therefore the string
representing M(s).

M^(s) is M'(<s, s>) where M' is a TM that does not halt on exactly those
inputs on which M halts.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 14:09 -0500
  Re: Infinitely Recursive input on HP Proofs Jeff Barnett <jbb@notatt.com> - 2021-05-16 13:46 -0600
  Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 19:05 -0400
    Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 18:21 -0500
      Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 21:11 -0400
        Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 21:01 -0500
          Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 23:18 -0400
            Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 22:23 -0500
              Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 07:11 -0400
              Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 07:26 -0400
                Re: Infinitely Recursive input on HP Proofs Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-05-17 05:45 -0700
                Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 10:23 -0500
                Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 20:41 -0400
                Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-17 20:27 +0100
                Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 14:31 -0500
                Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-18 01:38 +0100
                Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 19:54 -0500
                Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 21:21 -0400
                Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-20 12:57 +0100
                Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 20:43 -0400
      Re: Infinitely Recursive input on HP Proofs André G. Isaak <agisaak@gm.invalid> - 2021-05-16 19:15 -0600
        Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 20:34 -0500
          Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 21:55 -0400
  Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 15:56 -0400
  Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-16 21:21 +0100
    Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 17:19 -0400
      Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 16:37 -0500
    Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 16:00 -0500
      Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-17 02:19 +0100
        Re: Infinitely Recursive input on HP Proofs (Full Linz text) olcott <NoOne@NoWhere.com> - 2021-05-16 20:54 -0500
          Re: Infinitely Recursive input on HP Proofs (Full Linz text) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-18 01:57 +0100
            Re: Infinitely Recursive input on HP Proofs (eternally on this point) olcott <NoOne@NoWhere.com> - 2021-05-17 20:34 -0500

csiph-web