|
Computable Topology
Computable topology is a discipline in mathematics that studies the topological and algebraic structure of computation. Computable topology is not to be confused with algorithmic or ''computational topology'', which studies the application of computation to topology. Topology of lambda calculus As shown by Alan Turing and Alonzo Church, the lambda-calculus, λ-calculus is strong enough to describe all mechanically computable functions (see Church–Turing thesis). Lambda-calculus is thus effectively a programming language, from which other languages can be built. For this reason when considering the topology of computation it is common to focus on the topology of λ-calculus. Note that this is not necessarily a complete description of the topology of computation, since functions which are equivalent in the Church-Turing sense may still have different topologies. The topology of λ-calculus is the #Scott topology, Scott topology, and when restricted to continuous functions the typ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Effective Method
In logic, mathematics and computer science, especially metalogic and computability theory, an effective method Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University of California Press, 1971 or effective procedure is a procedure for solving a problem by any intuitively 'effective' means from a specific class. An effective method is sometimes also called a mechanical method or procedure. Definition The definition of an effective method involves more than the method itself. In order for a method to be called effective, it must be considered with respect to a class of problems. Because of this, one method may be effective with respect to one class of problems and ''not'' be effective with respect to a different class. A method is formally called effective for a class of problems when it satisfies these criteria: * It consists of a finite number of exact, finite instructions. * When it is applied to a problem from its class: ** I ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Product Topology
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seeming, topology called the box topology, which can also be given to a product space and which agrees with the product topology when the product is over only finitely many spaces. However, the product topology is "correct" in that it makes the product space a categorical product of its factors, whereas the box topology is too fine; in that sense the product topology is the natural topology on the Cartesian product. Definition Throughout, I will be some non-empty index set and for every index i \in I, let X_i be a topological space. Denote the Cartesian product of the sets X_i by X := \prod X_ := \prod_ X_i and for every index i \in I, denote the i-th by \begin p_i :\;&& \prod_ X_j &&\;\to\; & X_i \\ .3ex && \left(x_j\r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pointwise Convergence
In mathematics, pointwise convergence is one of Modes of convergence (annotated index), various senses in which a sequence of functions can Limit (mathematics), converge to a particular function. It is weaker than uniform convergence, to which it is often compared. Definition Suppose that X is a set and Y is a topological space, such as the Real number, real or complex numbers or a metric space, for example. A Net (mathematics), net or sequence of Function (mathematics), functions \left(f_n\right) all having the same domain X and codomain Y is said to converge pointwise to a given function f : X \to Y often written as \lim_ f_n = f\ \mbox if (and only if) \lim_ f_n(x) = f(x) \text x \text f. The function f is said to be the pointwise limit function of the \left(f_n\right). Sometimes, authors use the term bounded pointwise convergence when there is a constant C such that \forall n,x,\;, f_n(x), Properties This concept is often contra ...[...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kolmogorov Space
In topology and related branches of mathematics, a topological space ''X'' is a T0 space or Kolmogorov space (named after Andrey Kolmogorov) if for every pair of distinct points of ''X'', at least one of them has a neighborhood not containing the other. In a T0 space, all points are topologically distinguishable. This condition, called the T0 condition, is the weakest of the separation axioms. Nearly all topological spaces normally studied in mathematics are T0 spaces. In particular, all T1 spaces, i.e., all spaces in which for every pair of distinct points, each has a neighborhood not containing the other, are T0 spaces. This includes all T2 (or Hausdorff) spaces, i.e., all topological spaces in which distinct points have disjoint neighbourhoods. In another direction, every sober space (which may not be T1) is T0; this includes the underlying topological space of any scheme. Given any topological space one can construct a T0 space by identifying topologically indistinguishable ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Beta Normal Form
In the lambda calculus, a term is in beta normal form if no ''beta reduction'' is possible. A term is in beta-eta normal form if neither a beta reduction nor an ''eta reduction'' is possible. A term is in head normal form if there is no ''beta-redex in head position''. Beta reduction In the lambda calculus, a beta redex is a term of the form: : (\mathbf x . A) M. A redex r is in head position in a term t, if t has the following shape (note that application has higher priority than abstraction, and that the formula below is meant to be a lambda-abstraction, not an application): : \lambda x_1 \ldots \lambda x_n . \underbrace_ M_2 \ldots M_m , where n \geq 0 and m \geq 1. A beta reduction is an application of the following rewrite rule to a beta redex contained in a term: : (\mathbf x . A) M \longrightarrow A := M where A := M/math> is the result of substituting the term M for the variable x in the term A. A ''head'' beta reduction is a beta reduction applied in head position ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Equivalence Relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relation provides a partition of the underlying set into disjoint equivalence classes. Two elements of the given set are equivalent to each other if and only if they belong to the same equivalence class. Notation Various notations are used in the literature to denote that two elements a and b of a set are equivalent with respect to an equivalence relation R; the most common are "a \sim b" and "", which are used when R is implicit, and variations of "a \sim_R b", "", or "" to specify R explicitly. Non-equivalence may be written "" or "a \not\equiv b". Definition A binary relation \,\sim\, on a set X is said to be an equivalence relation, if and only if it is reflexive, symmetric and transitive. That is, for all a, b, and c in X: * a \sim a ( ref ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lambda Term
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing § lambda terms and performing § reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules: * x – variable, a character or string representing a parameter or mathematical/logical value. * (\lambda x.M) – abstraction, function definition (M is a lambda term). The variable x becomes bound in the expression. * (M\ N) – application, applying a function M to an argument N. M and N are lambda terms. The reduction operations include: * (\lambda x.M \rightarrow(\la ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lambda Calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing § lambda terms and performing § reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules: * x – variable, a character or string representing a parameter or mathematical/logical value. * (\lambda x.M) – abstraction, function definition (M is a lambda term). The variable x becomes bound in the expression. * (M\ N) – application, applying a function M to an argument N. M and N are lambda terms. The reduction operations include: * (\lambda x.M \rightarrow(\l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fixed-point Combinator
In mathematics and computer science in general, a '' fixed point'' of a function is a value that is mapped to itself by the function. In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function \textsf that returns some fixed point of its argument function, if one exists. Formally, if the function ''f'' has one or more fixed points, then : \textsf\ f = f\ (\textsf\ f)\ , and hence, by repeated application, : \textsf\ f = f\ (f\ ( \ldots f\ (\textsf\ f) \ldots))\ . Y combinator In the classical untyped lambda calculus, every function has a fixed point. A particular implementation of fix is Curry's paradoxical combinator Y, represented by : \textsf = \lambda f. \ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ .Throughout this article, the syntax rules given in Lambda calculus#Notation are used, to save parentheses.For an arbitrary lambda term ''f'', the fixed-point property can be validated by beta reducing the left- and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scott Continuous
In mathematics, given two partially ordered sets ''P'' and ''Q'', a function ''f'': ''P'' → ''Q'' between them is Scott-continuous (named after the mathematician Dana Scott) if it preserves all directed suprema. That is, for every directed subset ''D'' of ''P'' with supremum in ''P'', its image has a supremum in ''Q'', and that supremum is the image of the supremum of ''D'', i.e. \sqcup f = f(\sqcup D), where \sqcup is the directed join. When Q is the poset of truth values, i.e. Sierpiński space, then Scott-continuous functions are characteristic functions of open sets, and thus Sierpiński space is the classifying space for open sets. A subset ''O'' of a partially ordered set ''P'' is called Scott-open if it is an upper set and if it is inaccessible by directed joins, i.e. if all directed sets ''D'' with supremum in ''O'' have non-empty intersection with ''O''. The Scott-open subsets of a partially ordered set ''P'' form a topology on ''P'', the Scott topology. A function bet ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dana Scott
Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California. His work on automata theory earned him the Turing Award in 1976, while his collaborative work with Christopher Strachey in the 1970s laid the foundations of modern approaches to the semantics of programming languages. He has worked also on modal logic, topology, and category theory. Early career He received his B.A. in Mathematics from the University of California, Berkeley, in 1954. He wrote his Ph.D. thesis on ''Convergent Sequences of Complete Theories'' under the supervision of Alonzo Church while at Princeton, and defended his thesis in 1958. Solomon Feferman (2005) writes of this period: After completing his Ph.D. studies, he moved to the University of Chicago, working as an instructor there until 1960. In 1959, he pu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
