Today I Learned

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

Category Archives: language

111: Terminating Abstract Rewriting Systems

A terminating abstract rewriting system is one in which, given any starting element or term, there is no infinite sequence of rewritings which can be done on that starting element. That is, any sequence of rewritings on an element will eventually end in a ‘final’ rewritten form. Terminating ARSs are a subset of normal ARSs.


67: Confluence (Rewriting Systems)

A term a within a rewriting system (such as one in the lambda calculus) is confluent if, for any pair of terms b, c such that a \rightarrow b and a \rightarrow c (where x \rightarrow y means y is a reduct of x under 0 or more reductions), there exists a term d such that b \rightarrow d and c \rightarrow d. 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

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 \boldsymbol{n} representing the number n takes two arguments — a function f and a second argument to be passed to f — and returns the n-fold composition of f.


0 is represented as \boldsymbol{0} = \lambda f . \lambda x . x, which given any function f returns a function which simply returns x without applying f at all.

1 is represented as \boldsymbol{1} = \lambda f . \lambda x . f x, which given any function f returns a function which applies f once to x.

2 is represented as \boldsymbol{2} = \lambda f . \lambda x . f (f x), which given any function f returns a function which applies f twice to x.

3 is represented as \boldsymbol{3} = \lambda f . \lambda x . f (f (f x)), which given any function f returns a function which applies f three times to x.

27: 2 Undecideable Problems in Context-Free Grammars

A couple undecideable problems regarding context-free grammars:

  1. Equality: Given 2 distinct CFGs, do they produce/describe the same language?
  2. Disjointness: Again given 2 distinct CFGs, is there any string which can be produced by both?