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


13

Term rewriting is a rewriting formalism. Starting with a term we rewrite the term according to the term rewriting rules until a normal form is found. Unification is finding a solution (substitution with specific properties) to a problem (a pair of terms). Term rewriting uses a notion called "pattern matching". What you probably meant is: what is the ...


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

Here is one possible algorithm: If $N = 0$, output the empty string. If $N = 1$, output "0 1". If $N = 2$, output "0 2 2 3". If $N = 3$, output "0 2 4 3 4 5". If $N = 4$, output "0 2 4 6 4 5 6 7". If $N = 5$, output "0 2 4 6 8 5 6 7 8 9". Otherwise, output the empty string. Now, this is probably not the answer they were expecting, but it's perfectly valid. ...


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

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


2

Given the usual substitution function $[x/y]$ s.t. $M[x/y]$ is the result of substituting all free occurrences of '$y$' with '$x$' in $M$, your desired function can be defined as follows: $M [x//y] =_{df} M[x'/y][y/x][x/x']$ provided $x'$ doesn't occur in $M$. Example. Let $C = m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)$. Then: \begin{align*} D &= C~[Q~//~R]\\ ...


2

I found out that this could not be done natively in ASP (or at least in the solvers that I am using). So the abduction theory needs to be modeled with the problem in order to derive expected results. This is an example that demonstrates how it can be done. I haven't had the time to thoroughly test its efficiency but it works for some basic examples. ...


2

It's possible you're paraphrasing me. I've certainly said things similar to that e.g. here. A more precise statement would be that existential quantification in logic programming languages is (typically) handled by introducing a unification variable. To perform existential introduction, you need to have a term $t$. The rule looks like: $$\dfrac{\Gamma\vdash ...


2

Control flow is oriented around the idea of imperative statements. What is the computer doing at this given time? What will it do next? What actions should it perform? Declarative programming abstracts this away (or at least tries to). You're program is now not a set of instructions for the computer to follow, but a sort of specification for the problem. In ...


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

Herbrand models have special domains. The domain of every Herbrand model for $S$ (which is a set of formulas of $L$) is the Herbrand universe $U_L$ for $L$. The set $U_L$ cannot be $\{0, 1\}$, it has a totally different form, see the definition of Herbrand universe in Chapter 1 “Preliminaries”, §3 “Interpretations and models”. The set $U_L$ can contain $p(a)$...


1

By way of context, I'll assume the goal is to do unification in classical first-order logic in a fixed language $\mathscr{L}$. (Formatting and other corrections welcome.) Briefly, you can treat arrays as terms and multidimensional arrays as arrays of arrays. You'll also introduce a new term symbol that doesn't occur in $\mathscr{L}$. So for example, if you ...


1

My suggestion is in preparation for this course, to try and read some beginners guides on pure functional programming language. Having some practical experience actually doing some functional programming before learning the theory could be beneficial. I learned functional programming with F# which might not be the best idea, since it is a hybrid language ...


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.


1

See http://www-ps.informatik.uni-kiel.de/kics2/lib/Findall.html: it says IO based approach is deprecated and the prefferred way not is Curry's SetFunctions module, This new design does away with IO-wrapped return values and has other means to avoid leaking indeterminism and referential non-transparency into the pure-FP land.


1

The reasons for using the IO monad appear to be described in Braßel and Huch and Hanus, 2004, but I cannot find a clear reason given for using a list instead of a set. I guess it is so the list can be elaborated lazily. It seems that the approach described in the 2007 paper was unsatisfactory for some reason (I don't know why), because KiCS2 has gone back ...


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