Computer science

Math Topics A - Z listing

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Computer science Topics

Sort by:

Newton's iteration

Newton's iteration is an algorithm for computing the square root of a number via the recurrence equation(1)where . This recurrence converges quadratically as .Newton's iteration is simply an application of Newton'smethod for solving the equation(2)For example, when applied numerically, the first few iterations to Pythagoras's constant are 1, 1.5, 1.41667, 1.41422, 1.41421, ....The first few approximants , , ... to are given by(3)These can be given by the analytic formula(4)(5)These can be derived by noting that the recurrence can be written as(6)which has the clever closed-form solution(7)Solving for then gives the solution derived above.The following table summarizes the first few convergents for small positive integer OEIS, , ...11, 1, 1, 1, 1, 1, 1, 1, ...2A001601/A0510091, 3/2, 17/12, 577/408, 665857/470832, ...3A002812/A0715791, 2, 7/4, 97/56, 18817/10864, 708158977/408855776, .....

Computational reducibility

Some computations allow shortcuts which can be used to speed them up. Consider the operation of raising a number to a positive integer power. It is possible, for example, to calculate by multiplying 13 by itself seven times,However, the shortcut of squaring three times considerably speeds up the computation,It is often quite difficult to determine whether a given computation can be sped up by means of such a trick. Computations that cannot be sped up are said to exhibit computational irreducibility.

Computational irreducibility

While many computations admit shortcuts that allow them to be performed more rapidly, others cannot be sped up. Computations that cannot be sped up by means of any shortcut are called computationally irreducible. The principle of computational irreducibility says that the only way to determine the answer to a computationally irreducible question is to perform, or simulate, the computation. Some irreducible computations can be sped up by performing them on faster hardware, as the principle refers only to computation time.According to Wolfram (2002, p. 741), if the behavior of a system is obviously simple--and is say either repetitive or nested--then it will always be computationally reducible. But it follows from the principle of computational equivalence that in practically all other cases it will be computationally irreducible." Here, "practically all" refers to cases that arise naturally or from a simple..

Pairing function

A pairing function is a function that reversibly maps onto , where denotes nonnegative integers. Pairing functions arise naturally in the demonstration that the cardinalities of the rationals and the nonnegative integers are the same, i.e., , where is known as aleph-0, originally due to Georg Cantor. Pairing functions also arise in coding problems, where a vector of integer values is to be folded onto a single integer value reversibly.515202633414101419253236913182423581217112471112345Let(1)then Hopcroft and Ullman (1979, p. 169) define the pairing function(2)(3)illustrated in the table above, where . The inverse may computed from(4)(5)(6)(7)where is the floor function.51522303949604101623314050361117243241237121825331148131926002591420012345The Hopcroft-Ullman function can be reparameterized so that and are in rather than . This function is known as the Cantor function and is given by(8)illustrated in..

Universality

Universality is the property of being able to perform different tasks with the same underlying construction just by being programmed in a different way. Universal systems are effectively capable of emulating any other system. Digital computers are universal, but proving that idealized computational systems are universal can be extremely difficult and technical. Nonetheless, examples have been found in many systems, and any system that can be translated into another system known to be universal must itself be universal. Specific universal Turing machines, universal cellular automata (in both one and two dimensions), and universal cyclic tag systems are known, although the smallest universal example is known only in the case of elementary cellular automata (Wolfram 2002, Cook 2004).

Multiway system

A multiway system is a kind of substitution system in which multiple states are permitted at any stage. This accommodates rule systems in which there is more than one possible way to perform an update.A simple example is a string substitution system. For instance, take the rules and the initial condition . There are two choices for how to proceed. Applying the first rule yields the evolution , while applying the second rule yields the evolution . So at the first step, there is a single state (), at the second step there are two states , and at the third step there is a single state .A path through a multiway system arising from a choice of which substitutions to make is called an evolution. Typically, a multiway system will have a large number of possible evolutions. For example, consider strings of s and s with the rule . Then most strings will have more than one occurrence of the substring , and each occurrence leads down another path in the multiway system...

Chaitin's constant

A Chaitin's constant, also called a Chaitin omega number, introduced by Chaitin (1975), is the halting probability of a universal prefix-free (self-delimiting) Turing machine. Every Chaitin constant is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable (Chaitin 1975).A Chaitin's constant can therefore be defined as(1)which gives the probability that for any set of instructions, a particular prefix-free universal Turing machine will halt, where is the size in bits of program .The value of a Chaitin constant is highly machine-dependent. In some cases, it can even be proved that not a single bit can be computed (Solovay 2000).Chaitin constants are perhaps the most obvious specific example of uncomputable numbers. They are also known to be transcendental.Calude et..

