Computational Thinking - Учебное пособие, страница 7

Many of them exhibitedsymmetry, some moved sideways in a crab-like fashion, andsome others crawled on two evolved limbs. This marked theemergence of mechanical artificial life. At the same time, thefield of Artificial Life continues to explore directions such asartificial chemistry, as well as traditionally-biologicalphenomena in artificial systems, ranging from co-evolutionaryadaptation and development to growth, self-replication, andself-repair.Membrane computing investigates computing modelsabstracted from the structure and the functioning of livingcells.

A generic membrane system is essentially a nestedhierarchical structure of cell-like compartments or regions,delimited by “membranes”. Each membrane enveloped regioncontains objects and transformation rules which modify theseobjects, as well as specify whether they will be transferredoutside or stay inside the region. The transfer thus provides36for communication between regions.The computational behavior of a membrane system starts withan initial input configuration and proceeds in a maximallyparallel manner by the non-deterministic choice ofapplication of the transformation rules, as well as of theobjects to which they are to be applied.

The output of thecomputation is then collected from an a priori determinedoutput membrane. Typical applications of membrane systemsinclude biology, computer science (computer graphics,public-keycryptography,approximationandsortingalgorithms, and solving computationally hard problems), andlinguistics.Amorphous computing is a paradigm that draws inspirationfrom the development of form (morphogenesis) in biologicalorganisms, wherein interactions of cells guided by a geneticprogram give rise to well-defined shapes and functionalstructures. Analogously, an amorphous computing mediumcomprises a multitude of irregularly placed, asynchronous,locally interacting computing elements.

These identicallyprogrammed “computational particles” communicate onlywith particles situated within a small given radius, and maygive rise to certain shapes and patterns such as, for example,any pre-specified planar graph. The goal of amorphouscomputing is to engineer specified coherent computationalbehaviors from the interaction of large quantities of suchunreliablecomputationalparticlesinterconnectedinunknown, irregular, and time-varying ways. At the same time,the emphasis is on devising new programming abstractionsthat would work well for amorphous computing environments.Amorphous computing has been used both as a programmingparadigm using traditional hardware, and as the basis for“cellular computing”.Nature as Implementation SubstrateAll the previously described computational techniques havebeen implemented until now mostly on traditional electronichardware. An entirely distinct category is that of computingparadigms that use a radically different type of “hardware”.37This category includes molecular computing and quantumcomputing.Molecular computing (known also as biomolecularcomputing, biocomputing, biochemical computing, DNAcomputing) is based on the idea that data can be encoded asbiomolecules – such as DNA strands, and molecular biologytools can be used to transform this data to perform, forexample, arithmetic or logic operations.

The birth of this fieldwas the 1994 breakthrough experiment by Leonard Adlemanwho solved a small instance of the Hamiltonian Path Problemsolely by manipulating DNA strands in test-tubes.There are many possible DNA bio-operations that one canuse for computations, such as: cut-and-paste operationsachievable by enzymes, synthesizing desired DNA strands upto a certain length, making exponentially many copies of aDNA strand, and reading-out the sequence of a DNA strand.These bio-operations and the Watson-Crick complementaritybinding have all been used to control DNA computations andDNA robotic operations.

While initial experiments solvedsimple instances of computational problems, more recentexperiments tackled successfully sophisticated computationalproblems, such as a 20-variable instance of the 3Satisfiability-Problem. The efforts towards building anautonomous molecular computer include implementations ofcomputational state transitions with biomolecules, and a DNAimplementation of a finite automaton with potentialapplications to the design of smart drugs.More importantly, since 1994, research in molecularcomputinghas gained several new dimensions. One of the mostsignificant achievements of molecular computing has been itscontribution to the massive stream of research innanosciences, by providing computational insights into anumber of fundamental issues. Perhaps the most notable is itscontribution to the understanding of self-assembly, which isamong the key concepts in nanosciences.

Recent experimentalresearch into programmable molecular-scale devices has38produced impressive self-assembled DNA nanostructures,such as cubes, octahedra, Sierpinski triangles, DNA origami,or intricate nanostructures that achieve computation such asbinary counting. Other experiments include the constructionof DNA-based logic circuits, and ribozymes that can be usedto perform logical operations and simple computations. Inaddition, an array of ingenious DNA nanomachines werebuilt with potential uses to nanofabrication, engineering, andcomputation: molecular switches that can be driven betweentwo conformations, DNA “tweezers”, DNA “walkers” thatcan be moved along a track, and autonomous molecularmotors.A significant amount of research in molecular computing hasbeen dedicated to the study of theoretical models of DNAcomputation and their properties.

