The usual number of scalar operations (i.e., the total number of additions and multiplications) required to perform matrix multiplication is(1)(i.e., multiplications and additions). However, Strassen (1969) discovered how to multiply two matrices in(2)scalar operations, where is the logarithm to base 2, which is less than for . For a power of two (), the two parts of (2) can be written(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)so (◇) becomes(13)Two matrices can therefore be multiplied(14)(15)with only(16)scalar operations (as it turns out, seven of them are multiplications and 18 are additions). Define the seven products (involving a total of 10 additions) as(17)(18)(19)(20)(21)(22)(23)Then the matrix product is given using the remaining eight additions as(24)(25)(26)(27)(Strassen 1969, Press et al. 1989).Matrix inversion of a matrix to yield can also be done in fewer operations than expected using the formulas(28)(29)(30)(31)(32)(33)(34)(35)(36)(37)(38)(Strassen..
If is a class of recursively enumerable sets, then the set of Gödel numbers of functions whose domains belong to is called its index set. If the index set of is a recursive set, then either is empty or contains all recursively enumerable sets.Rice's theorem is an important result for computer science because it sets up boundaries for research in that area. It basically states that only trivial properties of programs are algorithmically decidable.
Let denote the recursive function of variables with Gödel number , where (1) is normally omitted. Then if is a partial recursive function, there exists an integer such thatwhere is Church's lambda notation. This is the variant most commonly known as Kleene's recursion theorem.Another variant generalizes the first variant by parameterization, and is the strongest form of the recursion theorem. This form states that for each , there exists a recursive function of variables such that is a injection and if is a total function, then for all , ..., , and ,Yet another and weaker variant of the recursion theorem guarantees the existence of a recursive function that is a fixed point for a recursive functional.
Determination of whether predicate is true or false for any given values of , ..., is called its decision problem. The decision problem for predicate is called recursively decidable if there is a total recursive function such that(1)Given the equivalence of computability and recursiveness, this definition may be restated with reference to computable functions instead of recursive functions.The halting problem was one of the first to be shown recursively undecidable. The formulation of recursive undecidability of the halting problem and many other recursively undecidable problems is based on Gödel numbers. For instance, the problem of deciding for any given whether the Turing machine whose Gödel number is is total is recursively undecidable. Hilbert's tenth problem is perhaps the most famous recursively undecidable problem.Most proofs of recursive undecidability use reduction. They show that recursive decidability..
Turing machines are defined by sets of rules that operate on four parameters: (state, tape cell color, operation, state). Let the states and tape cell colors be numbered and represented by quadruples of ordinal numbers. Then there exist algorithmic procedures that sequentially list all consistent sets of Turing machine rules. A set of rules is called consistent if any two quadruples differ in the first or second element out of the four. Any such procedure gives both an algorithm for going from any integer to its corresponding Turing machine and an algorithm for getting the index of any consistent set of Turing machine rules.Assume that one such procedure is selected. If Turing machine is defined by the set of quadruples whose index is , then is called the Gödel number of . The result of application of Turing machine with Godel number to is usually denoted .Given the equivalence of computability and recursiveness, it is common to use Gödel..
A set of integers is said to be recursively enumerable if it constitutes the range of a recursive function, i.e., if there exists a recursive function that can eventually generate any element in (Wolfram 2002, p. 1138). Any recursive set is also recursively enumerable.The union and intersection of two recursively enumerable sets are also recursively enumerable.Recursively undecidable problems give examples of recursively enumerable sets that are not recursive. For example, convergence of is known to be recursively undecidable, where denotes the Turing machine with Gödel number . Hence the set of all for which is convergent is not recursive. However, this set is recursively enumerable because it is the range of defined as follows:(1)A set is recursive iff both and its complement are recursively enumerable. This provides an approach to constructing additional sets that are not recursively enumerable. In particular, the..
A set of integers is said to be recursive if there is a total recursive function such that for and for . Any recursive set is also recursively enumerable.Finite sets, sets with finite complements, the odd numbers, and the prime numbers are all examples of recursive sets. The union and intersection of two recursive sets are themselves recursive, as is the complement of a recursive set.
A set of integers is productive if there exists a partial recursive function such that, for any , the following holds: If the domain of is a subset of , then is convergent, belongs to , and does not belong to the domain of , where denotes a recursive function whose Gödel number is .Productive sets are not recursively enumerable.
A recursively enumerable set is creative if its complement is productive. Creative sets are not recursive. The property of creativeness coincides with completeness. Namely, set is creative iff if it is many-one complete.Elementary arithmetic formulas are built up from 0, 1, 2, ..., , , , variables, connectives, and quantifiers. The set of all true arithmetic formulas is productive. Informally speaking, this means that no axiomatization of arithmetic can capture all true formulas and nothing else. For example, consider Peano arithmetic. Under the assumption that no false arithmetic formulas are provable in this theory, provable Peano arithmetic formulas form a creative set.
It is possible to perform multiplication of large numbers in (many) fewer operations than the usual brute-force technique of "long multiplication." As discovered by Karatsuba (Karatsuba and Ofman 1962), multiplication of two -digit numbers can be done with a bit complexity of less than using identities of the form(1)Proceeding recursively then gives bit complexity , where (Borwein et al. 1989). The best known bound is steps for (Schönhage and Strassen 1971, Knuth 1998). However, this algorithm is difficult to implement, but a procedure based on the fast Fourier transform is straightforward to implement and gives bit complexity (Brigham 1974, Borodin and Munro 1975, Borwein et al. 1989, Knuth 1998).As a concrete example, consider multiplication of two numbers each just two "digits" long in base ,(2)(3)then their product is(4)(5)(6)Instead of evaluating products of individual digits, now write(7)(8)(9)The..
A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with nodes has graph edges. Conversely, a connected graph with nodes and edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted tree), by way of distinguishing them from rooted trees (Skiena 1990, Knuth 1997).The points of connection are known..
In machine learning theory and artificial intelligence, a concept over a domain is a Boolean function . A collection of concepts is called a concept class.In context-specific applications, concepts are usually thought to assign either a "positive" or "negative" outcome (corresponding to range values of 1 or 0, respectively) to each element of the domain . In that way, concepts are the fundamental component of learning theory.
Inspired by computer simulations of fossilized worms trails published by Raup and Seilacher (1969), computer scientist Mike Paterson at the University of Warwick and mathematician J. H. Conway created in early 1971 a simple set to rules to study idealized worms traveling along regular grids. Mike Beeler of the MIT Artificial Intelligence Laboratory subsequently published a study Paterson's worms in which he considered paths on a triangular grid (Beeler 1973).The following table summarizes the number of steps required for a number of long-running worms to terminate (Rokicki).patternsteps to terminate10420151042020104202212521211420221infinite14202241450221infinite14502241525115201414221451422454142Paterson's worms are featured in the 2003 Stephen Low IMAX film Volcanoesof the Deep Sea...
An abstract machine is a model of a computer system (considered either as hardware or software) constructed to allow a detailed and precise analysis of how the computer system works. Such a model usually consists of input, output, and operations that can be preformed (the operation set), and so can be thought of as a processor. Turing machines are the best known abstract machines, but there exist many other machines as well such as cellular automata.Abstract machines that model software are usually thought of as having very high-level operations. For example, an abstract machine that models a banking system can have operations like "deposit," "withdraw," "transfer," etc.An abstract machine implemented in software is termed a virtualmachine, and one implemented in hardware is called simply a "machine."..
A universal cellular automaton is a cellular automaton which, like a Turing machine, exhibits universality. von Neumann proved that an automaton consisting of cells with four orthogonal neighbors and 29 possible states would be capable of simulating a Turing machine for some configuration of about cells (Gardner 1983, p. 227).The outlines of a proof that the two-dimensional game of life outer-totalistic cellular automaton is universal were given by Berlekamp, Conway, and Guy (1982) and independently by Gosper (Gardner 1983, pp. 250-253). Around 2000, a Turing machine was explicitly implemented in life by P. Rendell (Rendell, Adamatzky 2001). While Rendell's machine can be made into a "true" universal computer simply by making his tape infinite, he neither noted this fact nor provided an actual construction of a universal Turing machine. Subsequently, on November 11, 2002, P. Chapman constructed..
The mathematical study of abstract computing machines (especially Turingmachines) and the analysis of algorithms used by such machines.A connection between automata theory and number theory was provided by Christol et al. (1980), who showed that a sequence is generated by a -automaton iff the formal power series with coefficients is algebraic on the field of rational elements , where and are polynomials with coefficients in the finite field .
Given a sum and a set of weights, find the weights which were used to generate the sum. The values of the weights are then encrypted in the sum. This system relies on the existence of a class of knapsack problems which can be solved trivially (those in which the weights are separated such that they can be "peeled off" one at a time using a greedy-like algorithm), and transformations which convert the trivial problem to a difficult one and vice versa. Modular multiplication is used as the trapdoor one-way function. The simple knapsack system was broken by Shamir in 1982, the Graham-Shamir system by Adleman, and the iterated knapsack by Ernie Brickell in 1984.
A Turing machine is a theoretical computing machine invented by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine consists of a line of cells known as a "tape" that can be moved back and forth, an active element known as the "head" that possesses a property known as "state" and that can change the property known as "color" of the active cell underneath it, and a set of instructions for how the head should modify the active cell and move the tape (Wolfram 2002, pp. 78-81). At each step, the machine may modify the color of the active cell and change the state of the head. After this, it moves the tape one unit to the left or right.Turing machines are implemented in the WolframLanguage as TuringMachine.A generalization of the Turing machine in which the head is allowed to move steps in either direction was considered by Macura (2005).A template for specifying..
An encoding is a way of representing a number or expression in terms of another (usually simpler) one. However, multiple expressions can also be encoded as a single expression, as in, for example,which encodes and uniquely as a single number.000011102023114205More generally, any list of positive integers can be uniquely encoded using a Gödel number (Wolfram 2002, p. 1120).
A recursive sequence , also known as a recurrence sequence, is a sequence of numbers indexed by an integer and generated by solving a recurrence equation. The terms of a recursive sequences can be denoted symbolically in a number of different notations, such as , , or f, where is a symbol representing the sequence.The idea of sequences in which later terms are deduced from earlier ones, which is implicit in the principle of mathematical induction, dates to antiquity.In the case of linear recurrence equationssuch as the recurrence(with ) generating the Fibonacci numbers, it is possible to solve for an explicit analytic form of the th term of the sequence. Some special classes of recurrence equations have analytic solutions for specific parameters, but solutions for a general parameter is not known. An example of this type is the logistic equationwhich has known exact solutions only for , 2, and 4. It is not known how to solve a general recurrence..
Let be a set and a collection of subsets of . A subset is shattered by if each subset of can be expressed as the intersection of with a subset in . Symbolically, then, is shattered by if for all , there exists some for which .If is shattered by , one says that shatters .There are a number of equivalent ways to define shattering. One can easily verify that the above definition is equivalent to saying that shatters ifwhere denotes the power set of . Yet another way to express this concept is to say that a set of cardinality is shattered by a set if where here,In the field of machine learning theory, one usually considers the set to be a sample of outcomes drawn according to a distribution with the set representing a collection of "known" concepts or laws. In this context, saying that is shattered by intuitively means that all of the constituent outcomes in can be known by knowing only the laws in ...
A recurrence plot is defined as a plot of the quantitywhere is the Heaviside step function and denotes a norm. A recurrence plot is therefore a binary plot. The figure above shows a recurrence plot for the Lorenz attractor with , , , , , , and .Recurrence plots were initially used to graphically display nonstationarity in time series (Eckmann et al. 1987, Gao and Cai 2000), but are also useful for visualizing functions.A so-called global recurrence plot or unthresholded recurrence plot of a function is a plot of (or ) in the - plane. Recurrence plots for a number of common functions are illustrated above.