Causal network

A causal network is an acyclic digraph arising from an evolution of a substitution system, and representing its history. The illustration above shows a causal network corresponding to the rules (applied in a left-to-right scan) and initial condition (Wolfram 2002, p. 498, fig. a).The figure above shows the procedure for diagrammatically creating a causal network from a mobile automaton (Wolfram 2002, pp. 488-489).In an evolution of a multiway system, each substitution event is a vertex in a causal network. Two events which are related by causal dependence, meaning one occurs just before the other, have an edge between the corresponding vertices in the causal network. More precisely, the edge is a directed edge leading from the past event to the future event.Some causal networks are independent of the choice of evolution, and these are calledcausally invariant...

Reducible

A set of integers is said to be one-one reducible to a set () if there is a one-one recursive function such that for every ,(1)and(2)Similarly, a set of integers is many-one reducible to set () if there is a recursive function such that for every ,(3)and(4)Here, the two reducibility relations are reflexivity and transitivity.One-one reducibility implies many-one reducibility. Any set reducible to a recursive set is recursive itself. Any set reducible to a recursively enumerable set is recursively enumerable itself. The above facts are commonly used in recursive undecidability proofs done by reduction to nonrecursive sets.Two sets are one-one/many-one equivalent if each of them is one-one/many-one reducible to the other. One-one equivalence, many-one equivalence, and recursive isomorphism are all equivalence relations.If sets and are recursively isomorphic, then they are one-one equivalent and vice versa.If a class (also called..

Causal invariance

A multiway system that generates causal networks which are all isomorphic as acyclic digraphs is said to exhibit causal invariance, and the causal network itself is also said to be causally invariant. Essentially, causal invariance means that no matter which evolution is chosen for a system, the history is the same in the sense that the same events occur and they have the same causal relationships. The figures above illustrate two nontrivial substitution systems that exhibit the same causal networks independent of the order in which the rules are applied (Wolfram 2002, pp. 500-501).Whenever two rule hypotheses overlap in an evolution, the corresponding system is not causally invariant. Hence, the simplest way to search for causal invariance is to use rules whose hypotheses can never overlap except trivially. An overlap can involve one or two strings. For example, does not have any overlaps. However, can overlap as , and the set of strings..

Recursive function

The term "recursive function" is often used informally to describe any function that is defined with recursion. There are several formal counterparts to this informal definition, many of which only differ in trivial respects.Kleene (1952) defines a "partial recursive function" of nonnegative integers to be any function that is defined by a noncontradictory system of equations whose left and right sides are composed from (1) function symbols (for example, , , , etc.), (2) variables for nonnegative integers (for example, , , , etc.), (3) the constant 0, and (4) the successor function .For example,(1)(2)(3)(4)defines to be the function that computes the product of and .Note that the equations might not uniquely determine the value of for every possible input, and in that sense the definition is "partial." If the system of equations determines the value of f for every input, then the definition is said to be "total."..

Rabin's compression theorem

For any constructible function , there exists a function such that for all functions , the following two statements are equivalent: 1. There exists an algorithm such that for all inputs , computes in volume . 2. is constructible and . Here, the volume is the combined number of active edges during all steps, which is the number of state-changes needed to run a certain Turing machine on a particular input.

Deterministic

A Turing machine is called deterministic if there is always at most one instruction associated with a given present internal state/tape state pair . Otherwise, it is called nondeterministic (Itô 1987, p. 137).In prediction theory, let be a weakly stationary process, and let be a subspace spanned by the (with ). If is independent of so that for every , then is said to be deterministic (Itô 1987, p. 1463).

Constructible function

A function is said to be constructible if some algorithm computes it, in binary, within volume , i.e., . Here, the volume is the combined number of active edges during all steps, which is the number of state-changes needed to run a certain Turing machine on a particular input.

Primitive recursive function

As first shown by Meyer and Ritchie (1967), do-loops (which have a fixed iteration limit) are a special case of while-loops. A function that can be implemented using only do-loops is called primitive recursive. (In contrast, a computable function can be coded using a combination of for- and while-loops, or while-loops only.) Examples of primitive recursive functions include power, greatest common divisor, and (the function giving the th prime).The Ackermann function is the simplest example of a well-defined total function that is computable but not primitive recursive, providing a counterexample to the belief in the early 1900s that every computable function was also primitive recursive (Dötzel 1991; Wolfram 2002, p. 907).

Selection sort

A sorting algorithm which makes passes over a set of elements, in each pass selecting the smallest element and deleting it from the set. This algorithm has running time , compared to for the best algorithms (Skiena 1990, p. 14).

Quicksort

Quicksort is the fastest known comparison-based sorting algorithm (on average, and for a large number of elements), requiring steps. Quicksort is a recursive algorithm which first partitions an array according to several rules (Sedgewick 1978): 1. Some key is in its final position in the array (i.e., if it is the th smallest, it is in position ). 2. All the elements to the left of are less than or equal to . The elements , , ..., are called the "left subfile." 3. All the elements to the right of are greater than or equal to . The elements , ..., are called the "right subfile." Quicksort was invented by Hoare (1961, 1962), has undergone extensive analysis and scrutiny (Sedgewick 1975, 1977, 1978), and is known to be about twice as fast as the next fastest sorting algorithm. In the worst case, however, quicksort is a slow algorithm (and for quicksort, "worst case" corresponds to already sorted).The average time for the algorithm..

Pancake sorting

Assume that numbered pancakes are stacked, and that a spatula can be used to reverse the order of the top pancakes for . Then the pancake sorting problem asks how many such "prefix reversals" are sufficient to sort an arbitrary stack (Skiena 1990, p. 48).The maximum numbers of flips needed to sort a random stack of , 2, 3, ... pancakes are 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, ... (OEIS A058986), with the number of maximal stacks for , 3, ... being 1, 1, 3, 20, 2, 35, 455, ... (OEIS A067607).The following table (OEIS A092113) gives the numbers of stacks of pancakes requiring flips. A flattened version is shown above as a binary plot.0123456781121131221413611351412354820615207919928113327163014954313571903101635For example, the three stacks of four pancakes requiring the maximum of four flips are , , and , which can be ordered using the flip sequences , , and , respectively (illustrated above). Similarly, the two stacks of six pancakes..

Merge sort

A merge sort (or collation sort) is the combination of two or more ordered lists into a single ordered list (Knuth 1998, p. 158). Merge sorting was one of the first methods proposed for computer sorting, and was first proposed by John von Neumann in 1945 (Knuth 1998, p. 159). Variants include two-way, natural two-way, straight two-way, and list merge sorts.The minimum number of comparisons needed for a merge sort of elements for , 2, ... are 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ... (OEIS A001768). An upper limit is given by the sequence(1)where(2)where is the floor function (Steinhaus 1999, pp. 55-56), or equivalently,(3)giving 0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, ... (OEIS A001855).

Qubit

A qubit (or quantum bit) is the analog of a bit for quantum computation. Unlike an ordinary bit, which may only assume two possible values (usually called 0 and 1), a qubit may assume a continuum of values of the form where and are arbitrary complex numbers satisfying .

Bloch sphere

The qubit can be represented as a point on a unit sphere called the Bloch sphere. Define the angles and by letting and . Here, is taken to be real, which can always be made real by multiplying by an overall phase factor (that is unobservable). Then is represented by the unit vector (, , ) called the Bloch vector.

Signaling nan

In the IEEE 754-2008 standard (referred to as IEEE 754 henceforth), a signaling NaN or sNaN is a NaN which is signaling in the sense of being most commonly returned in conjunction with various exceptions and handling mechanisms defined therefor. This is in contrast to the quiet NaN (qNaN) which rarely signals a floating-point exception of any kind (IEEE Computer Society 2008).Within the framework documentation, it is suggested that sNaNs be implemented in such a way as to afford meaningful representations for uninitialized variables and arithmetic-like enhancements which may naturally fall beyond the scope of the standard. In particular, sNaNs are largely reserved for operands which signal exceptions for nearly every general-computational and signaling-computational operation though, in rare instances, qNaNs may also result from such contexts...

Quiet nan

In the IEEE 754-2008 standard (referred to as IEEE 754 henceforth), a quiet NaN or qNaN is a NaN which is quiet in the sense of rarely signaling a floating-point exception. This is in contrast to the signaling NaN (sNaN) which often occurs in conjunction with any number of exceptions and handling mechanisms defined therefor (IEEE Computer Society 2008).Within the framework documentation, it is suggested that qNaNs be implemented in such a way as to afford useful diagnostic information regarding invalid or unavailable data and results. Under the default exception handling mechanisms provided within IEEE 754, any operation which signals an invalid operation exception and for which a floating-point result is expected shall return a quiet NaN; qNaNs may also result from operations not delivering a floating-point result, though in practice, these operations are far more likely to output sNaNs instead...

Partial evaluation

Partial evaluation is a branch of computer science studying program transformation via specialization. Any function can be specialized by fixing one or more of its inputs to a particular values. The number of inputs to the program resulting from specialization is the initial number of inputs minus the number of inputs whose values are constants. These specialized programs are also called residual programs.Kleene's s-m-n theorem established a theoretical possibility of function specialization. Partial evaluation applies this idea to computer programs. Note that Kleene's theorem does not address the efficiency of specialized functions whereas the goal of partial evaluation is program optimization.Partial evaluation is accomplished by detecting code fragments depending exclusively on specialized variables whose values are fixed and by symbolically precomputing these fragments. The residual program will run faster because..

Nan

In the IEEE 754-2008 standard (referred to as IEEE 754 henceforth), NaN (or "not a number") is a symbolic floating-point representation which is neither a signed infinity nor a finite number. In general, NaNs occur as the output of computations which are somehow "indeterminate," e.g., when attempting to compute quantities such as , , or .The use of NaN representations is a relatively new development. Traditionally, the computation of indeterminate quantities such as or was treated as an unrecoverable error which caused a computation to halt. In practice, however, it sometimes makes sense for a computation to continue despite encountering such a scenario; in these situations, unnecessary halting can be avoided by specifying that the computation of expressions like and output NaN rather than halting the program (Goldberg 1991).Ostensibly, a NaN output should carry with it some degree of diagnostic information regarding..

Universal hash function

Let be efficiently computable by an algorithm (solving a P-problem). For fixed , view as a function of that maps (or hashes) bits to bits. Let , then is said to be a (pairwise independent) universal hash function if, for distinct and for all ,i.e., maps all distinct independently and uniformly.These functions are easily constructible (Wegman and Carter 1981, Luby 1996).

Rsa encryption

A public-key cryptography algorithm which uses prime factorization as the trapdoor one-way function. Define(1)for and primes. Also define a private key and a public key such that(2)(3)where is the totient function, denotes the greatest common divisor (so means that and are relatively prime), and is a congruence. Let the message be converted to a number . The sender then makes and public and sends(4)To decode, the receiver (who knows ) computes(5)since is an integer. In order to crack the code, must be found. But this requires factorization of since(6)Both and should be picked so that and are divisible by large primes, since otherwise the Pollard p-1 factorization method or Williams p+1 factorization method potentially factor easily. It is also desirable to have large and divisible by large primes.It is possible to break the cryptosystem by repeated encryption if a unit of has small field order (Simmons and Norris 1977, Meijer 1996), where..

Hash function

A hash function projects a value from a set with many (or even an infinite number of) members to a value from a set with a fixed number of (fewer) members. Hash functions are not reversible. A hash function might, for instance, be defined as , where , , and is the floor function.Hash functions can be used to determine if two objects are equal (possibly with a fixed average number of mistakes). Other common uses of hash functions are checksums over a large amount of data (e.g., the cyclic redundancy check [CRC]) and finding an entry in a database by a key value. The UNIX c-shell (csh) uses a hash table to store the location of executable programs. As a result adding new executables in a user's search path requires regeneration of the hash table using the rehash command before these programs can be executed without specifying the complete path.To illustrate the use of hash functions in database lookups, consider a database consisting of an array containing..

Tree searching

In database structures, two quantities are generally of interest: the average number of comparisons required to 1. Find an existing random record, and 2. Insert a new random record into a data structure. Some constants which arise in the theory of digital tree searching are(1)(2)(3)(4)(5)(6)(OEIS A065442 and A065443), where is a q-polygamma function. Erdős (1948) proved that is irrational, and is sometimes known as the Erdős-Borwein constant.The expected number of comparisons for a successful search is(7)(8)and for an unsuccessful search is(9)(10)(OEIS A086309 and A086310). Here is the Euler-Mascheroni constant, , , and are small-amplitude periodic functions, and lg is the base 2 logarithm.The variance for searching is(11)(12)(OEIS A086311) and for inserting is(13)(14)(OEIS A086312).The expected number of pairs of twin vacancies in a digital search tree is(15)where(16)(17)(OEIS A086313), which can also be written(18)(Flajolet..

Pair

A set of two numbers or objects linked in some way is said to be a pair. The pair and is usually denoted (, ), and is generally considered to be ordered, making it a 2-tuple. In certain circumstances, pairs are also called brothers or twins.

Ordered pair

A pair of quantities (, ) where ordering is significant, so (, ) is considered distinct from (, ) for .

Encroaching list set

A structure consisting of an ordered set of sorted lists such that the head and tail entries of later lists nest within earlier ones. For example, an encroaching list set for is given by . Encroaching list sets can be computed using EncroachingListSet[l] in the Wolfram Language package Combinatorica` .It is conjectured that the number of encroaching lists associated with a random permutation of size is for sufficiently large (Skiena 1988; Skiena 1990, p. 78).

Nat

The unit of information obtained by using the natural logarithm instead of the base-2 logarithm when defining entropy and related information theoretic functions. When is used instead, information content is obtained in the more convenient unit of bits.

String

A string of length on an alphabet of characters is an arrangement of not necessarily distinct symbols from . There are such distinct strings.For example, the strings of length on the alphabet are , , , , , , , and .In the Wolfram Language, strings of length in the alphabet consisting of the members of a list can be enumerated using Tuples[list, n].

Stack

A stack is a data structure which is a special kind of list in which elements may be added to or removed from the top only. These actions are called a push or a pop, respectively. Actions may be taken by popping one or more values, operating on them, and then pushing the result back onto the stack.Stacks are used as the basis for computer languages such as FORTH, PostScript® (Adobe Systems), and the RPN language used in Hewlett-Packard® programmable calculators.Another notion of the term stack is the algebraicgeometry stack of Grothendieck.

Multiset

A set-like object in which order is ignored, but multiplicity is explicitly significant. Therefore, multisets and are equivalent, but and differ. The number of multisets of length on symbols is called multichoose , denoted .

Rsa number

RSA numbers are difficult to-factor composite numbers having exactly two prime factors (i.e., so-called semiprimes) that were listed in the Factoring Challenge of RSA Security®--a challenge that is now withdrawn and no longer active.While RSA numbers are much smaller than the largest known primes, their factorization is significant because of the curious property of numbers that proving or disproving a number to be prime ("primality testing") seems to be much easier than actually identifying the factors of a number ("prime factorization"). Thus, while it is trivial to multiply two large numbers and together, it can be extremely difficult to determine the factors if only their product is given. With some ingenuity, this property can be used to create practical and efficient encryption systems for electronic data.RSA Laboratories sponsored the RSA Factoring Challenge to encourage research into computational..

P versus np problem

The P versus NP problem is the determination of whether all NP-problems are actually P-problems. If P and NP are not equivalent, then the solution of NP-problems requires (in the worst case) an exhaustive search, while if they are, then asymptotically faster algorithms may exist.The answer is not currently known, but determination of the status of this question would have dramatic consequences for the potential speed with which many difficult and important problems could be solved.In the Season 1 episode "Uncertainty Principle" (2005) of the television crime drama NUMB3RS, math genius Charlie Eppes uses the game minesweeper as an analogy for the P vs. NP problem.

Megabyte

One million () bytes. Unfortunately, the term is sometimes also used to mean bytes. Furthermore, a third meaning of the term refers to bytes when formatting 3.5-inch 1.44-"megabyte" floppy disks. However, the latter usages are deprecated, and the term mebibyte is preferred for bytes.

Mebibyte

bytes. Although the term megabyte is almost universally used to refer to bytes, such usage is deprecated in favor of the standard SI naming convention of 1 megabyte being equal to bytes.

List

A list is a data structure consisting of an ordered set of elements, each of which may be a number, another list, etc. A list is usually denoted (, , ..., ) or , and may also be interpreted as a vector (specifically, an n-vector) or an n-tuple. Multiplicity matters in a list, so (1, 1, 2) and (1, 2) are not equivalent.

Byte

A binary unit of information equal to 8 bits. Unfortunately, the storage of binary numbers in computers is not entirely standardized. Because computers store information in 8-bit bytes (where a bit is a single binary digit), depending on the "word size" of the machine, numbers requiring more than 8 bits must be stored in multiple bytes. The usual FORTRAN77 integer size is 4 bytes long. However, a number represented as (byte1 byte2 byte3 byte4) in a VAX would be read and interpreted as (byte4 byte3 byte2 byte1) on a Sun. The situation is even worse for floating-point (real) numbers, which are represented in binary as a mantissa and characteristic, and worse still for long (8-byte) reals!The naming of large multiples of bytes follows standard SI prefixes, as summarized in the following table.bytesunitkilobytemegabytegigabyteterabytepetabyteexabyteUnfortunately, there is some ambiguity in the meanings of the prefixes kilo-,..

Push

An action which adds a single element to the top of a stack, turning the stack (, , ..., ) into (, , , ..., ).

Hyperstring

A hyperstring is a simple semi-Hamiltonian acyclic digraph with a labeling of the edges in such that, for all vertices , either or , where a set is the set of label strings represented by the paths .

Pop

In computer science, a pop is an action which removes the initial element from the top of a queue or stack, turning the list (, , ..., ) into (, ..., ) and returns the removed element .

Bit length

The number of binary bits necessary to represent a number, given explicitly by(1)(2)where is the ceiling function, is the floor function, and is lg, the logarithm to base 2. For , 2, ..., the sequence of bit lengths is given by 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, ... (OEIS A036377). The function is given by the Wolfram Language function BitLength[n].

Archimedes' recurrence formula

Let and be the perimeters of the circumscribed and inscribed -gon and and the perimeters of the circumscribed and inscribed -gon. Then(1)(2)The first follows from the fact that side lengths of the polygons on a circle of radius are(3)(4)so(5)(6)But(7)(8)Using the identity(9)then gives(10)The second follows from(11)Using the identity(12)gives(13)(14)(15)(16)Successive application gives the Archimedes algorithm, which can be used to provide successive approximations to pi ().

Archimedes algorithm

Successive application of Archimedes' recurrence formula gives the Archimedes algorithm, which can be used to provide successive approximations to (pi). The algorithm is also called the Borchardt-Pfaff algorithm. Archimedes obtained the first rigorous approximation of by circumscribing and inscribing -gons on a circle. From Archimedes' recurrence formula, the circumferences and of the circumscribed and inscribed polygons are(1)(2)where(3)For a hexagon, and(4)(5)where . The first iteration of Archimedes' recurrence formula then gives(6)(7)(8)Additional iterations do not have simple closed forms, but the numerical approximations for , 1, 2, 3, 4 (corresponding to 6-, 12-, 24-, 48-, and 96-gons) are(9)(10)(11)(12)(13)By taking (a 96-gon) and using strict inequalities to convert irrational bounds to rational bounds at each step, Archimedes obtained the slightly looser result(14)..

Heap

A sequence forms a (binary) heap if it satisfies for , where is the floor function, which is equivalent to and for . The first member must therefore be the smallest. A heap can be viewed as a labeled binary tree in which the label of the th node is smaller than the labels of any of its descendents (Skiena 1990, p. 35). Heaps support arbitrary insertion and seeking/deletion of the minimum value in times per update (Skiena 1990, p. 38).A list can be converted to a heap in times using an algorithm due to Floyd (1964). A binary heap can be generated from a permutation using Heapify[p] in the Wolfram Language package Combinatorica` . For example, given the random permutation , Floyd's algorithm gives the heap (left figure). The right figure shows a heap containing 30 elements.A permutation can be tested to see if it is a heap using the following Wolfram Language functions. HeapQ[a_List] := Module[{i, n = Length[a]}, And @@ Table[a[[Floor[i/2]]]..

Automatic set

A -automatic set is a set of integers whose base- representations form a regular language, i.e., a language accepted by a finite automaton or state machine. If bases and are incompatible (do not have a common power) and if an -automatic set and -automatic set are both of density 0 over the integers, then it is believed that is finite. However, this problem has not been settled.Some automatic sets, such as the 2-automatic consisting of numbers whose binary representations contain at most two 1s: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, ... (OEIS A048645) have a simple arithmetic expression. However, this is not the case for general -automatic sets.

Universal turing machine

A Turing machine which, by appropriate programming using a finite length of input tape, can act as any Turing machine whatsoever. In his seminal paper, Turing himself gave the first construction for a universal Turing machine (Turing 1937, 1938). Shannon (1956) showed that two colors were sufficient, so long as enough states were used. Minsky (1962) discovered a 7-state 4-color universal Turing machine, illustrated above (Wolfram 2002, p. 706). Note that the 20th rule specifies that the Turing machine should halt, as indicated by leaving the head stationary and not changing its state. Upon conversion to a 2-color machine, Minsky's universal Turing machine requires 43 states.Comparatively little more was published about small universal Turing machines until Rogozhin (1996) found examples with the numbers of states and colors given by (24, 2), (10, 3), (7, 4), (5, 5), (4, 6), (3, 10), and (2, 18) (Wolfram 2002, p. 1119).A 2-state..

Subscribe to our updates
79 345 subscribers already with us
Math Subcategories
Check the price
for your project