|
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 λ-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, and when restricted to continuous functions the type free λ-calculus amounts to a to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Effective Method
In metalogic, mathematical logic, and computability theory, an effective method or effective procedure is a finite-time, deterministic procedure for solving a problem from a specific class. An effective method is sometimes also called a mechanical method or procedure. Definition Formally, a method is called effective to a specific class of problems when it satisfies the following criteria: * It consists of a finite number of exact, finite instructions. * When it is applied to a problem from its class: ** It always finishes (''terminates'') after a finite number of steps. ** It always produces a correct answer. * In principle, it can be done by a human without any aids except writing materials. * Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed.The Cambridge Dictionary of Philosophy, ''effective procedure'' Optionally, it may also be required that the method never returns a result as if it were an answer wh ... [...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 Comparison of topologies, 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 Product (category theory), categorical product of its factors, whereas the box topology is too Comparison of topologies, 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 ... [...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 function (mathematics), 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 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) the limit of a sequence, limit of the sequence f_n(x) evaluated at each point x in the domain of f is equal to f(x), written as \forall x \in X, \lim_ f_n(x) = f(x). The function f is said to be the pointwise limit function of the \left(f_n\right). The definition easily generalizes from sequences to Net (mathematics), nets f_\bull ... [...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 indistinguisha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Beta Normal Form
In 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 the head position''. The normal form of a term, if one exists, is unique (as a corollary of the Church–Rosser theorem). However, a term may have more than one head normal form. 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 ... [...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. A simpler example is equality. Any number a is equal to itself (reflexive). If a = b, then b = a (symmetric). If a = b and b = c, then a = c (transitive). 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". Definitions A binary relation \,\si ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lambda Term
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution. Untyped lambda calculus, the topic of this article, is a universal machine, a model of computation that can be used to simulate any Turing machine (and vice versa). It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. In 1936, Church found a formulation which was logically consistent, and documented it in 1940. Lambda calculus consists of constructing lambda terms and performing reduction operations on them. A term is defined as any valid lambda calculus expression. In the simplest form of lambda calculus, terms are built using only the following rules: # x: A variable is a character or string representing a parameter. # (\lambda x.M): A lambda abstraction is a function definition, taking as in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lambda Calculus
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using variable Name binding, binding and Substitution (algebra), substitution. Untyped lambda calculus, the topic of this article, is a universal machine, a model of computation that can be used to simulate any Turing machine (and vice versa). It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. In 1936, Church found a formulation which was #History, logically consistent, and documented it in 1940. Lambda calculus consists of constructing #Lambda terms, lambda terms and performing #Reduction, reduction operations on them. A term is defined as any valid lambda calculus expression. In the simplest form of lambda calculus, terms are built using only the following rules: # x: A ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fixed-point Combinator
In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function (i.e., a function which takes a function as argument) that returns some '' fixed point'' (a value that is mapped to itself) of its argument function, if one exists. Formally, if \mathrm is a fixed-point combinator and the function f has one or more fixed points, then \mathrm\ f is one of these fixed points, i.e., : \mathrm\ f\ = f\ (\mathrm\ f) . Fixed-point combinators can be defined in the lambda calculus and in functional programming languages, and provide a means to allow for recursive definitions. ''Y'' combinator in lambda calculus In the classical untyped lambda calculus, every function has a fixed point. A particular implementation of \mathrm is Haskell Curry's paradoxical combinator ''Y'', given byThroughout this article, the syntax rules given in Lambda calculus#Notation are used, to save parentheses.According to Barendregt p.132, the name origin ... [...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 betw ... [...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 also worked 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, h ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
