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


Groups > sci.logic > #165685

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-25 02:33 +0100
Organization A noiseless patient Spider
Message-ID <87k1zk2eq4.fsf@bsb.me.uk> (permalink)
References (4 earlier) <UoCdne51A-l3zHPEnZ2dnUU7-TXNnZ2d@giganews.com> <87inf5idp3.fsf@bsb.me.uk> <9pydnYZj4tqIAXPEnZ2dnUU7-YHNnZ2d@giganews.com> <8760b4izde.fsf@bsb.me.uk> <LJ-dnev0QKbs3nLEnZ2dnUU7-W3NnZ2d@giganews.com>

Cross-posted to 2 groups.

Show all headers | View raw


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?

(C) You are wrong.

Any ideas?

-- 
Ben.

Back to sci.logic | Previous | Next — Previous in thread | Next 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