Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
82 votes
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 ...
Jörg W Mittag's user avatar
31 votes
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 ...
Jörg W Mittag's user avatar
10 votes

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.
Caleb Stanford's user avatar
8 votes

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 ...
Yuval Filmus's user avatar
6 votes
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 ...
Derek Elkins left SE's user avatar
5 votes
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 ...
Joey Eremondi's user avatar
4 votes

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 ...
slebetman's user avatar
  • 699
2 votes

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 ...
beroal's user avatar
  • 781
2 votes
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 ...
ShyPerson's user avatar
  • 925
2 votes
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 (...
Derek Elkins left SE's user avatar
2 votes

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 ...
heatsink's user avatar
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 ...
Andrej Bauer's user avatar
  • 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 ...
Pseudonym's user avatar
  • 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 ...
Gaslight Deceive Subvert's user avatar
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 ...
François Bry's user avatar

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