74
4 Advanced Neural Networks
The readers may find that the time evolution similar to the scattering of solitons 14
of the KdV equations is obtained. By the way, if we count the number of •
separated by ◦ from the left, this is [3, 2, 1] → [1, 2, 3], which is the same as
the sorting algorithm! Just in case, if we put in another initial state corresponding to
[3, 4, 2, 1, 2, 3], then [1, 2, 2, 3, 3, 4] is obtained: 15
• • • ◦ ◦ ◦ • • • • ◦ ◦ • • ◦ ◦ ◦ • ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ • • ◦ ◦ • • • ◦ • • ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ • • ◦ ◦ ◦ • ◦ ◦ • • • • ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ • • ◦ ◦ • ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • • • • ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • • ◦ • • ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • ◦ ◦ • • • ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ • ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • ◦ • • ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • • ◦
Namely, the physical phenomena described by the KdV equation seem to have
included the sorting algorithm. This discrete-time evolution model of discrete states
in a discrete space such as this box-ball system is called a cellular automaton.
Critical State and Turing Completeness of One-Dimensional
Cellular Automata
Stephen Wolfram, famous for the mathematical software Mathematica, was originally a physicist working on elementary particle theories. He is also famous
for classification of the one-dimensional (elementary) cellular automaton [54].
According to the classification, the dynamics of cellular automata are either:
I. Static (any initial state immediately stops and stabilizes)
II. Periodic (any initial state immediately stops or periodically moves and stabilizes)
III. Chaotic (the state does not stabilize even after sufficient time)
IV. Other than the above (the “edge” of stability and chaos)
14 Solutions of differential equations with a localized energy density are called solitons (in physics).
15 Note that if the solitons are not well-separated, calculation errors due to some phase shift will
occur.
4 Advanced Neural Networks
The readers may find that the time evolution similar to the scattering of solitons 14
of the KdV equations is obtained. By the way, if we count the number of •
separated by ◦ from the left, this is [3, 2, 1] → [1, 2, 3], which is the same as
the sorting algorithm! Just in case, if we put in another initial state corresponding to
[3, 4, 2, 1, 2, 3], then [1, 2, 2, 3, 3, 4] is obtained: 15
• • • ◦ ◦ ◦ • • • • ◦ ◦ • • ◦ ◦ ◦ • ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ • • ◦ ◦ • • • ◦ • • ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ • • ◦ ◦ ◦ • ◦ ◦ • • • • ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ • • ◦ ◦ • ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • • • • ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • • ◦ • • ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • ◦ ◦ • • • ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ • ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • ◦ • • ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ • • • • ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • ◦ ◦ ◦ • • ◦ ◦ ◦ ◦ ◦ ◦ • • ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ ◦ ◦ • • • • ◦
Namely, the physical phenomena described by the KdV equation seem to have
included the sorting algorithm. This discrete-time evolution model of discrete states
in a discrete space such as this box-ball system is called a cellular automaton.
Critical State and Turing Completeness of One-Dimensional
Cellular Automata
Stephen Wolfram, famous for the mathematical software Mathematica, was originally a physicist working on elementary particle theories. He is also famous
for classification of the one-dimensional (elementary) cellular automaton [54].
According to the classification, the dynamics of cellular automata are either:
I. Static (any initial state immediately stops and stabilizes)
II. Periodic (any initial state immediately stops or periodically moves and stabilizes)
III. Chaotic (the state does not stabilize even after sufficient time)
IV. Other than the above (the “edge” of stability and chaos)
14 Solutions of differential equations with a localized energy density are called solitons (in physics).
15 Note that if the solitons are not well-separated, calculation errors due to some phase shift will
occur.