Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > sci.logic > #165566 > unrolled thread
| Started by | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| First post | 2017-10-23 09:06 -0700 |
| Last post | 2017-10-27 21:50 +0100 |
| Articles | 11 — 4 participants |
Back to article view | Back to sci.logic
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
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
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2017-10-23 09:06 -0700 |
| Subject | Re: Gödel’s 1931 Incompleteness Theorem summed as a single line of Minimal Type Theory |
| Message-ID | <eda75d70-8fd0-4573-9609-65f044b598dc@googlegroups.com> |
On Sunday, October 22, 2017 at 3:00:30 PM UTC-4, Pete Olcott wrote: > http://liarparadox.org/index.php/2017/10/22/godels-1931-incompleteness-theorem-summed-as-a-single-line-of-minimal-type-theory/ > > > > Gödel’s 1931 Incompleteness Theorem > > http://jacqkrol.x10.mx/assets/articles/godel-1931.pdf > > > > Gödel’s 1931 Incompleteness Theorem summed as a > single line of Minimal Type Theory > > G @ ∃X ~Provable(X, G) > > (1) The above sentence says that it is not provable. > > (2) The above sentence is indeed not provable. > > (3) However the above sentence is not true (see graph below). > > > > Sentence translated into a Directed Acyclic Graph by the MTT > compiler: > > [00] ROOT (01) > > [01] G (02)(04) > > [02] THERE_EXISTS (03) > > [03] X > > [04] NOT (05) > > [05] Provable (03)(01) // cycle indicate > infinite evaluation loop Truth is not recursively enumerable. F.I. C-B
[toc] | [next] | [standalone]
| From | peteolcott <peterolcott2@gmail.com> |
|---|---|
| Date | 2017-10-23 09:42 -0700 |
| Message-ID | <f71a62df-983c-47b0-b1f9-020a890e7894@googlegroups.com> |
| In reply to | #165566 |
On Monday, October 23, 2017 at 11:06:06 AM UTC-5, Charlie-Boo wrote: > On Sunday, October 22, 2017 at 3:00:30 PM UTC-4, Pete Olcott wrote: > > http://liarparadox.org/index.php/2017/10/22/godels-1931-incompleteness-theorem-summed-as-a-single-line-of-minimal-type-theory/ > > > > > > > > Gödel’s 1931 Incompleteness Theorem > > > > http://jacqkrol.x10.mx/assets/articles/godel-1931.pdf > > > > > > > > Gödel’s 1931 Incompleteness Theorem summed as a > > single line of Minimal Type Theory > > > > G @ ∃X ~Provable(X, G) > > > > (1) The above sentence says that it is not provable. > > > > (2) The above sentence is indeed not provable. > > > > (3) However the above sentence is not true (see graph below). > > > > > > > > Sentence translated into a Directed Acyclic Graph by the MTT > > compiler: > > > > [00] ROOT (01) > > > > [01] G (02)(04) > > > > [02] THERE_EXISTS (03) > > > > [03] X > > > > [04] NOT (05) > > > > [05] Provable (03)(01) // cycle indicate > > infinite evaluation loop > > Truth is not recursively enumerable. > > F.I. > > C-B Prolog is able to express Truth in a recursively enumerable way.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2017-10-23 21:11 +0100 |
| Message-ID | <87zi8hipzj.fsf@bsb.me.uk> |
| In reply to | #165578 |
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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2017-10-23 15:32 -0500 |
| Message-ID | <UoCdne51A-l3zHPEnZ2dnUU7-TXNnZ2d@giganews.com> |
| In reply to | #165596 |
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? -- Defining Tarski’s ∀x True(x) ↔ φ(x) True(x) ↔ ∃y Provable(y, x)
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2017-10-24 01:36 +0100 |
| Message-ID | <87inf5idp3.fsf@bsb.me.uk> |
| In reply to | #165599 |
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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2017-10-23 20:49 -0500 |
| Message-ID | <9pydnYZj4tqIAXPEnZ2dnUU7-YHNnZ2d@giganews.com> |
| In reply to | #165610 |
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. 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. Prolog is unable to exhaustively list all of the members of the set of sentences based on its axioms that evaluate to true? It seems to me that Prolog could exhaustively list its finite set of atomic true sentences. -- Defining Tarski’s ∀x True(x) ↔ φ(x) True(x) ↔ ∃y Provable(y, x)
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2017-10-24 12:01 +0100 |
| Message-ID | <8760b4izde.fsf@bsb.me.uk> |
| In reply to | #165613 |
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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2017-10-24 08:43 -0500 |
| Message-ID | <LJ-dnev0QKbs3nLEnZ2dnUU7-W3NnZ2d@giganews.com> |
| In reply to | #165628 |
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 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. -- Defining Tarski’s ∀x True(x) ↔ φ(x) True(x) ↔ ∃y Provable(y, x)
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2017-10-25 02:33 +0100 |
| Message-ID | <87k1zk2eq4.fsf@bsb.me.uk> |
| In reply to | #165633 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2017-10-27 10:49 -0500 |
| Message-ID | <p4KdnQ0woqMdyG7EnZ2dnUU7-Y_NnZ2d@giganews.com> |
| In reply to | #165685 |
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. -- Defining Tarski’s ∀x True(x) ↔ φ(x) True(x) ↔ ∃y Provable(y, x)
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2017-10-27 21:50 +0100 |
| Message-ID | <87a80ciad9.fsf@bsb.me.uk> |
| In reply to | #165830 |
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.
[toc] | [prev] | [standalone]
Back to top | Article view | sci.logic
csiph-web