Re: Godel's Incompleteness and Nonmonotonic Logic

From: Student (jagasian_at_mailinator.com)
Date: 08/25/04 

Date: 25 Aug 2004 15:26:47 -0700

I haven't read anything about "Default Logic"... I will look into it.
Thanks for the references by the way.

> For default logic, inconsistency works pretty much the same as for
> classical logic: some theories are consistent, others are not.
> It's not difficult to find simple default theories that definitely have
> extensions. And i'm sure it works the same way for answer set programming.

So I guess my question is, is arithmetic (i.e. Peano's theory)
inconsistent when coded in answer set programming? Surely anybody can
write a messed up set of inference rules that is inconsistent... I
could just take A and -A as axioms in my logic program. However,
anything calling itself a logic shouldn't make arithmetic
inconsistent.

> The Goedel sentence contains a coding of a 'provability' predicate.
> For fixpoint systems such as default logic or asp, such a coding is not
> available. (The notion of 'provable' there is not the same as classical
> provability.)

So there these logics have no notion of proof? The fact that these
logics are used for computing things implies that there has to be some
notion of a proof of a formula. For example, answer set programming
language interpreters will tell me whether or not a query succeeds,
and the computation history which leads up to this answer can be
regarded as a proof.

Assuming that the answer set language I choose is Turing complete,
then it should be possible to code a predicate "isAProof( P, F )" that
is true when P is a structure representing a computation history
resulting in a positive answer for the query formula represented by
the structure F.

What am I missing? I understand that some ASP languages lack function
symbols, and are therefore not Turing complete, but in Chitta Baral's
text, he uses something called "AnsProlog"... which is Prolog with
Answer Set style negation - that should be Turing complete. Hence
writing an "isAProof" predicate like Godel uses should be
straightforward (though tedious).

Relevant Pages

  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... And i'm sure it works the same way for answer set programming. ... So there these logics have no notion of proof? ... Assuming that the answer set language I choose is Turing complete, ... symbols, and are therefore not Turing complete, but in Chitta Baral's ...
    (comp.lang.prolog)
  • Re: The Promise of Forth
    ... but that can simply reflect the difficulty with language. ... And when your language includes internal contradictions, ... But when you find contradictions in your ... But there are nonstandard logics that can accommodate this just as there are non-Euclidean geometries. ...
    (comp.lang.forth)
  • ESSLLI 2009 - Final Call for Participation
    ... The European Summer School in Logic, Language and Information ... Non-deterministic Multi-valued Logics - Arnon Avron and Beata Konikowska ... Foundations and main properties - Philippe de Groote and Sylvain Salvati (Introductory course, ... An introduction to minimalist grammars - Greg Kobele and Jens Michaelis (Advanced course, ...
    (comp.specification.z)
  • Re: The Promise of Forth
    ... logical contraditions, it's sloppy. ... but that can simply reflect the difficulty with language. ... But our common culture still holds logic in a superstitious regard it manifestly doesn't deserve. ... (there are many "logics" these days, just as there are many "geometries") ...
    (comp.lang.forth)
  • WoLLIC 2010 - Call for Papers
    ... WoLLIC 2010 17^th Workshop on Logic, Language, Information and Computation /* ... Each meeting includes invited talks and tutorials as well as contributed papers. ... It is sponsored by theAssociation for Symbolic Logic, the Interest Group in Pure and Applied Logics, the The Association for Logic, Language and Information, the European Association for Theoretical Computer Science ... Proposed contributions should be in English, and consist of a scholarly exposition accessible to the non-specialist, including motivation, background, and comparison with related works. ...
    (comp.specification.z)
Loading