Böhm tree
Encyclopedia
The concept of a Böhm tree arises in lambda calculus
, a discipline within mathematical logic
and computer science
. It is named after Corrado Böhm
.
If one considers lambda-terms
as trees, the set of Böhm trees is the set of all possible trees built by taking a lambda-term and replacing zero, one or more subterms by a special symbol
, and allowing for infinite trees. It can be proved that Böhm trees are a model of lambda-calculus.
Böhm trees can be ordered by the following relation :
if 
can be obtained out of 
by replacing some occurrences of 
by subtrees. Clearly, every Böhm tree 
is such that 
. The set of Böhm trees with this ordering is a complete partial order
.
Informally, starting from a lambda-term and reducing it to try to reach a normal form using the leftmost outermost evaluation strategy
, we can use Böhm trees as we go as a way to represent the information obtained so far about the normal form (with the
indicating the subterms which still need to be reduced). If the lambda-term isn't strongly normalizing, the leftmost outermost evaluation strategy will fail to terminate, and the interpretation of the lambda-term will be an infinite Böhm tree.
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, a discipline within mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. It is named after Corrado Böhm
Corrado Böhm
Corrado Böhm , Professor Emeritus at the University of Rome "La Sapienza", is a computer scientist known especially for his contributions to the theory of structured programming, constructive mathematics, combinatory logic, lambda-calculus, and the semantics and implementation of functional...
.
If one considers lambda-terms
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
as trees, the set of Böhm trees is the set of all possible trees built by taking a lambda-term and replacing zero, one or more subterms by a special symbol
, and allowing for infinite trees. It can be proved that Böhm trees are a model of lambda-calculus.Böhm trees can be ordered by the following relation :
if can be obtained out of by replacing some occurrences of by subtrees. Clearly, every Böhm tree is such that . The set of Böhm trees with this ordering is a complete partial orderComplete partial order
In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...
.
Informally, starting from a lambda-term and reducing it to try to reach a normal form using the leftmost outermost evaluation strategy
Evaluation strategy
In computer science, an evaluation strategy is a set of rules for evaluating expressions in a programming language. Emphasis is typically placed on functions or operators: an evaluation strategy defines when and in what order the arguments to a function are evaluated, when they are substituted...
, we can use Böhm trees as we go as a way to represent the information obtained so far about the normal form (with the
indicating the subterms which still need to be reduced). If the lambda-term isn't strongly normalizing, the leftmost outermost evaluation strategy will fail to terminate, and the interpretation of the lambda-term will be an infinite Böhm tree.