Encyclopedia - Lambda Calculus: Encyclopedia Ii - Lambda Calculus - Formal Definition
Formally, we start with a countably infinite set of identifiers, say {a, b, c, ..., x, y, z, x1, x2, ...}. The set of all lambda expressi...   » Read the article

Encyclopedia - Church Encoding: Encyclopedia Ii - Church Encoding - Church Numerals
Church numerals are the representations of natural numbers under Church encoding. The higher-order function that represents natural numbe...   » Read the article

Encyclopedia - Calculus Of Constructions: Encyclopedia Ii - Calculus Of Constructions - The Basics Of The Calculus Of Constructions
The Calculus of Constructions can be considered an extension of the Curry-Howard isomorphism. The Curry-Howard isomorphism associates a t...   » Read the article

Encyclopedia - Abstract Machine: Encyclopedia - Abstract Machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system. Abstraction of c...   » Read the article

Encyclopedia - Church Encoding: Encyclopedia Ii - Church Encoding - Church Booleans
Church booleans are the Church encoding of the boolean values true and false. Some programming languages use these as implementation mode...   » Read the article

Encyclopedia - Currying: Encyclopedia Ii - Currying - Examples
Suppose that plus is a function taking two arguments x and y and returning x + y. In the ML programming language we would define it as fo...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Pure Functions
Purely functional programs have no side-effects. Since functions do not modify state, no data may be changed by parallel function calls. ...   » Read the article

Encyclopedia - List Of Computing Topics: Encyclopedia Ii - List Of Computing Topics - 0–9
1.TR.6 -- 100BaseFX -- 100BaseTX -- 100BaseT -- 100BaseVG -- 100VG-AnyLAN -- 10base2 -- 10base5 -- 10baseT -- 120 reset -- 16-bit -- 16-b...   » Read the article

Encyclopedia - List Of Mathematics Categories: Encyclopedia Ii - List Of Mathematics Categories - Mathematics Categories
List of mathematics categories - 0–9. 3-manifolds -- 4-dimensional geometry -- 4-manifolds -- List of mathematics categories - A. ...   » Read the article

Encyclopedia - Turing Completeness: Encyclopedia Ii - Turing Completeness - Examples
The computational systems (algebras, calculi) that are discussed as Turing complete systems are those intended for studying theoretical c...   » Read the article

Encyclopedia - Value-level Programming: Encyclopedia Ii - Value-level Programming - Connection With Lambda Calculus Languages
Lambda calculus-based languages (such as Lisp, ISWIM, and Scheme) are in actual practice value-level languages, although they are not thu...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - History Of The Halting Problem
In the following: H refers to the source "Hodges" U refers to the source "Undecidable" W refers to definitions from Websters Ninth New Co...   » Read the article

Encyclopedia - Ski Combinator Calculus: Encyclopedia Ii - Ski Combinator Calculus - Ski Expressions
SKI combinator calculus - Self-application and recursion. is an expression that takes an argument and applies that argument to itself:...   » Read the article

Encyclopedia - Higher-order Function: Encyclopedia Ii - Higher-order Function - Alternatives
Programming languages can achieve some of the same algorithmic results as are obtained through higher-order functions by dynamically exec...   » Read the article

Encyclopedia - Beta Normal Form: Encyclopedia Ii - Beta Normal Form - Beta Reduction
In the lambda calculus, a beta redex is a term of the form where A(x) is a term (possibly) involving variable x. A beta reduction in h...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Introduction
Mathematical functions have great strengths in terms of flexibility and analysis. For example, if a function is known to be idempotent, t...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Speed And Space Considerations
Functional languages have long been criticised as resource-hungry, both in terms of CPU resources and memory. This was mainly due to two ...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Functional Languages
The first computer-based functional programming language was Information Processing Language (IPL) from the RAND corporation. Another ver...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Functional Languages
The oldest example of a functional language is Lisp, though neither the original LISP nor modern Lisps such as Common Lisp are pure-funct...   » Read the article

