Search NKS | Online
141 - 150 of 165 for FromDigits
![](/common/images/search/spacer.gif)
History of iterated maps
Newton's method from the late 1600s for finding roots of polynomials (already used in specific cases in antiquity) can be thought of as a smooth iterated map (see page 920 ) in which a rational function is repeatedly applied (see page 1101 ). … Starting in the 1930s iterated maps were sometimes considered as possible models in fields like population biology and business cycle theory—usually arising as discrete annualized versions of continuous equations like the Verhulst logistic differential equation from the mid-1800s. … (Already in the late 1940s John von Neumann had suggested using x 4x (1 - x) as a random number generator, commenting on its extraction of initial condition digits, as mentioned on page 921 .)
Multicolor Turing machines [from 2-color TMs]
Given rules in the form on page 888 for a Turing machine with s states and k colors the following yields an equivalent Turing machine with With[{c = Ceiling[Log[2, k]]}, (3 2 c + 2c - 7) s] states (always less than 6.03 k s ) and 2 colors:
TMToTM2[rule_, s_, k_] := # /. … Given an initial condition {i, list, n} the initial condition for the 2-color Turing machine is
With[{b = Ceiling[Log[2, k]]}, {i, Flatten[IntegerDigits[list, 2, b]], b n}]
In the 1940s it also became popular to use frequency modulation (FM) Sin[(1 + s[t]) ω t] , and in the 1970s pulse code modulation (PCM) (pulse trains for IntegerDigits[s[t], 2] ). … The regular signals come from such sources as navigation beacons, time standards, identification transponders and radars. … At present, the most intense overall artificial radio emission from the Earth is probably the 50 or 60 Hz hum from power lines.
Nonlinear feedback shift registers
Linear feedback shift registers of the kind discussed on page 974 can be generalized to allow any function f (note the slight analogy with cyclic tag systems):
NLFSRStep[f_, taps_, list_] := Append[Rest[list], f[list 〚 taps 〛 ]]
With the choice f=IntegerDigits[s, 2, 8] 〚 8 - # . {4, 2, 1} 〛 & and taps = {1, 2, 3} this is essentially a rule s elementary cellular automaton. … The main conclusion drawn from extensive data was that nothing like the linear theory applies.
(Assuming that the Turing machine starts in state 1, with a 0 under its head, other initial conditions can be encoded just by taking the values of cells on the left and right to give the digits of the numbers that are initially in the first two registers.) Given the list of successive configurations of the register machine, the steps that correspond to successive steps of Turing machine evolution can be obtained from
(Flatten[Partition[Complement[#, #-1], 1, 2]]&)[ Position[list, {_,{_,_,0}}]]
The program given above works for Turing machines with any number of states, but it requires some simple extensions to handle more than two possible colors for each cell.
Fractal dimensions [of additive cellular automata]
The total number of nonzero cells in the first t rows of the pattern generated by the evolution of an additive cellular automaton with k colors and weights w (see page 952 ) from a single initial 1 can be found using
g[w_, k_, t_] := Apply[Plus, Sign[NestList[Mod[ ListCorrelate[w, #, {-1, 1}, 0], k] &, {1}, t - 1]], {0, 1}]
The fractal dimension of this pattern is then given by the large m limit of
Log[k,g[w, k,k m + 1 ]/g[w, k, k m ]]
When k is prime it turns out that this can be computed as
d[w_, k_:2] := Log[k,Max[Abs[Eigenvalues[With[ {s = Length[w] - 1}, Map[Function[u, Map[Count[u, #] &, #1]], Map[Flatten[Map[Partition[Take[#, k + s - 1], s, 1] &, NestList[Mod[ListConvolve[w, #], k] &, #, k - 1]], 1] &, Map[Flatten[Map[{Table[0, {k - 1}], #} &, Append[#, 0]]] &, #]]] &[Array[IntegerDigits[#, k, s] &, k s - 1]]]]]]]
For rule 90 one gets d[{1, 0, 1}] = Log[2, 3] ≃ 1.58 .
But from experience with traditional mathematics one might have the impression that it would at some basic level be easier to get formulas for continuous systems. … As an example of what can happen in continuous systems consider iterated mappings x a x (1 - x) from page 920 . … The series has an accumulation of poles on the circle Abs[a] 2 1 ; the coefficient of x m turns out to have denominator
2^(m - DigitCount[m, 2, 1]) Apply[Times, Table[Cyclotomic[s, a]^Floor[(m - 1)/s], {s, m - 1}]]
For other iterated maps general formulas also seem rare.
The presence of apparent randomness in digit sequences of square roots, logarithms, numbers like π , and other mathematical constructs was presumably noticed by the 1600s (see page 911 ), and by the late 1800s it was being taken for granted. … One case where there was occasional discussion of origins of randomness from at least the early 1900s was fluid turbulence (see page 997 ).
An example due to Gregory Chaitin is the digits of the fraction Ω of initial conditions for which a universal system halts (essentially a compressed version—with various subtleties about limits—of the sequence from page 1127 giving the outcome for each initial condition). … As a reduced analog of algorithmic information theory one can for example ask what the simplest cellular automaton rule is that will generate a given sequence if started from a single black cell.
By the 1800s there was extensive debate about this, but in the early 1900s with the advent of statistical mechanics and measure theory the use of ensembles (see page 1020 ) turned discussions of probability away from issues of randomness in individual sequences. … In 1909 Emile Borel had formulated the notion of normal numbers (see page 912 ) whose infinite digit sequences contain all blocks with equal frequency. … Note that definitions of randomness given in dictionaries tend to emphasize lack of aim or purpose, in effect following the common legal approach of looking at underlying intentions (or say at physical construction of dice) rather than trying to tell if things are random from their observed behavior.
![](/common/images/search/spacer.gif)