Computer is conceptually a general-purpose device that is built upon a computing model, and manufactured by certain materials that can be used to implement the specific computing model. For instance, today’s electronic computer is conceptualized by Turing machine (TM) and composed of electronic components. Although the phenomenal growth of TM-based computing devices (e.g., electronic computer) follows Moore’s Law, the manufacturing technology of semiconductors will reach its limit in the next ten years, as predicted by Kaku in 2012 and today’s electronic computers have been unable to solve large-scale NP-complete problems due to the limitation of TMs. In the exploration of new computing models, bionic computing (e.g., neural networks, evolutionary computing, particle swarm optimization, and computing), optical computing, quantum computing, and biological computing have been proposed. It has been shown that the aforementioned computing models are equivalent to TM with respect to computability, while they lead to different levels of computational efficiency.
In 2016, Prof. XU, Jin proposed a novel computing model, called Probe Machine (PM). TM is a computing model with a linear data placement mode, and only adjacently placed data can be processed sequentially by individual operations. In contrast, PM is a fully parallel computing model with a data placement that is free of constrains in the space, and any pair of data can be viewed as adjacent, and can be processed directly. Therefore, PM has the powerful computation capability of processing numerous pairs of data simultaneously. It only requires one or several probe operations to solve some hard problems, which TM cannot solve in polynomial time. This is the first computing model going beyond TM. In particular XU, Jin shows that TM is a special case of PM. XU, Jin’s article “Probe Machine” was selected as one of the three featured papers by the IEEE Computational Intelligence Society for 2016, and the first CIS-publication outstanding paper in fourth quarter of 2016 by the IEEE Computational Intelligence Magazine.
PM is mathematically defined as a nine-tuple PM = (X, Y, σ1, σ2, τ, λ, η, Q, C) where the nine components denote the data library (X), probe library (Y ), data controller (σ1), probe controller (σ2), probe operation (τ), computing platform (λ), detector (η), true solution storage (Q), and residue collector (C). And the probes are divided into two types: connective and transitive probes. The connective operation does not consider the direction of information processing between data fibers, while the transitive operation does.
XU, Jin presents a model called nano-DNA PM model to implement the connective PM. In a nano-DNA PM model, the data are made by the complexus of nanoparticle and DNA molecule, and the probe is made by DNA molecule. To implement the concept of probe machine experimentally in biology, recently XU, Jin designed the two-dimensional (2D) and three-dimensional (3D) DNA origami models and realized them via biological method. In the experiment, 264 single stranded DNAs are assembled into the basic DNA origami modules by self-assembly method, that occupy about 5000bp of M13 circular single-stranded, which have about 7000bp bases. Then the other 2000bp bases are used to form three type signs. The three types DNA origamis can be constituted as 18 different DNA origami packets through 18 sets specific linkers. These DNA origamis are able to link between themselves in a planar manner via the complementary linkers, with the aid of covalent bindings between two bases of the paired linkers. Then these different DNA origamis enable the interconnectivity, and constitute the triangle and square, ultimately, form six-vertex graph with three different coloring methods, respectively. Thus the probe operations are fulfilled expectedly.
Besides computing model theory, another field of interest for XU, Jin is graph theory. Graph theory is one of the most important branches in combinatorial and discrete mathematics; the research of the coloring problem in graph theory is of great theoretical value and widely employed in the fields of combinatorial optimization, operations research, linear programming, electronics and information and computer science, etc. During the last five years, he has conducted a thorough research on the structure and coloring of maximal planar graphs, and published six articles of this series, his main achievement are as follows.
1) Establishing the extending-contracting operational system for maximal planar graphs. By the existing methods of generating maximal planar graphs, it is difficult to associate the structure of a maximal planar graph with its coloring, to overcome this weakness, XU, Jin proposed a novel technique, extending-contracting operation, to construct maximal planar graphs, which can also essentially reveal where any given maximal planar graph comes from. Starting with a 4-order maximal planar graph, one can generate any given maximal planar graphs by using the four basic extending-wheel operators of the operational system repeatedly. Though the extending-contracting operations, he also proved that every maximal planar graph with order n (≥9) and minimum degree ≥4 contains one of the five given basic configurations, thus clearly characterizing the structure of maximal planar graphs.
2) Classifying the 4-colorings of planar graphs into tree-colorings and cycle-colorings. In respect of 4-colorings of planar graphs, XU, Jin divided them into two types, namely, tree-colorings and cycle-colorings, the first researcher to attempt to classify the colorings of planar graphs systematically. This proposed classification method has proved to be an extremely useful tool in the study of planar graph coloring problems. Based on tree-colorings, he introduced a class of graphs called purely tree-colored maximal planar graphs, and put forward the corresponding constructing methods for such graphs, thereby, the proof of the uniquely 4-colorable maximal planar graph conjecture, which has 44 years of history, boils down to characterize the properties of purely tree-colored maximal planar graphs.
3) Putting forward a mathematic proof of four color problem. In mathematics, the four color problem states that, every planar graphs is 4-colorable, it is one of the world’s three major mathematical problems. Up to now, it is still regarded as surprisingly difficult to prove this seemingly simple expression in a rigorous mathematical way. During the research of cycle-colored graphs, XU, Jin discovered a kind of special cycle-colored graphs, 2-chromatic cycle-unchanged colored maximal planar graphs, which is made up of the union of two basic modules. Then, he carried out an in-depth research on basic modules, including proposing a complete constructing system for basic modules by using I-type operators and the basic extending-contracting operators, and proving that every basic module has a 4-colring satisfied that its exterior face has 4 colors. Based on these results, finally, he provided a mathematic proof of four color problem.
These results have been published in research paper Online, and reported successively in the “workshop of graph theory” organized by the Mathematics Institute of Chinese Academy of Sciences in 2016, “Academic Seminar on mathematical mechanization and Education Information Technology in 2016”, and “2016 Combinatorics and Related Academic Front Conference”. In addition, XU, Jin has made helpful and detailed discussions with scholars such as Professor ZHANG, Cunqun from the West Virginia University, DONG, Fengming from the Nanyang Technological University, YE, Yongnan from the Academia Sinica, and the mathematician ZHU, Xuding, etc. In 2017, XU, Jin is invited to make a 45-nimute report on his research work in four color problem to the International Conference on Combinatorics.
