Some of the things I've learned every day since Oct 10, 2016
Category Archives: language
December 18, 2016Posted by on
A term within a rewriting system (such as one in the lambda calculus) is confluent if, for any pair of terms such that and (where means is a reduct of under 0 or more reductions), there exists a term such that and . If every term in a system is confluent, the system itself is said to be confluent.
Systems which are both confluent and terminating are especially nice, because any sequence of reductions can be applied to a given term with the resulting irreducible reduct being the same.
November 28, 2016Posted by on
In Church encoding, an encoding system using lambda calculus, the Church numerals are the representation of the natural numbers. The distinguishing feature of the Church numerals is that the natural numbers are not treated as a primitive type, as they would typically be, but are simply represented by higher-order functions. Each higher-order function representing the number takes two arguments — a function and a second argument to be passed to — and returns the -fold composition of .
0 is represented as , which given any function returns a function which simply returns without applying at all.
1 is represented as , which given any function returns a function which applies once to .
2 is represented as , which given any function returns a function which applies twice to .
3 is represented as , which given any function returns a function which applies three times to .
November 6, 2016Posted by on
A couple undecideable problems regarding context-free grammars:
- Equality: Given 2 distinct CFGs, do they produce/describe the same language?
- Disjointness: Again given 2 distinct CFGs, is there any string which can be produced by both?