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


Groups > sci.logic > #172560

Re: What is the deal with the Halting Theorem?

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups sci.logic
Subject Re: What is the deal with the Halting Theorem?
Date 2018-02-13 04:46 +0000
Organization A noiseless patient Spider
Message-ID <87h8qlh4z9.fsf@bsb.me.uk> (permalink)
References (2 earlier) <p5n0qj$lq$1@dont-email.me> <87bmgwn1oj.fsf@bsb.me.uk> <955791b3-0b0c-4b81-8e5d-3f366c1451b6@googlegroups.com> <87fu66hzs7.fsf@bsb.me.uk> <tuednf9IGNVozB_HnZ2dnUU7-IvNnZ2d@giganews.com>

Show all headers | View raw


Pete Olcott <Pete@NoEmail.address> writes:

> On 2/12/2018 11:40 AM, Ben Bacarisse wrote:
>> peteolcott <peterolcott2@gmail.com> writes:
>>
>>> On Saturday, February 10, 2018 at 12:23:59 PM UTC-6, Ben Bacarisse wrote:
>>>> Newberry writes:
>>>>
>>>>> grahamcooper wrote:
>>>>>> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote:
>>>>>>> For every decider we can construct a "counter-example", i.e. a program
>>>>>>> constructed from the decider such that it will do the opposite of what
>>>>>>> the decider says. So there is no universal decider, right? Right, but
>>>>>>> there is s decider that can prove that it cannot prove that the
>>>>>>> counter-example halts. [It cannot prove that the counter-example does
>>>>>>> not halt.] In fact I claim that there exists a decider that can
>>>>>>> dichotomize the entire space of programs: either it can prove that P
>>>>>>> halts on q, or it can prove that it cannot prove that P halts on q.
>>>>>>>
>>>>>>> I am 80% sure I am right. Prove me wrong.
>>>>>>
>>>>>> That's fuzzy logic!
>>>>>
>>>>> No, that's non-bivalent logic.
>>>>>
>>>>>> Halt Loop Neither
>>>>>
>>>>>     T    F     ~T
>>>>
>>>> Given that every instance of the halting problem is a computation that
>>>> either halts or does not halt, which computations do you plan to assign
>>>> to the "neither" camp?
>>>
>>> Therefore H would correctly transition to its H.qn state rejecting the
>>> infinitely recursive evaluation sequence specified by [Ĥx] [Ĥx] as the
>>> semantic error of Pathological self-reference(Olcott 2004).
>>
>> This is not an answer to my question.  I think Newberry does not reply
>> to my posts (for which I am grateful) so I should probably not have
>> phrased it as a question.  I should simply have asserted that there are
>> no instances for which the "neither" camp is correct, and then there
>> would have been no question for you to not answer.
>
> H.qy pair of finite strings represent a correct TMD that halts on its input
> else
> (1) Not a syntactically correct TMD
> (2) Not a semantically correct TFD (PSR) error
> (3) A correct TMD that does not halt.
>
> The first two being not a TMD that halts and not a TMD that does not
> halt, thus neither.

You could do that, but that is not the halting problem.  The halting
problem (when expressed in terms of string as you prefer) is to decide
the set of strings that encode a TM and a string where the TM would halt
when given that string.  Thus (1) and (3) must be rejected and all other
string must be accepted[1].

If you add an extra condition like (2) then you are talking about some
other problem which I'll call the PO-problem.  As I have said to
you (and to Newberry) *that* problem may well have decider.  If you have
not been talking about the halting problem all this time, then shame on
you.

You could repair the situation by proving that strings in category (2)
are either a decidable set (in which case we are back on track but the
theorem still stands) or that they are not a decidable set which, whilst
allowing a PO-problem decider to exist, would immediately show that the
halting theorem stands.  You see the theme?  It complicates things, but
does not alter the fundamentals of the theorem you object to.

So, are string of the form (2) a decidable set or not?

-- 
Ben.

Back to sci.logic | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-09 16:19 -0800
  Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 02:05 +0000
  Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-10 00:31 -0600
    Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 12:19 +0000
    Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-10 18:26 -0800
      Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-12 09:19 -0800
  Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-10 00:15 -0800
    Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-10 06:49 -0800
      Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 18:23 +0000
        Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-10 15:37 -0800
        Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-12 09:16 -0800
          Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-12 17:40 +0000
            Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-12 20:48 -0600
              Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-13 04:46 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 14:16 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-13 20:46 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 19:26 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 13:54 +0000
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 15:24 +0000
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 00:21 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 19:36 -0600
                Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 18:05 -0800
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 22:12 -0600
                Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 21:10 -0800
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-13 21:35 -0800
                Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 23:36 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:54 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:00 -0600
                Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-14 08:29 -0800
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 10:46 -0600
                Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-14 21:37 -0800
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-14 21:49 -0800
                Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:52 -0800
                Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:54 -0800
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 12:52 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 14:05 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 07:02 -0800
                Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-15 07:09 -0800
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:41 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 15:20 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:56 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:05 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:29 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:35 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:55 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 13:44 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 07:21 -0800
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 15:39 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 09:08 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 17:25 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 11:38 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 17:49 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 12:03 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 18:23 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 10:33 -0800
                Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-16 16:49 -0800
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 18:20 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 10:28 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 18:55 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 12:46 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 20:53 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 13:36 -0800
                Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-28 13:22 -0800
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-28 15:46 -0600
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 20:44 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 15:53 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:29 +0000
                Re: What is the deal with the Halting Theorem? Jim Burns <james.g.burns@att.net> - 2018-02-14 08:42 -0500
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:35 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 20:14 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 17:10 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 13:39 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 06:47 -0800
                Re: What is the deal with the Halting Theorem? Jim Burns <james.g.burns@att.net> - 2018-02-14 20:55 -0500
                Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-14 08:27 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:52 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:47 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 20:12 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 17:05 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 13:53 +0000
                Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 06:51 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 15:16 +0000
                Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-15 08:36 -0800
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:14 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:19 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:43 -0600
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 16:57 +0000
                Re: What is the deal with the Halting Theorem? bursejan@gmail.com - 2018-02-15 09:24 -0800
                Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:58 -0800
                Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-14 21:33 -0800
                Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:45 +0000
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 02:24 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 22:18 -0600
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 05:32 +0000
                Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 00:30 -0600
                Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 14:07 +0000
                Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-13 18:04 -0800
    Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-10 09:06 -0600
      Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 16:32 +0000

csiph-web