Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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.
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
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