Studies on thecomputational power of such models proved that varioussubsets of bio-operations can achieve the computationalpower of a Turing machine, showing thus that molecularcomputers are in principle possible.Quantum Computing is another paradigm that uses analternative “hardware” for performing computations. The ideaof a quantum computer that would run according to the lawsof quantum physics and operate exponentially faster than adeterministic electronic computer to simulate physics, wasfirst suggested by Feynman in 1982.

Subsequently, Deutschintroduced a formal model of quantum computing using aTuring machine formalism, and described a universalquantum computer.A quantum computer uses distinctively quantum mechanicalphenomena, such as superposition and entanglement, toperform operations on data stored as quantum bits (qubits). Aqubit can hold a 1, a 0, or a quantum superposition of these.A quantum computer operates by manipulating those qubitswith quantum logic gates.The 1980s saw an abundance of research in quantuminformation processing, such as applications to quantumcryptography, which, unlike its classical counterpart, is not39usually based on the complexity of computation, but on thespecial properties of quantum information. Recently, an openair experiment was reported in quantum cryptography (notinvolving optical cable) over a distance of 144 km, conductedbetween two Canary islands.The theoretical results that catapulted quantum computing tothe forefront of computing research were Shor’s quantumalgorithms for factoring integers and extracting discretelogarithms in polynomial time, obtained in 1994 – the sameyear that saw the first DNA computing experiment byAdleman.

A problem where quantum computers were shownto have a quadratic time advantage when compared toclassical computers is quantum database search. Possibleapplications of Shor’s algorithm include breaking RSAexponentially faster than an electronic computer. This joinedother exciting applications, such as quantum teleportation (atechnique that transfers a quantum state, but not matter orenergy, to an arbitrarily distant location), in sustaining thegeneral interest in quantum information processing.So far, the theory of quantum computing has been far moredeveloped than the practice. Practical quantum computationsuse a variety of implementation methods such as ion-traps,superconductors, nuclear magnetic resonance techniques, toname just a few. To date, the largest quantum computingexperiment uses liquid state nuclear magnetic resonancequantum information processors that can operate on up to 12qubits.Nature as ComputationSystems biology takes a systemic approach in focusing on theinteraction networks themselves, and on the properties of thebiological systems that arise because of these interactionnetworks.

Hence, for example, at the cell level, scientificresearch on organic components has focused strongly on fourdifferent interdependent interaction networks, based on fourdifferent “biochemical toolkits”: nucleic acids (DNA andRNA), proteins, lipids, carbohydrates, and their buildingblocks.40Gene interactions, together with the genes’ interactions withother substances in the cell, form the most basic interactionnetwork of an organism, the gene regulatory network.

Generegulatory networks perform information processing taskswithin the cell, including the assembly and maintenance ofthe other networks. Research into modeling gene regulatorynetworks includes qualitative models such as random andprobabilistic Boolean networks, asynchronous automata, andnetwork motifs.Another point of view, is that the entire genomic regulatorysystem can be thought of as a computational system, the“genomic computer”. Such a perspective has the potential toyield insights into both computation as humans historicallydesigned it, and computation as it occurs in nature. There areboth similarities and significant differences between thegenomic computer and an electronic computer.

Both performcomputations, the genomic computer on a much larger scale.However, in a genomic computer, molecular transport andmovement of ions through electrochemical gradients replacewires, causal coordination replaces imposed temporalsynchrony, changeable architecture replaces rigid structure,and communication channels are formed on an as-neededbasis. Both computers have a passive memory, but thegenomic computer does not place it in an a priori dedicatedand rigidly defined place; in addition, the genomic computerhas a dynamic memoryin which, for example, transcriptional subcircuits maintaingiven regulatory states. In a genomic computer robustness isachieved by different means, such as by rigorous selection:non(or poorly)-functional processes are rapidly degraded byvarious feedback mechanisms or, at the cell level, non(orpoorly)-functional cells are rapidly killed by apoptosis, and, atthe organism level, non (or poorly)-functional organisms arerapidly outcompeted by more fit species.