CushionTheBlow (구 BluemoonSoft)

Mathematical logic is a subfield of logic and mathematics. It consists both of the mathematical study of logic and the application of this study to other areas of mathematics. Mathematical logic has close connections to computer science and philosophical logic, as well. Unifying themes in mathematical logic include the expressive power of formal logics and the deductive power of formal proof systems.

Since its inception, mathematical logic has contributed to, and has been motivated by, the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and analysis. In the early 20th century it was shaped by David Hilbert's program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Work in set theory showed that almost all ordinary mathematics can be formalized in terms of sets, although there are some theorems that cannot be proven in common axiom systems for set theory. Contemporary work in the foundations of mathematics often focuses on establishing which parts of mathematics can be formalized in particular formal systems, rather than trying to find theories in which all of mathematics can be developed.

Mathematical logic is often divided into the subfields of set theory, model theory, recursion theory, and proof theory and constructive mathematics. These areas share basic results on logic, particularly first-order logic, and definability.

Reference:
http://en.wikipedia.org/wiki/Mathematical_logic

In mathematics, model theory is the study of (classes of) mathematical structures such as groups, fields, graphs or even models of set theory using tools from mathematical logic. Model theory has close ties to algebra and universal algebra.

This article focuses on finitary first order model theory of infinite structures. The model theoretic study of finite structures (for which see finite model theory) diverges significantly from the study of infinite structures in both the problems studied and the techniques used. Model theory in higher-order logics or infinitary logics is hampered by the fact that completeness does not in general hold for these logics. However, a great deal of study has also been done in such languages.

Reference:
http://en.wikipedia.org/wiki/Model_theory

In computer science and mathematical logic, the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems; the Turing degree of a set tells how difficult it is to solve the decision problem associated with the set.

Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered so that if the Turing degree of a set X is less than the Turing degree of a set Y then any (noncomputable) procedure that correctly decides whether numbers are in Y can be effectively converted to a procedure that correctly decides whether numbers are in X. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.

The Turing degrees were introduced by Stephen Cole Kleene and Emil Leon Post in the 1940s and have been an area of intense research since then.

Reference:
http://en.wikipedia.org/wiki/Turing_degree

Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. They make precise the intuitive notion of algorithm. Computable functions can be used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Their definition, however, must make reference to some specific model of computation.

Before the precise definition of computable function, mathematicians often used the informal term effectively computable. This term has since come to be identified with the computable functions. Note that the effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time). In fact, for some effectively computable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases exponentially (or even superexponentially) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently.

According to the Church-Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that any function which has an algorithm is computable.

The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory, the problem of determining the complexity of a computable function is known as a function problem.

Reference:
http://en.wikipedia.org/wiki/Computable_function

In the discussion of the foundations of mathematics, several set theories have been developed, of which naive set theory is one. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics (for example Venn diagrams and symbolic reasoning about their Boolean algebra), and the everyday usage of set theory concepts in most contemporary mathematics.

Sets are of great importance in mathematics; in fact, in modern formal treatments, most mathematical objects (numbers, relations, functions, etc.) are defined in terms of sets. Naive set theory can be seen as a stepping-stone to more formal treatments, and suffices for many purposes.

Reference:
http://en.wikipedia.org/wiki/Naive_set_theory

A formal language can be entirely defined by the way a set of symbols is organized. This way, it can be defined before it has any meaning- without any reference to any meanings of its expressions and before any interpretations are given to it. Formal languages are tools in the field of mathematical logic and computer science. As such they are designed to express the logic of executable programs.

Like languages in linguistics, formal languages generally have two aspects: syntax and semantics. The syntax of a language is what the language looks like without regard to its meaning. The syntax is defined by the set of rules that govern how the symbols of a formal language can be used to construct valid expressions. The semantics is what those expressions mean. This is formalized in various ways, depending on the type of language in question.

A formal language can be identified by its well formed formulas (wffs). The set of well-formed formula of a particular formal language is determined by a fiat of its creator. Usually, the determination of what is and is not a well-formed formula is laid down by designating a) a set of symbols which are the alphabet of the language and b) a set of formation rules which determine what sequences of symbols from the alphabet are the well-formed formula of the language.

The branch of mathematics and computer science which studies exclusively the theory of language syntax is known as formal language theory. In formal language theory, a language is nothing more than its syntax; questions of semantics are not addressed in this specialty.

Reference:
http://en.wikipedia.org/wiki/Formal_language

Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. Combinatorial optimization algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances. Combinatorial optimization algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.

A study of computational complexity theory helps to motivate combinatorial optimization. Combinatorial optimization algorithms are typically concerned with problems that are NP-hard. Such problems are not believed to be efficiently solvable in general. However, the various approximations of complexity theory suggest that some instances (e.g. "small" instances) of these problems could be efficiently solved. This is indeed the case, and such instances often have important practical ramifications.

Reference:
http://en.wikipedia.org/wiki/Combinatorial_search

A heuristic is a method to help to solve a problem, commonly informal. It is particularly used for a method that often rapidly leads to a solution that is usually reasonably close to the best possible answer. Heuristics are "rules of thumb", educated guesses, intuitive judgments or simply common sense.

In more precise terms, heuristics stand for strategies using readily accessible, though loosely applicable, information to control problem-solving in human beings and machines.

Reference:
http://en.wikipedia.org/wiki/Heuristic