Computational systems

Math Topics A - Z listing


Computational systems Topics

Sort by:

Block growth

Let be a sequence over a finite alphabet (all the entries are elements of ). Define the block growth function of a sequence to be the number of admissible words of length . For example, in the sequence , the following words are admissible lengthadmissible words1234so , , , , and so on. Notice that , so the block growth function is always nondecreasing. This is because any admissible word of length can be extended rightwards to produce an admissible word of length . Moreover, suppose for some . Then each admissible word of length extends to a unique admissible word of length .For a sequence in which each substring of length uniquely determines the next symbol in the sequence, there are only finitely many strings of length , so the process must eventually cycle and the sequence must be eventually periodic. This gives us the following theorems: 1. If the sequence is eventually periodic, with least period , then is strictly increasing until it reaches , and is..

String rewriting system

A substitution system in which rules are used to operate on a string consisting of letters of a certain alphabet. String rewriting systems are also variously known as rewriting systems, reduction systems, or term rewriting systems. String rewriting is a particularly useful technique for generating successive iterations of certain types of fractals, such as the box fractal, Cantor dust, Cantor square fractal, and Sierpiński carpet.

Generalized mobile automaton

A generalized mobile automaton is a generalization of the mobile automaton in which the automaton may have more than one active cell. Generalized mobile automata allow for more change in a single update, so interesting behavior can develop more rapidly. Like cellular automata, the generalized mobile automata can involve parallel computing. During an updating event, every active cell is updated based on the value of that cell and its neighbors. The update determines the new color for the active cell, and specifies which if any of it and its neighbors become active cells. A cell becomes active if any of the previous step's events determined that it should become active. An example is shown above (Wolfram 2002, p. 76).Its rule structure allows for the creation and destruction of the active cells, but only updates values of the active cells. This way there is no overlap, even if neighboring cells are active. A cellular automaton is a special..

Sequential substitution system

A sequential substitution system is a substitution system in which a string is scanned from left to right for the first occurrence of the first rule pattern. If the pattern is found, the rule is applied and processing advances to the next step. If the first rule pattern does not occur, the string is scanned from left to right for the first occurrence of the second rule pattern. If the pattern is found, the rule is applied and processing advances to the next step, and so on. If none of the rule patterns match at some step, the string repeats indefinitely for all subsequent steps. For example, consider the single rule and the initial string , illustrated above. The first step yields , the second step yields , and from there on the system repeats since there are no more matches of the pattern rule.A more interesting sequential substitution system is illustrated above (Wolfram 2002, p. 90). This system has two rules and the initial condition . It builds..

Dyck language

The simplest algebraic language, denoted . If is the alphabet , then is the set of words of which satisfy 1. , where is the numbers of letters in the word , and 2. if is factored as , where and are words of , then .

Register machine

An idealized computing machine consisting of a fixed set of data registers and set of instructions for operating on them. Register machines are also known as counter machines and program machines. Early investigators included Shepherdson and Sturgis (1963) and Minsky (1961). Somewhat similar constructs were also part of Kurt Gödel's 1931 work on representing logic within arithmetic (Wolfram 2002, p. 896).Wolfram (2002) considers machines with two registers and two operations: "increments" and "decrement-jumps." The above illustration shows 30 steps of a five-instruction program that generate nonrepetitive output (Wolfram 2002, p. 99).

De bruijn sequence

The shortest circular sequence of length such that every string of length on the alphabet of size occurs as a contiguous subrange of the sequence described by . For example, a de Bruijn sequence of order on the alphabet is given by .A de Bruijn sequence can be generated in the Wolfram Language using DeBruijnSequence[list, n]. Every de Bruijn sequence corresponds to an Eulerian cycle on a de Bruijn graph. Surprisingly, it turns out that the lexicographic sequence of Lyndon words of lengths divisible by gives the lexicographically smallest de Bruijn sequence (Ruskey).de Bruijn sequences can be generated by feedback shift registers (Golomb 1967; Ronse 1984; Skiena 1990, p. 196).

Cyclic tag system

A tag system in which a list of tag rules (each of a special form) is applied to a system in sequential order and then starting again from the first rule. In a cyclic tag system, each set of tag rules has the special structure that a pattern is appended if (and only if) the first element of the current pattern is a 1 and that independent of whether the first element is 0 or 1, the first element is then deleted.For example, consider a state consisting of white and black cells, labeled 0 and 1, respectively, and the cyclic tag system and with initial state , illustrated above. As required, this system always removes the first element and appends specific patterns iff the first cell is black. 1. At the first step, the leftmost element is 1, so applying the first rule gives , since is appended, and the initial is then deleted. 2. Applying the second rule adds at the end and removes the first element, yielding . 3. Again applying the first rule adds at the end and (as always)..

Paterson's worms

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...


