Initially one had results showing that certain terms were not interconvertible e. See below for more detailed discussion of consistency. Its relation to programming languages was also clarified. It does not have the right shape: it is simply a variable, not an application term whose left-hand side is an abstraction term.
We thus have:. There are infinitely many reduction sequences commencing with this term:. One can combine notions of reduction. Once we have defined a reduction strategy, it is natural to ask whether one can improve it. This is the question of optimality. Defining optimal strategies and showing that they are optimal is generally considerably more difficult than simply defining a strategy.
For more discussion, see Barendregt, chapter Various approaches are available. In the case of the reflexivity rule, nothing is written above the horizontal rule. Through this rule we can also see that all terms are effectively functions. The question might not be well-posed. Intuitively, a logic is inconsistent if it permits us to derive too much.
Church were indeed inconsistent; see Barendregt, , appendix 2 or Rosser, for a discussion. The two terms are obviously intuitively distinct. The proof of this theorem is quite non-trivial and is well-beyond the scope of this entry. To prove the theorem, it is sufficient to produce one underivable equation. Scott; other models were found later. See, for example, Hyland, for details. The language of combinatory logic is built up from combinators and variables.
The names are not arbitrary. The principal reduction relations are:. Here is one translation; it is defined recursively. We can give but a glimpse of combinatory logic; for more on the subject, consult the entry on combinatory logic.
In many contexts of reasoning and computing it is natural to distinguish between different kinds of objects. The way this distinction is introduced is by requiring that certain formulas, functions, or relations accept arguments or permit substitution only of some kinds of objects rather than others. Regimenting objects into types is also the idea behind the passage from unsorted, or one-sorted first-order logic to many-sorted first-order logic. See Enderton, and Manzano, for more about many-sorted first-order logic.
How do these terms function as truth values? This section sketches the beginnings of the development of the subject known as type theory. We are interested in developing type theory only so far as to make the so-called Curry-Howard-de Bruijn correspondence visible. A more detailed treatment can be found in the entry on type theory ; see also Hindley, and Barendregt, Dekkers, Statman, Type theory gives us the resources for making this intuitive argument more precise. Given an assignment of types to term variables, one has the typing rules:.
The above two rules define the assignment of types to applications and to abstraction terms. The set of terms of type theory is the set of terms built up according to these formation rules.
See Hindley Table of principal types for a more extensive listing. The language used is meager: there are only propositional variables and implication; there are no other connectives. Could it really be that the types assigned to formulas, when understood as logical formulas, are valid? The correspondence can be seen when one identifies intuitionistic validity with derivability in a certain natural deduction formalism.
For a proof of these two theorems, see Hindley, , chapter 6. The correspondence expressed by the previous two theorems between intuitionistic validity and typability is known as the Curry-Howard-de Bruijn correspondence, after three logicians who noticed it independently. One can extend the correspondence to other connectives and to quantifiers, too, but the most crisp correspondence is at the level of the implication-only fragment.
For details, see Howard, Various representations of natural numbers are available; this representation is but one. This shows that the model is exactly as expressive as other models of computing, such as Turing machines and register machines. This is done in the case of various property theories , formal theories for reasoning about properties as metaphysical objects Bealer , Zalta , Menzel , , and Turner This kind of theory is employed in certain metaphysical investigations where properties are metaphysical entities to be investigated.
This approach contrasts with the approach above. For further discussion, see Orilia, The properties and relations described by the theories of Bealer, Zalta, Menzel, and Turner have exactly this characteristic. In other words, the theories are hyperintensional property theories. Introduction 1.
Syntax 2. Reduction 4. Extensions and Variations 8. Applications 9. Abramsky, D. Gabbay, T. Maibaum, and H. Barendregt eds. Cutland, Nigel J. Enderton, Herbert B.
Furth trans. Kleene, Stephen C. Hindley, J. Roger and Jonathan P. Howard, William A. Hindley and J. Seldin eds. Hyland, J. Martin E. McMichael, Alan and Edward N. Meyer, Albert R. Partee, Barbara H. Revesz, George E. Rosser, J. Turing, Alan M. Zalta, Edward N. Academic Tools How to cite this entry. Enhanced bibliography for this entry at PhilPapers , with links to its database. Lambda Evaluator , for visualizing reductions.
Standard combinators and Church numerals are predefined. Open access to the SEP is made possible by a world-wide funding initiative. Mirror Sites View this site from another server:. Terms are evaluated only once their value is really needed. When an expression e can go through infinite sequence of evaluation steps, we say e diverges.
This corresponds to nontermination. It depends on the reduction strategy. This puts the evaluator into an infinite loop, so e diverges. So CBN avoids divergence because it is lazy about evaluating arguments. One feature we seem to be missing is the ability to declare local variables. We don't really need to have let in the language. Perhaps the simplest interesting kind of value is a Boolean. There are many reasonable encodings into lambda calculus. Now, what about the conditional test IF?
We would like IF to take three arguments b, t, f , where b is a Boolean value and t , f are arbitrary terms. There is no guarantee of any kind of reasonable behavior. Evaluation will proceed and reductions will be applied, but there is no way to usefully interpret the result. We can encode natural numbers using Church numerals , introduced by Alonzo Church. The Church numeral for the number n is denoted n. We can perform more interesting arithmetic with Church numerals. We might define addition as follows:.
As another alternative, recall that Church numerals act on a function to apply that function repeatedly, and addition is equivalent to repeated application of the successor function S, so we could define ADD as:. If we apply ADD in curried fashion to one argument n , we will get a function that adds n to whatever it is applied to.
A good exercise is to figure out how to construct a predecessor function on the natural numbers. Church numerals only encode natural numbers, but they can be used to build more complex kinds of numbers such as integers and floating point numbers.
Pairing and Projection Logic and arithmetic are good places to start, but we still have no useful data structures. For example, consider ordered pairs.
We can take a hint from IF. Recall that IF selects one of its two branch options depending on its Boolean argument.
PAIR can do something similar, wrapping its two arguments for later extraction by some function f :. With an encoding for IF, we have some control over the flow of a program. We can also write simple for loops using the Church numerals n , by applying the Church numeral to the loop body expressed as a function.
However, we do not yet have the ability to write an unbounded while loop or a recursive function. Therefore it doesn't make sense as a shorthand for the term on the right. But it turns out we can define a term that acts in the way we want. Suppose we break up the recursion into two steps.
We start by defining a function F that adds an extra argument f for passing in something similar to FACT:.
0コメント