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


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


4

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


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

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

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


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

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.


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