Encyclopedia - Ski Combinator Calculus: Encyclopedia Ii - Ski Combinator Calculus - Informal Description
Informally, the combinators in this system are defined as follows (x, y, and z represent expressions made from the functions , , and , an...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Relationship With Gödel's Incompleteness Theorem
The concepts raised by Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Higher-order Functions
A powerful mechanism sometimes used in functional programming is the notion of higher-order functions. Functions are higher-order when th...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Comparison With Imperative Programming
Functional programming can be contrasted with imperative programming. Functional programming appears to be missing several constructs oft...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Functional Programming Languages
Pure functional programs require no variables and have no side-effects, and are therefore automatically thread-safe. They are also automa...   » Read the article

Encyclopedia - Turing Completeness: Encyclopedia Ii - Turing Completeness - Related Work
One important result from computability theory is that it is impossible in general to find if a program written in a Turing-complete lang...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Comparison With Imperative Programming
Functional programming can be contrasted with imperative programming. Functional programming appears to be missing several constructs oft...   » Read the article

Encyclopedia - Ski Combinator Calculus: Encyclopedia Ii - Ski Combinator Calculus - Formal Definition
The terms and derivations in this system can also be more formally defined: Terms: The set T of terms is defined recursively by the follo...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Speed And Space Considerations
Functional languages have long been criticised as resource-hungry, both in terms of CPU resources and memory. This was mainly due to two ...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - Higher-order Functions
A powerful mechanism used in functional programming is the notion of higher-order functions. Functions are higher-order when they can tak...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Sketch Of Proof
The proof proceeds by reductio ad absurdum. We start with assuming that there is a function halt(a, i) that returns true if the algorithm...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Formalization Of The Halting Problem
In his original proof Turing formalized the concept of algorithm by introducing Turing machines. However, the result is in no way specifi...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Recognizing Partial Solutions
No program can solve the halting problem. There are programs that give correct answers for some instances of it, and run forever on all o...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Can Humans Solve The Halting Problem?
It might seem like humans could solve the halting problem. After all, a programmer can often look at a program and tell whether it will h...   » Read the article

Encyclopedia - List Of Mathematics Categories: Encyclopedia Ii - List Of Mathematics Categories - Mathematicians Categories
List of mathematics categories - 0–9. 10th century mathematicians -- 11th century mathematicians -- 12th century mathematicians -- 13...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Common Pitfalls
Many students, upon analyzing the above proof, ask whether there might be an algorithm that can return a third option, such as "undecidab...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Importance And Consequences
The importance of the halting problem lies in the fact that it is the first problem to be proved undecidable. Subsequently, many other su...   » Read the article

Encyclopedia - Currying: Encyclopedia Ii - Currying - Mathematical View
When viewed in a set-theoretic light, currying becomes the theorem that the set of functions from to A, and the set (AB)C of functions ...   » Read the article

Encyclopedia - Functional Programming: Encyclopedia Ii - Functional Programming - History
Lambda calculus, invented by Alonzo Church in the 1930s, provides a theoretical framework for describing functions and their evaluation. ...   » Read the article

Encyclopedia - Halting Problem: Encyclopedia Ii - Halting Problem - Formal Statement
One possible way of formally stating the halting problem is as follows: Given a Gödel numbering of the computable functions, with the ...   » Read the article

Encyclopedia - Beta Normal Form: Encyclopedia Ii - Beta Normal Form - Eta Reduction
An eta redex is a term of the form where F is a term in which x does not occur. Eta reduction is an application of the following rewri...   » Read the article

Encyclopedia - Lambda Calculus: Encyclopedia Ii - Lambda Calculus - Undecidability Of Equivalence
There is no algorithm which takes as input two lambda expressions and outputs TRUE or FALSE depending on whether or not the two expressio...   » Read the article

Encyclopedia - Lambda Calculus: Encyclopedia Ii - Lambda Calculus - Lambda Calculus And Programming Languages
Most programming languages are equivalent to the lambda calculus extended with some additional programming language constructs. The class...   » Read the article

Encyclopedia - Lambda Calculus: Encyclopedia Ii - Lambda Calculus - Recursion
Recursion is the definition of a function using the function itself; on the face of it, lambda calculus does not allow this. However, thi...   » Read the article

Encyclopedia - Lambda Calculus: Encyclopedia Ii - Lambda Calculus - Arithmetic In Lambda Calculus
There are several possible ways to define the natural numbers in lambda calculus, but by far the most common are the Church numerals, whi...   » Read the article

Encyclopedia - Lambda Calculus: Encyclopedia Ii - Lambda Calculus - Informal Description
In lambda calculus, every expression stands for a function with a single argument; the argument of the function is in turn a function wit...   » Read the article

Encyclopedia - Lambda Calculus: Encyclopedia Ii - Lambda Calculus - Logic And Predicates
By convention, the following two definitions (known as Church booleans) are used for the boolean values TRUE and FALSE: TRUE := λ ...   » Read the article