# Re: Goedel incompleteness

On Wed, Feb 21, 2018 at 7:52 PM, Bruno Marchal <marc...@ulb.ac.be> wrote:
>
>> On 21 Feb 2018, at 09:58, Telmo Menezes <te...@telmomenezes.com> wrote:
>>
>> Hi Bruno,
>>
>>> For example, prolog is a tiny subset of first order logic, and is Turing
>>> universal.
>>
>> I thought Prolog was more or less equivalent to first order logic.
>> What's missing?
>
> A program in Prolog is a finite set of universally quantified logical
> sentences (called Horne clause) with the shape
>
> A <- B1, B2, B3, … Bk, i.e.  ~B1 v ~B2 v ~B3, v… v ~Bk v A
>
> This admits a procedural interpretation: to satisfy the goal A, try to
> satisfy B1, then B2, then .. then Bk.
>
> First order logic is the full logic, with existential quantifier,
> conjunction, etc. Most proposition will not have procedural interpretation.
> In particular, if A is replaced by more than one formula, (disjunction) it
> will be provably not procedural.
>
> The Horne Clauses enforced the A above to be alone, which leads to the
> procedural interpretation through a unification of the variable process.

Ok, got it!

I only used Prolog in univ. I remember being excited by the idea of
logic programming, and then a bit disappointed that explicitly
procedural commands where necessary for anything remotely interesting.

Could it be possible to create some hyper-Prolog that is not
procedural, but instead used a search algo? A quick look at wikipedia
suggests that the problem here is that it is an NP-hard problem,
right? If so, I wonder if a fuzzy version (do-what-you-can) approach
could have value for AI...

Anyway, thanks for the explanation!

Telmo.

> Bruno
>
>
>
>
>>
>> Telmo.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Everything List" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to everything-list+unsubscr...@googlegroups.com.
>> To post to this group, send email to everything-list@googlegroups.com.
>> Visit this group at https://groups.google.com/group/everything-list.
>> For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Everything List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to everything-list+unsubscr...@googlegroups.com.
> To post to this group, send email to everything-list@googlegroups.com.
> Visit this group at https://groups.google.com/group/everything-list.
> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.