Information content in formal languages
Motivated by creating physical theories, formal languages S with variables are considered and a kind of distance between elements of the languages is defined by the formula d(x,y)= ℓ(x ∇ y) - ℓ(x) ∧ℓ(y), where ℓ is a length function and x ∇ y means the united theory of x and y. Actually we mainly consider abstract abelian idempotent monoids (S,∇) provided with length functions ℓ. The set of length functions can be projected to another set of length functions such that the distance d is actually a pseudometric and satisfies d(x∇ a,y∇ b) ≤ d(x,y) + d(a,b). We also propose a "signed measure" on the set of Boolean expressions of elements in S, and a Banach-Mazur-like distance between abelian, idempotent monoids with length functions, or formal languages.
READ FULL TEXT