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


Groups > sci.logic > #165841

Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups sci.logic, comp.theory
Subject Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory
Date 2017-10-27 21:50 +0100
Organization A noiseless patient Spider
Message-ID <87a80ciad9.fsf@bsb.me.uk> (permalink)
References (6 earlier) <9pydnYZj4tqIAXPEnZ2dnUU7-YHNnZ2d@giganews.com> <8760b4izde.fsf@bsb.me.uk> <LJ-dnev0QKbs3nLEnZ2dnUU7-W3NnZ2d@giganews.com> <87k1zk2eq4.fsf@bsb.me.uk> <p4KdnQ0woqMdyG7EnZ2dnUU7-Y_NnZ2d@giganews.com>

Cross-posted to 2 groups.

Show all headers | View raw


Pete Olcott <Pete@NoEmail.address> writes:

> On 10/24/2017 8:33 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 10/24/2017 6:01 AM, Ben Bacarisse wrote:
>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>
>>>>> On 10/23/2017 7:36 PM, Ben Bacarisse wrote:
>>>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>>>
>>>>>>> On 10/23/2017 3:11 PM, Ben Bacarisse wrote:
>>>>>>>> peteolcott <peterolcott2@gmail.com> writes:
>>>>>>>>
>>>>>>>>> On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote:
>>>>>>>> <snip>
>>>>>>>>>> Truth is not recursively enumerable.
>>>>>>>> <snip>
>>>>>>>>> Prolog is able to express Truth in a recursively enumerable way.
>>>>>>>>
>>>>>>>> Prolog has no choice -- that's the best is can do.  However, the set of
>>>>>>>> true sentences of any interesting axiomatic system is not an R.E. set.
>>>>>>>>
>>>>>>>
>>>>>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>>>>>> Your statement depends upon the assumption that the Halting Problem
>>>>>>> proof is correct?
>>>>>>
>>>>>> No.  I don't know which proof you are thinking of but it's correctness
>>>>>> or otherwise has no bearing on the validity of the statement it may or
>>>>>> may not prove.
>>>>>>
>>>>>
>>>>> OK I misread the link.
>>>>
>>>> I'm not sure that's the problem.  From what you write, I think you've
>>>> misunderstood the ideas.
>>>>
>>>>> There is an algorithm that enumerates the members of S. That means
>>>>> that its output is simply a list of the members of S: s1, s2, s3,
>>>>> ... . If necessary, this algorithm may run forever.
>>>>
>>>> You should make it clear when you are quoting material.  When something
>>>> is in your own words, your readers can use that to try ro work out if
>>>> you know what you are talking about.  The above is just a quote from a
>>>> website, so there is no way to know how much of it you understand.
>>>>
>>>>> Prolog is unable to exhaustively list all of the members of the set of
>>>>> sentences based on its axioms that evaluate to true?
>>>>
>>>> Prolog is a programming language.  If that does not answer your
>>>> question, you are very, very confused.
>>>>
>>>>> It seems to me that Prolog could exhaustively list its finite set of
>>>>> atomic true sentences.
>>>>
>>>> Did you mean to say that the Prolog system could list any program's
>>>> finite set of facts?
>>>>
>>>> That seems unlikely for two reasons.  First, it's a boring fact (a
>>>> simple subset of the program's sentences constitute such a list), and
>>>> second, it looks like you think the last two sentences are talking about
>>>> the same things.  It seems likely that you don't know much about Prolog
>>>> so the words you use end up being muddled.
>>>>
>>>
>>> You said: Prolog is able to express Truth in a recursively enumerable way. -
>>
>> I said it can do no other.  Since it's a programming language everything
>> it can "express" must be R.E.  One might like some of these things to be
>> recursive, but we often settle for R.E.
>>
>> As I said above, the set of true sentences of any interesting axiomatic
>> system is /not/ R.E. so whatever it is that Prolog expresses, it is not
>> truth as Tarski would have it.
>>
>>> I did some more research.
>>>
>>> https://en.wikipedia.org/wiki/Recursively_enumerable_set
>>> Every recursive set is recursively enumerable, but it is not true that
>>> every recursively enumerable set is recursive. For recursive sets, the
>>> algorithm must also say if an input is not in the set – this is not
>>> required of recursively enumerable sets.
>>>
>>> Prolog is able to determine and report whether or not an expression is
>>> provably true (within its specified axioms) for the exhaustive set of
>>> Prolog expressions. (A set of Prolog axioms define a language).
>>>
>>> Prolog is able to determine and report whether or not an expression is
>>> not provably true (within its specified axioms) for the exhaustive set
>>> of Prolog expressions.
>>>
>>> Thus for a set of axioms defining a language in Prolog, Prolog can
>>> determine whether or not any finite string is in the set of provably
>>> true Prolog expressions or not in the set of provably true Prolog
>>> expressions, thus making this set of Prolog axioms a recursive
>>> language with respect to provably true.
>>
>> Pick an unsolved arithmetic conjecture (I suggest the Goldbach
>> conjecture), write it out as a Prolog expression and find out the
>> answer!
>>
>> Hmm... that does not seem right...  Maybe
>>
>> (A) No one has thought of this yet.  Quick, do it now before I publish
>> a paper solving 30 arithmetic conjectures before you do.
>>
>> (B) Prolog can't even express simple arithmetic facts as expressions to
>> be proved.  If so, what use is it's notion of "provable", especially to
>> you?
>>
>
> Prolog can express simple arithmetic facts as expressions to be proved
> and conventional counter-examples to the contrary can be detected and
> reported as erroneous by unify_with_occurs_check/2.

Woosh.

-- 
Ben.

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


Thread

Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Charlie-Boo <shymathguy@gmail.com> - 2017-10-23 09:06 -0700
  Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory peteolcott <peterolcott2@gmail.com> - 2017-10-23 09:42 -0700
    Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-23 21:11 +0100
      Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-23 15:32 -0500
        Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-24 01:36 +0100
          Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-23 20:49 -0500
            Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-24 12:01 +0100
              Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-24 08:43 -0500
                Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-25 02:33 +0100
                Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Pete Olcott <Pete@NoEmail.address> - 2017-10-27 10:49 -0500
                Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-27 21:50 +0100

csiph-web