Re: Goedel incompleteness

```> On 23 Feb 2018, at 14:53, Telmo Menezes <te...@telmomenezes.com> wrote:
>
> On Wed, Feb 21, 2018 at 7:52 PM, Bruno Marchal <marc...@ulb.ac.be
> <mailto: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.```
```
Yes, pure prolog, without the “cut” (excavation point) will very often never
stop. So they have added the cut which forces the program to stop when he found
what it was searching for. Then, the order of the clause should not been taken
into account, but everyone knows that the order will make a program
efficacious, or terribly slow.

>
> Could it be possible to create some hyper-Prolog that is not
> procedural, but instead used a search algo?

Searching is natural in prolog, but I guess you mean a more general search
algorithm. The literature is full of attempts and generalisation of prolog, but
I have stop to follow this since some time. There is always that frustrating
trade-off between being logically acceptable, with a semantic related to logic,
or being efficacious. This is a bit true for all programming language, but some
language are better suited. Lisp is far more better for this. It has the Church
Rosser properties which makes the lambda expression converging to the same
solution when they have the same semantics, which is not the case for Prolog
and logic programming. In fact, logic is too much a non procedural thing in
general.
Yet I love prolog, because it is extremely useful to write short powerful
program. You can do meta programming easily, as an interpreter in Prolog can be
written in two or three lines (it inherits in that case the unification
algorithm of its host), or a dozen of lines (including the unification
procedure, which is just a form of pattern matching, and search in the
data-base.

> A quick look at wikipedia
> suggests that the problem here is that it is an NP-hard problem,
> right?

Yes. Even without variables. That is like SAT (the satisfaction of a
propositional formula).

> If so, I wonder if a fuzzy version (do-what-you-can) approach
> could have value for AI…

I have developed a fuzzy version of prolog, actually based on Philippe Smets
(the main creator of IRIDIA)  “transfer belief model”, to help in some search
in giant protein databanks (when I was working for Monsanto (!)). With a friend
we have taken some years to compile it in ADA. He told me that a subroutine we
created has actually been implemented in all chips (a sort of hash-table data
retrieving procedure! I am not sure if this can have value in AI, or perhaps I
do think a fuzzy prolog can have value, but I am not sure if this is exploited
today. At that time, I heard about a Japanese firm which built a fuzzy chip for
logic programming for a “clever” cleaning machine. I believe more in neural
nets, especially if it is cycling, and with ¨many¨hidden layers. You can be
sure that when such machine will think, we will not understand how they do it,
and such machine will be beyond theoretical analysis. With computers, either we
massacre the semantics, and they will be efficacious, but often wrong and a bit
stupid in the human way, or we will built docile slaves. It is about the same
with the education of kids. We will forever remains in-between security and
liberty ...

>
> Anyway, thanks for the explanation!

Best!

Bruno

>
> 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
>>> 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
>> 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
> 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