A reduction system is called confluent (or globally confluent) if, for all , , and such that and , there exists a such that and . A reduction system is said to be locally confluent if, for all , , such that and , there exists a such that and . Here, the notation indicates that is reduced to in one step, and indicates that is reduced to in zero or more steps.A reduction system is confluent iff it has Church-Rosser property (Wolfram 2002, p. 1036). In finitely terminating reduction systems, global and local confluence are equivalent, for instance in the systems shown above. Reduction systems that are both finitely terminating and confluent are called convergent. In a convergent reduction system, unique normal forms exist for all expressions.The problem of determining whether a given reduction system is confluent is recursivelyundecidable.The property of being confluent is called confluence. Confluence is a necessary conditionfor causal..


A string or word is said to be admissible if that word appears in a given sequence. For example, in the sequence , , , are all admissible, but is inadmissible.

Abstract machine

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."..


The concatenation of two strings and is the string formed by joining and . Thus the concatenation of the strings "book" and "case" is the string "bookcase". The concatenation of two strings and is often denoted , , or, in the Wolfram Language, . Concatenation is an associative operation, so that the concatenation of three or more strings, for example , , etc., is well-defined.The concatenation of two or more numbers is the number formed by concatenating their numerals. For example, the concatenation of 1, 234, and 5678 is 12345678. The value of the result depends on the numeric base, which is typically understood from context.The formula for the concatenation of numbers and in base iswhereis the number length of in base and is the floor function.

Mobile automaton

A class of automata similar to cellular automata but which have a single "active" cell instead of updating all cells in parallel. In a mobile automaton, the evolution rules apply only to the active cell, and also specify how the active cell moves from one generation to the next. All cells that are not active remain the same from one generation to the next. Mobile automata can therefore be considered a hybrid between elementary cellular automata and Turing machines. An example is shown above (Wolfram 2002, p. 71).Two-dimensional mobile automata are also possible, but the number of possible rulesis much larger than can be systematically categorized (Wolfram 2002, p. 931).


Turmites, also called turning machines, are 2-dimensional Turing machines in which the "tape" consists of a grid of spaces that can be written and erased by an active ("head") element that turns at each iteration on the basis of the state of its current grid square. The "head" of the system is usually called a "vant," "ant," or "turmite" on square grids, and a "bee," "worm," or "turtle" on hexagonal grids. (The term "turtle" is named after Seymour Papert's turtle geometry). The turmite tracks its position, direction, and current state.Amazingly, the turmite with rule illustrated above mimics binary counting. In this turmite, the pattern of bands above the red line corresponds to incrementing binary digits. After each cycle constructing the upper pattern, the same pattern is produced (mirrored left-to-right) below the red..

Turing machine

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..

Tag system

A tag system is set of rules that specifies a fixed number of elements (commonly denoted or ) be removed from the beginning of a sequence and a set of elements to be appended ("tagged" onto the end) based on the elements that were removed from the beginning. For example, consider the tag system shown in the illustration above, in which black represents 1 and white represents 0. Then the starting pattern is "1" and the transition rules are and (Wolfram 2002, p. 93).Tag systems were first considered by Post in 1920 (Wolfram 2002, p. 894), although these results did not become widely known until published much later (Post 1943). Post apparently studied all of a certain type of tag system that involve removal and addition of no more than two elements at each step and concluded that none of them produced complicated behavior. However, looking at rules that remove three elements at each step, he discovered a particular rule..

Langton's ant

A 4-state two-dimensional Turing machine invented in the 1980s. The ant starts out on a grid containing black and white cells, and then follows the following set of rules. 1. If the ant is on a black square, it turns right and moves forward one unit. 2. If the ant is on a white square, it turns left and moves forward one unit. 3. When the ant leaves a square, it inverts the color. When the ant is started on an empty grid, it eventually builds a "highway" that is a series of 104 steps that repeat indefinitely, each time displacing the ant two pixels vertically and horizontally. The plots above show the ant starting from a completely white grid after 386 (left figure) and (right figure) steps. In the right figure, the highway is being constructed towards the lower right-hand corner. The fact that the ant's path is unbounded is guaranteed by the Cohen-Kung theorem. It is believed that no matter what initial pattern the ant is started on, it will eventually..

Busy beaver

A busy beaver is an -state, 2-color Turing machine which writes a maximum number of 1s before halting (Rado 1962; Lin and Rado 1965; Shallit 1998). Alternatively, some authors define a busy beaver as a Turing machine that performs a maximum number of steps when started on an initially blank tape before halting (Wolfram 2002, p. 889). The process leading to the solution of the three-state machine is discussed by Lin and Rado (1965) and the process leading to the solution of the four-state machine is discussed by Brady (1983) and Machlin and Stout (1990).For , 2, ..., (also known as Rado's sigma function) is given by 1, 4, 6, 13, ... (OEIS A028444; Rado 1962; Wolfram 2002, p. 889). The next few terms are not known, but examples have been constructed giving lower limits of and (Marxen). The illustration above shows a 3-state Turing machine with maximal (Lin and Rado 1965, Shallit 1998).The maximum number of steps which an -state 2-color Turing..

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