|
List Of Undecidable Problems
In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer. More formally, an undecidable problem is a problem whose language is not a recursive set; see the article Decidable language. There are uncountably many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subsets of Turing recognizable languages: i.e., such undecidable languages may be recursively enumerable. Many, if not most, undecidable problems in mathematics can be posed as word problems: determining when two distinct strings of symbols (encoding some mathematical concept or object) represent the same object or not. For undecidability in axiomatic mathematics, see List of stateme ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computability Theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: * What does it mean for a function on the natural numbers to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages. I ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Halting Problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program–input pairs cannot exist. For any program that might determine whether programs halt, a "pathological" program , called with some input, can pass its own source and its input to ''f'' and then specifically do the opposite of what ''f'' predicts ''g'' will do. No ''f'' can exist that handles this case. A key part of the proof is a mathematical definition of a computer and program, which is known as a Turing machine; the halting problem is '' undecidable'' over Turing machines. It is one of the first cases of decision problems proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming inventi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Conjugacy Problem
In abstract algebra, the conjugacy problem for a group ''G'' with a given presentation is the decision problem of determining, given two words ''x'' and ''y'' in ''G'', whether or not they represent conjugate elements of ''G''. That is, the problem is to determine whether there exists an element ''z'' of ''G'' such that :y = zxz^.\,\! The conjugacy problem is also known as the transformation problem. The conjugacy problem was identified by Max Dehn in 1911 as one of the fundamental decision problems in group theory; the other two being the word problem and the isomorphism problem. The conjugacy problem contains the word problem as a special case: if ''x'' and ''y'' are words, deciding if they are the same word is equivalent to deciding if xy^ is the identity, which is the same as deciding if it's conjugate to the identity. In 1912 Dehn gave an algorithm that solves both the word and conjugacy problem for the fundamental groups of closed orientable two-dimensional manifolds of g ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Word Problem For Groups
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group ''G'' is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if ''A'' is a finite set of generators for ''G'' then the word problem is the membership problem for the formal language of all words in ''A'' and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on ''A'' to the group ''G''. If ''B'' is another finite generating set for ''G'', then the word problem over the generating set ''B'' is equivalent to the word problem over the generating set ''A''. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group ''G''. The related but different uniform word problem for a class ''K'' of recursively presented groups is the algorithmic problem of deciding, given as input a pres ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer Matrices
In mathematics, an integer matrix is a matrix whose entries are all integers. Examples include binary matrices, the zero matrix, the matrix of ones, the identity matrix, and the adjacency matrices used in graph theory, amongst many others. Integer matrices find frequent application in combinatorics. Examples :\left(\begin 5 & 2 & 6 & 0\\ 4 & 7 & 3 & 8\\ 5 & 9 & 0 & 4\\ 3 & 1 & 0 & \!\!\!-3\\ 9 & 0 & 2 & 1\end\right) and \left(\begin 1 & 5 & 0\\ 0 & 9 & 2\\ 1 & 7 & 3\end\right) are both examples of integer matrices. Properties Invertibility of integer matrices is in general more numerically stable than that of non-integer matrices. The determinant of an integer matrix is itself an integer, thus the numerically smallest possible magnitude of the determinant of an invertible integer matrix is one, hence where inverses exist they do not become excessively large (see condition number). Theorems from matrix theory that infer properties from determinants ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', denotes the result of applying the semigroup operation to the ordered pair . Associativity is formally expressed as that for all ''x'', ''y'' and ''z'' in the semigroup. Semigroups may be considered a special case of magmas, where the operation is associative, or as a generalization of groups, without requiring the existence of an identity element or inverses. The closure axiom is implied by the definition of a binary operation on a set. Some authors thus omit it and specify three axioms for a group and only one axiom (associativity) for a semigroup. As in the case of groups or magmas, the semigroup operation need not be commutative, so ''x''·''y'' is not necessarily equal to ''y''·''x''; a well-known example of an operation that is as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Zero Matrix
In mathematics, particularly linear algebra, a zero matrix or null matrix is a matrix all of whose entries are zero. It also serves as the additive identity of the additive group of m \times n matrices, and is denoted by the symbol O or 0 followed by subscripts corresponding to the dimension of the matrix as the context sees fit. Some examples of zero matrices are : 0_ = \begin 0 \end ,\ 0_ = \begin 0 & 0 \\ 0 & 0 \end ,\ 0_ = \begin 0 & 0 & 0 \\ 0 & 0 & 0 \end .\ Properties The set of m \times n matrices with entries in a ring K forms a ring K_. The zero matrix 0_ \, in K_ \, is the matrix with all entries equal to 0_K \, , where 0_K is the additive identity in K. : 0_ = \begin 0_K & 0_K & \cdots & 0_K \\ 0_K & 0_K & \cdots & 0_K \\ \vdots & \vdots & \ddots & \vdots \\ 0_K & 0_K & \cdots & 0_K \end_ The zero matrix is the additive identity in K_ \, . That is, for all A \in K_ \, it satisfies the equation :0_+A = A + 0_ = A. There is exactly one zero matrix of any ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mortal Matrix Problem
In mathematics, particularly linear algebra, a zero matrix or null matrix is a matrix all of whose entries are zero. It also serves as the additive identity of the additive group of m \times n matrices, and is denoted by the symbol O or 0 followed by subscripts corresponding to the dimension of the matrix as the context sees fit. Some examples of zero matrices are : 0_ = \begin 0 \end ,\ 0_ = \begin 0 & 0 \\ 0 & 0 \end ,\ 0_ = \begin 0 & 0 & 0 \\ 0 & 0 & 0 \end .\ Properties The set of m \times n matrices with entries in a ring K forms a ring K_. The zero matrix 0_ \, in K_ \, is the matrix with all entries equal to 0_K \, , where 0_K is the additive identity in K. : 0_ = \begin 0_K & 0_K & \cdots & 0_K \\ 0_K & 0_K & \cdots & 0_K \\ \vdots & \vdots & \ddots & \vdots \\ 0_K & 0_K & \cdots & 0_K \end_ The zero matrix is the additive identity in K_ \, . That is, for all A \in K_ \, it satisfies the equation :0_+A = A + 0_ = A. There is exactly one zero matrix of an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tag System
A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post–Turing machines)—briefly, a finite-state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition. Because all of the indicated operations are performed in a single transition, a tag machine strictly has only one state. Definitions A ''tag system'' is a triplet (''m'', ''A'', ''P''), where * ''m'' is a positive integer, called the ''deletion number''. * ''A'' is a finite alphabet of symbols, one of which is a special ''halting symbol''. All finite (possibly empty) strings on ''A'' are called ' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pushdown Automaton
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines (see below). Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design. The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata. A nested stack automaton allows full access, and also allows stacked values to be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minsky Machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent. Overview The register machine gets its name from its use of one or more " registers". In contrast to the tape and head used by a Turing machine, the model uses multiple, uniquely addressed registers, each of which holds a single positive integer. There are at least four sub-classes found in literature, here listed from most primitive to the most like a computer: * Counter machine – the most primitive and reduced theoretical model of a computer hardware. Lacks indirect addressing. Instructions are in the finite state machine in the manner of the Harvard architecture. *Pointer machine – a blend of counter machine and RAM models. Less common and more abstract than either model. Instructions are in the finite state machine in the manner of the Harvard architecture. *Random-access mach ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rice's Theorem
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is ''non-trivial'' if it is neither true for every partial computable function, nor false for every partial computable function. Rice's theorem can also be put in terms of functions: for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called ''trivial'' if it holds for all partial computable functions or for none, and an effective decision method is called ''general'' if it decides correctly for every algorithm. The theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
