# Tag Info

Accepted

### Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

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 ...
• 6,150
Accepted

### What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?

Very good explanations of programming paradigms and the programming concepts from which those paradigms are built are found in Peter van Roy's works. Especially in the book Concepts, Techniques, and ...
• 6,150

### What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?

Check out the book Types and Programming Languages (TAPL) by Benjamin Pierce. This is an excellent introduction to the fundamental concepts of the field of programming languages.
• 7,088

### What is the sequence of numbers for N = 6?

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 ...
• 277k
Accepted

### Generalization of Horn clauses in logic programming?

$\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 ...
• 12.1k
Accepted

### What is the difference between control flow and control logic?

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 ...
• 29.8k

### Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

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

### What is Herbrand interpreration and model?

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 ...
• 781
Accepted

### What algorithms for unification over (multidimensional) array terms?

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 ...
• 925
Accepted

### Is Unification "an Implementation of Existential Quantification"?

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 (...
• 12.1k

### What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?

Teach yourself how to make a compiler and learn about computer architecture/digital design. Knowing that material will distinguish you from beginners very easily. This free course material from the ...
• 21
1 vote
Accepted

### Is it possible to encode contradictory horn clauses without goal clauses?

If you only allow propositional letters p, q, r, ... and Horn clauses of the form ...
• 30.5k
1 vote

### How does Warrens Abstract Machine work?

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 ...
• 22.2k
1 vote

### Pseudocode for constructing control flow graph

To create a CFG you begin with an Abstract Syntax Tree (AST). So I assume you have an AST available. The first step is to collect the nodes in the tree into basic blocks. This step is optional but ...
1 vote

### What makes PROLOG Turing-complete?

Completing the excellent answer by @Pseudonym and referring to your last question "Are function symbols themselves Turing complete?". You probably mean: Can a language made only of function symbols ...

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