# Today I Learned

Some of the things I've learned every day since Oct 10, 2016

## Category Archives: language

## 67: Confluence (Rewriting Systems)

December 18, 2016

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

## 49: Church Numerals

November 28, 2016

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

Examples:

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 .

## 27: 2 Undecideable Problems in Context-Free Grammars

November 6, 2016

Posted 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?

## Recent Comments