Hot answers tagged

82

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that. A list is not a natural number, and list intersection is not a function on natural numbers. Note: it is, of course, possible to encode lists as natural numbers, which would then make list intersection a ...


22

It's a fairly reliable rule of thumb that Turing-completeness depends on the ability to construct answers or intermediate values of unrestricted "size" and the ability to loop or recurse an unrestricted number of times. If you have those two things, you probably have Turing-completeness. (More specifically, if you can construct Peano arithmetic, then you ...


9

If you understand Prolog then you're probably fine. The jargon in Prolog-land is not as fixed as you'd expect, because we really only have three things to refer to, with a dozen or more pieces of jargon to use on. These are my working definitions arrived at from reading books and reading/answering questions about Prolog on Stack Overflow. I may have a ...


8

A horn clause is a disjunction with at most one positive literal, e.g. \begin{align} \lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n \lor Y \end{align} The implication $X \rightarrow Y$ can be written as disjunction $\lnot X \lor Y$ (proof by truth table). If $X = \lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n $, then $\lnot X$ is equivalent to $...


6

$\lambda$Prolog is a logic programming language based on a much richer logic than Prolog. In particular, the formulas that constitute its language are (higher-order) hereditary Harrop formulas. Horn clauses are a pallid fragment of that. The enabling concept for $\lambda$Prolog is the notion of a uniform proof, and additionally switching to an intuitionistic ...


4

how widely used ASP or other declarative languages are You can see the activity of Prolog which I think is the most common ASP programming language: SWI-Prolog Package Downloads: 483 downloads (not sure the interval), 239 packages. Compare to Node.js Package Downloads underscore.js has 139,326 weekly downloads. Over 350k packages. Just based on that, ...


4

Logic programming with substructural logics has been studied, starting in the second half of the 90's. I am not an expert, but I can probably provide enough references to get you going. There is Dale Miller's Lolli, a programming language for linear logic programming. Major research was carried out by Frank Pfenning and his coworkers and students. For ...


4

First, all this "worlds" stuff is unnecessary. It's a notion used in some semantics of modal logic. You don't need it to understand modal logic, let alone non-modal logics. This isn't to say it can't be useful, it's just that "worlds" is not some fundamental constituent of logic or their semantics, and, regardless, is not typically used outside of modal ...


4

Expressiveness is not a criteria of being Turing complete. Computability is. If Pure Prolog is Turing Complete then Pure Prolog can compute the intersection between two sequential sets. You may not be able to express this computation. It may take you several lines of code or even several pages. You may not be able to use the data structure you prefer. You ...


3

There are some rules of thumb I follow when writing prolog. Two of them are: Use dif instead of \=. From the reference manual: "To make your programs work correctly also in situations where the arguments are not yet sufficiently instantiated, use dif/2 instead." Avoid unnecessary variables and always get rid of the "Singleton variables: [X]&...


3

It sounds like you have the impression that there are some rules on what languages you are allowed to define. There are no such rules. You can define whatever language you want. You can do whatever what you want -- you're not required to do anything (there are no language police who will come arrest you for failing to prove some theorem about it). ...


3

Read about AI winters and more on the history of AI. In the 1980s, symbolic AI was dominant. In that time, expert systems proliferated. Many of them have been coded in Prolog. Today, we still have (in some areas) business rules systems and business rules engines, and the business rules approach used in business rule management systems, which IMHO are the ...


3

Prolog does not support arbitrary first-order logic but only a fragment of it known as Horn clauses. These are statements of the form $$\forall x_1, \ldots, x_n \,.\, P(x_1, \ldots, x_n) \Rightarrow q(x_1, \ldots, x_n)$$ where $P$ is built from atomic predicates and conjunctions, and $q$ is an atomic predicate. Not every statement in logic can be converted ...


3

The order of clauses matters in Prolog: they are tried in order. So, the first clause is always tried first, and the second one would only be considered after the first clause fails. As you discovered, this never happens because the first gets stuck in a loop. If Prolog used a breadth-first resolution algorithm, the clause order would not matter (but it ...


3

I doubt you find mainstream languages with HKTs simpler than Scala and Haskell. And even those don't implement HKTs fully. Tim Sheard's Ωmega and some interactive proof assistants have HKTs too. Chapters 29 and 30 of Types and Programming Languages show exactly how HKTs are added to a typing-system and how to do type-checking with HKTs. Why not ...


2

I think the computation model of Prolog is the SLDNF resolution of Horn clauses. Prolog is actually very procedural. Kowalski 1974: "The interpretation of predicate logic as a programming language is based upon the interpretation of implications [...] as procedure declarations [...]" (emphasis mine) https://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf (...


2

No. Every path is a tree, but not every tree is a path. Therefore, the minimum spanning path might be more expensive than the minimum spanning tree. If you work through some examples you should be able to find an explicit counterexample. I'll let you have the joy of finding it on your own.


2

An interpreter for a logic programming language is usually based on a proof systems that has been proven sound and complete, like definite clause resolution that Prolog uses. Of course you could implement that in any way you like, but if that implementation itself uses some declarative form of programming, it may be easier to argue that your implementation ...


2

I just walked 354 students, mostly SE's, through installing SWI-Prolog. Had about a dozen install issues. Most found the process fairly easy. I'll admit, if SWI-Prolog had 100x as many users the install would get more polished. But nobody is shying away because the install is too hard. As for packs, to install a pack you query pack_install(my_pack). That'...


2

If you can convert them to Horn clauses, you can convert them to Prolog. If you can't convert them to Horn clauses, I don't think you can convert them to Prolog. So, convert them to Horn clauses first, and then see the answer to this question: Horn clause to Prolog


2

As expressed, this looks like a homework question, and there is missing information, specifically, the definition of sublist/2. Having said that, you did ask a good computer science question, namely, what exactly is "resolution" in Prolog and, more to the point, why is it called "resolution" in the first place. If you're not used to ...


1

One issue is efficiency. Having different predicates means more efficient compilation. It also allows for separate compilation, using modules, which is important for even medium-sized programs. Additionally, using the WAM terminology, you will end up with a lot more choicepoints than you expect. Modern compilers go to a lot of trouble to perform ...


1

This may be a question that's too broad to cover here. The WAM covers a lot of Prolog-specific capabilities (e.g. unification, nondeterminism, the cut) that other abstract machines do not, and its design is also quite subtle in its details (e.g. garbage collection on backtracking is designed into the machine). There is a reason why the WAM Book is 130 pages ...


1

While @DerekElkins provided a proof theory perspective on Prolog, I want to provide a model theory perspective and contest the claim that no “satisfaction” is involved. Prolog is connected to logic via its denotational semantics [1]. For example, the Prolog rule in another answer p(X,Y) :- q(X,Z), r(W); t(Y). is expressed in traditional logic notation as ...


1

If your intention is just to check if your translation from English to first order logic is correct, then I think you could put both your answer and the correct answer that is different from yours in CNF using Herbrand's theorem and compare if they are equal.


1

So, there are two possibilities, depending on how complex your statements are. If your statements are relatively simple, then there's a good chance they fit in what is decidable with Satisfiability Modulo Theories. It's basically a way of taking a SAT solver and integrating it with a solver for a specific theory, for example, theory of linear arithmetic. ...


1

I use predicate to denote p(X) (just like this ). A clause is a disjunction of literals: both facts and rules are (Horn) clauses (Horn) clauses . See the Horn clause wiki link on how to read Prolog rules and on what is a goal (short answer goal=query). Hope that helps.


Only top voted, non community-wiki answers of a minimum length are eligible