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


Groups > sci.logic > #172381

Re: Necessary sequence of halt decider's inference chain

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups sci.logic
Subject Re: Necessary sequence of halt decider's inference chain
Date 2018-02-11 01:38 +0000
Organization A noiseless patient Spider
Message-ID <87r2psjof9.fsf@bsb.me.uk> (permalink)
References (1 earlier) <959bc654-e795-41a3-827f-fb0378bf7beb@googlegroups.com> <87y3k1ni4w.fsf@bsb.me.uk> <95384b56-12f1-4ef8-9bc1-9429b825b1d4@googlegroups.com> <873728l6li.fsf@bsb.me.uk> <462d45a8-b558-4365-b0b6-52ed7dfe9888@googlegroups.com>

Show all headers | View raw


grahamcooper7@gmail.com writes:

> On Sunday, February 11, 2018 at 10:20:45 AM UTC+10, Ben Bacarisse wrote:
>> grahamcooper7@gmail.com writes:
>> 
>> > On Saturday, February 10, 2018 at 10:28:33 PM UTC+10, Ben Bacarisse wrote:
>> >> grahamcooper7@gmail.com writes:
>> >> <snip>
>> >> > Halt is not a LANGUAGE decider, it is a PROGRAM decider.
>> >> 
>> >> I don't usually reply to your posts because I can't understand the
>> >> fractured comments, but this one looks plain wrong.  All deciders are
>> >> language deciders.  A halt decider is a decider for the language
>> >> (i.e. set of strings) that encode halting TM computations.
>> >> 
>> >> Posters here often play Humpty Dumpty with technical terms, but that
>> >> does not make them right.
>> >
>> > No a LANGUAGE DECIDER is computable.
>> 
>> Not all languages are decidable,
>> 
>> > https://en.wikipedia.org/wiki/Recursive_language
>> 
>> as the text at that link correctly sates.
>
> Which of these is TRUE?
>
> 1/ HALT IS A DECIDER
> 2/ HALT IS NOT A DECIDER
  3/ HALT IS JUST A NAME
  4/ WHAT'S HALT?
  5/ DO I HAVE TO GUESS?

> there exists a Turing machine that, when presented with any finite
> input string, halts and accepts if the string is in the language

for any recursively enumerable (AKA semi-decidable) language, yes.

-- 
Ben.

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


Thread

Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-09 22:20 -0800
  Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 12:28 +0000
    Re: Necessary sequence of halt decider's inference chain Pete Olcott <Pete@NoEmail.address> - 2018-02-10 09:15 -0600
      Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 16:44 +0000
        Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-10 15:16 -0800
    Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-10 15:27 -0800
      Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-11 00:20 +0000
        Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-10 17:21 -0800
          Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-11 01:38 +0000

csiph-web