A logical calculus of the ideas immanent in nervous activity

Because of the “all-or-none” character of nervous activity, neural events and the relations among them can be treated by means of propositional logic. It is found that the behavior of every net can be described in these terms, with the addition of more complicated logical means for nets containing circles; and that for any logical expression satisfying certain conditions, one can find a net behaving in the fashion it describes. It is shown that many particular choices among possible neurophysiological assumptions are equivalent, in the sense that for every net behaving under one assumption, there exists another net which behaves under the other and gives the same results, although perhaps not in the same time. Various applications of the calculus are discussed.     

A logical calculus of the ideas immanent in nervous activity

Because of the “all-or-none” character of nervous activity, neural events and the relations among them can be treated by means of propositional logic. It is found that the behavior of every net can be described in these terms, with the addition of more complicated logical means for nets containing circles; and that for any logical expression satisfying certain conditions, one can find a net behaving in the fashion it describes. It is shown that many particular choices among possible neurophysiological assumptions are equivalent, in the sense that for every net behaving under one assumption, there exists another net which behaves under the other and gives the same results, although perhaps not in the same time. Various applications of the calculus are discussed. Reprinted from theBulletin of Mathematical Biophysics, Vol. 5, pp. 115–133 (1943).     

Demonstration of a universal surface DNA computer

A fundamental concept in computer science is that of the universal Turing machine, which is an abstract definition of a general purpose computer. A general purpose (universal) computer is defined as one which can compute anything that is computable. It has been shown that any computer which is able to simulate Boolean logic circuits of any complexity is such a general purpose computer. The field of DNA computing was founded in 1994 by Adleman's solution of a 7-bit instance of the Hamiltonian path problem. This work, as well as most of the subsequent experimental and theoretical investigations in the area, focused primarily upon the solution of NP-complete problems, which are a subset of the larger universal class of problems. In the present work a surface DNA computer capable of simulating Boolean logic circuits is demonstrated. This was done by constructing NOR and OR gates and combining them into a simple logic circuit. The NOR gate is one of the universal gates in Boolean logic, meaning that any other logic gate can be built from it alone. The circuit was solved using DNA-based operations, demonstrating the universal nature of this surface DNA computing model.     

A dynamical systems view of neuroethology: Uncovering stateful computation in natural behaviors

State-dependent computation is key to cognition in both biological and artificial systems. Alan Turing recognized the power of stateful computation when he created the Turing machine with theoretically infinite computational capacity in 1936. Independently, by 1950, ethologists such as Tinbergen and Lorenz also began to implicitly embed rudimentary forms of state-dependent computation to create qualitative models of internal drives and naturally occurring animal behaviors. Here, we reformulate core ethological concepts in explicitly dynamical systems terms for stateful computation. We examine, based on a wealth of recent neural data collected during complex innate behaviors across species, the neural dynamics that determine the temporal structure of internal states. We will also discuss the degree to which the brain can be hierarchically partitioned into nested dynamical systems and the need for a multi-dimensional state-space model of the neuromodulatory system that underlies motivational and affective states.     

Noisy neural nets exhibiting memory domains

Previous studies with probabilistic neural nets in which the neural connections are set up by means of chemical markers, revealed the existence of multiple memory domains. We generalized these studies by considering the intrinsic noise of the systems, caused by the spontaneous release of synaptic transmitter substance. A simple mathematical model is developed, which yields characteristics of multiple memory domains analogous to those occurring in noiseless nets.     

Computation emerges from adaptive synchronization of networking neurons

The activity of networking neurons is largely characterized by the alternation of synchronous and asynchronous spiking sequences. One of the most relevant challenges that scientists are facing today is, then, relating that evidence with the fundamental mechanisms through which the brain computes and processes information, as well as with the arousal (or progress) of a number of neurological illnesses. In other words, the problem is how to associate an organized dynamics of interacting neural assemblies to a computational task. Here we show that computation can be seen as a feature emerging from the collective dynamics of an ensemble of networking neurons, which interact by means of adaptive dynamical connections. Namely, by associating logical states to synchronous neuron's dynamics, we show how the usual Boolean logics can be fully recovered, and a universal Turing machine can be constructed. Furthermore, we show that, besides the static binary gates, a wider class of logical operations can be efficiently constructed as the fundamental computational elements interact within an adaptive network, each operation being represented by a specific motif. Our approach qualitatively differs from the past attempts to encode information and compute with complex systems, where computation was instead the consequence of the application of control loops enforcing a desired state into the specific system's dynamics. Being the result of an emergent process, the computation mechanism here described is not limited to a binary Boolean logic, but it can involve a much larger number of states. As such, our results can enlighten new concepts for the understanding of the real computing processes taking place in the brain.     

Probabilistic computation by neuromine networks

In this paper, we address the question, can biologically feasible neural nets compute more than can be computed by deterministic polynomial time algorithms? Since we want to maintain a claim of plausibility and reasonableness we restrict ourselves to algorithmically easy to construct nets and we rule out infinite precision in parameters and in any analog parts of the computation. Our approach is to consider the recent advances in randomized algorithms and see if such randomized computations can be described by neural nets. We start with a pair of neurons and show that by connecting them with reciprocal inhibition and some tonic input, then the steady-state will be one neuron ON and one neuron OFF, but which neuron will be ON and which neuron will be OFF will be chosen at random (perhaps, it would be better to say that microscopic noise in the analog computation will be turned into a megascale random bit). We then show that we can build a small network that uses this random bit process to generate repeatedly random bits. This random bit generator can then be connected with a neural net representing the deterministic part of randomized algorithm. We, therefore, demonstrate that these neural nets can carry out probabilistic computation and thus be less limited than classical neural nets.     

A dynamical systems perspective on the relationship between symbolic and non-symbolic computation

It has been claimed that connectionist (artificial neural network) models of language processing, which do not appear to employ “rules”, are doing something different in kind from classical symbol processing models, which treat “rules” as atoms (e.g., McClelland and Patterson in Trends Cogn Sci 6(11):465–472, 2002). This claim is hard to assess in the absence of careful, formal comparisons between the two approaches. This paper formally investigates the symbol-processing properties of simple dynamical systems called affine dynamical automata, which are close relatives of several recurrent connectionist models of language processing (e.g., Elman in Cogn Sci 14:179–211, 1990). In line with related work (Moore in Theor Comput Sci 201:99–136, 1998; Siegelmann in Neural networks and analog computation: beyond the Turing limit. Birkhäuser, Boston, 1999), the analysis shows that affine dynamical automata exhibit a range of symbol processing behaviors, some of which can be mirrored by various Turing machine devices, and others of which cannot be. On the assumption that the Turing machine framework is a good way to formalize the “computation” part of our understanding of classical symbol processing, this finding supports the view that there is a fundamental “incompatibility” between connectionist and classical models (see Fodor and Pylyshyn 1988; Smolensky in Behav Brain Sci 11(1):1–74, 1988; beim Graben in Mind Matter 2(2):29--51,2004b). Given the empirical successes of connectionist models, the more general, super-Turing framework is a preferable vantage point from which to consider cognitive phenomena. This vantage may give us insight into ill-formed as well as well-formed language behavior and shed light on important structural properties of learning processes.     

A neural net model for multiple memory domains

Previous studies with neural nets constructed of discrete populations of formal neurons have assumed that all neurons have the same probability of connection with any other neuron in the net. However, in this new study we incorporate the behavior of the neural systems in which the neural connections can be set up by means of chemical markers carried by the individual cells. With this new approach we studied the dynamics of isolated neural nets again as well as the dynamics of neural nets with sustained inputs. Results obtained with this approach show simple and multiple hysteresis phenomena. Such hysteresis loops may be considered to represent the basis for short-term memory.     

Parallel versus sequential processing of relational stimulus structures

Organisms are often faced with sets of stimuli bearing specifiable relationships to each other. Experimental data suggest that even animals not suspected of being particularly rational can solve problems involving consistent linear relationships. We examine the information processing required to cope with these and related stimulus structures from a theoretical point of view. We show that both a parallel processing neural network model and a serially processing Turing machine model require minimal complexities to process linear hierarchical structures. When dealing with other relational stimulus structures, the models need differing, greater minimal complexities. Siemann and Delius (1994) report experimental results indicating that both pigeons and humans appear to operate according to the parallel, neural network model we propose here. Further experiments likely to be diagnostic are proposed.     

Cybernetic models of pattern sensitive units in the visual system

Summary Pattern-specific response in the visual system is represented in terms of a mathematical model and as the response of corresponding sequential circuits. The mathematical model employs standard relations of propositional calculus, with extension to the time domain. It is shown that pattern sensitive units of many types can be generated by successive applications of a generalised contrast operator together with a spatial summation operator. The implications of the models are interpreted in neural terms.     

Artificial neural networks and their use in quantitative pathology

A brief general introduction to artificial neural networks is presented, examining in detail the structure and operation of a prototype net developed for the solution of a simple pattern recognition problem in quantitative pathology. The process by which a neural network learns through example and gradually embodies its knowledge as a distributed representation is discussed, using this example. The application of neurocomputer technology to problems in quantitative pathology is explored, using real-world and illustrative examples. Included are examples of the use of artificial neural networks for pattern recognition, database analysis and machine vision. In the context of these examples, characteristics of neural nets, such as their ability to tolerate ambiguous, noisy and spurious data and spontaneously generalize from known examples to handle unfamiliar cases, are examined. Finally, the strengths and deficiencies of a connectionist approach are compared to those of traditional symbolic expert system methodology. It is concluded that artificial neural networks, used in conjunction with other nonalgorithmic artificial intelligence techniques and traditional algorithmic processing, may provide useful software engineering tools for the development of systems in quantitative pathology.     

Polarity and form regulation in development and reconstitution

In the literature, it is often assumed, for example with respect to Hydra, that several Turing systems coexist and it is also assumed that maintaining the polar profile, even when the system increases in size, is important for the polarity of the final phenotype. It is shown here that in reality there is only one Turing system, Child's system. To obtain a complete polar individual or organ, whether in reconstitution or development, it is essential that the complete succession of metabolic patterns occurs. Child's concepts of physiological dominance, subordination and isolation are interpreted in the light of Turing theory and in particular the Turing wavelength. It is emphasised, particularly by pointing to Child's metabolic patterns in coelenterates, both in development and in reconstitution, that it is the elongation that drives the succession polar metabolic pattern-->bipolar metabolic pattern, and this corresponds to the prediction of Turing theory supporting the thesis that Child's metabolic pattern is a Turing pattern. It is shown that if we assume that ATP is the Turing inhibitor then the many results of Child about the reduction of the scale of organisation with the decrease in the intensity of the energy metabolism correspond to the reduction of the Turing wavelength. The interplay between the Turing wavelength and the length of the form explains the conditions of reconstitution under which partial forms, wholes and form regulation are obtained. It is suggested that higher metabolism is responsible for both larger size and larger Turing wavelength thus securing form regulation. The results could be of importance in modern 'regenerative biology'. Heteromorphosis, i.e. animals with two heads (or two tails), one at each end, is explained by a bipolar Turing-Child metabolic pattern replacing a polar metabolic pattern. This can be brought about by chemical or by genetic means and indeed the prediction for Drosophila that the transition, wild type-->Bicaudal D, occurs because a polar Turing pattern is replaced by bipolar Turing pattern is confirmed, again if we accept that Child's metabolic pattern is the underlying Turing pattern. Child's experiments on Drosophila, including the requirement of critical length for metabolic polarity, are explained by Turing theory. Phenocopies and phenotypes are explained by the Turing-Child theory. It is shown that both Child's results about metabolic patterns and modern results for Hydra about gap junctions, 'endogeneous inhibitor' and gene expression, are correlated and explained by (cAMP, ATP) Turing theory. It is argued that the double-gradient hypothesis is incorrect in its original formulation and that it is Child's conception of succeeding metabolic patterns that is the correct one and that it corresponds to the prediction of the Turing theory.     

On problem solving with Hopfield neural networks

Hopfield and Tank have shown that neural networks can be used to solve certain computationally hard problems, in particular they studied the Traveling Salesman Problem (TSP). Based on network simulation results they conclude that analog VLSI neural nets can be promising in solving these problems. Recently, Wilson and Pawley presented the results of their simulations which contradict the original results and cast doubts on the usefulness of neural nets. In this paper we give the results of our simulations that clarify some of the discrepancies. We also investigate the scaling of TSP solutions found by neural nets as the size of the problem increases. Further, we consider the neural net solution of the Clustering Problem, also a computationally hard problem, and discuss the types of problems that appear to be well suited for a neural net approach.     

Computational functions in biochemical reaction networks.

In prior work we demonstrated the implementation of logic gates, sequential computers (universal Turing machines), and parallel computers by means of the kinetics of chemical reaction mechanisms. In the present article we develop this subject further by first investigating the computational properties of several enzymatic (single and multiple) reaction mechanisms: we show their steady states are analogous to either Boolean or fuzzy logic gates. Nearly perfect digital function is obtained only in the regime in which the enzymes are saturated with their substrates. With these enzymatic gates, we construct combinational chemical networks that execute a given truth-table. The dynamic range of a network's output is strongly affected by "input/output matching" conditions among the internal gate elements. We find a simple mechanism, similar to the interconversion of fructose-6-phosphate between its two bisphosphate forms (fructose-1,6-bisphosphate and fructose-2,6-bisphosphate), that functions analogously to an AND gate. When the simple model is supplanted with one in which the enzyme rate laws are derived from experimental data, the steady state of the mechanism functions as an asymmetric fuzzy aggregation operator with properties akin to a fuzzy AND gate. The qualitative behavior of the mechanism does not change when situated within a large model of glycolysis/gluconeogenesis and the TCA cycle. The mechanism, in this case, switches the pathway's mode from glycolysis to gluconeogenesis in response to chemical signals of low blood glucose (cAMP) and abundant fuel for the TCA cycle (acetyl coenzyme A).     

Cooperative combinatorial optimization: evolutionary computation case study

This paper presents a formalization of the notion of cooperation and competition of multiple systems that work toward a common optimization goal of the population using evolutionary computation techniques. It is proved that evolutionary algorithms are more expressive than conventional recursive algorithms, such as Turing machines. Three classes of evolutionary computations are introduced and studied: bounded finite, unbounded finite, and infinite computations. Universal evolutionary algorithms are constructed. Such properties of evolutionary algorithms as completeness, optimality, and search decidability are examined. A natural extension of evolutionary Turing machine (ETM) model is proposed to properly reflect phenomena of cooperation and competition in the whole population.     

Induction and the Turing-Child field in development

The central problem in biological development is the understanding of epigenesis. The dominant theory of development in the last 80 years that also purports to explain epigenesis is induction theory. It suggests that development is driven by sequential inductions where each "induction" (in one sense of the word induction) is effected by the action of an inducing part of the embryo on a responding part of the embryo. The theory stems from Spemann and Mangold (W.Roux' Arch.f.Entw.d.Organis.u.mikrosk.Anat.100 (1924) 599) who transplanted a tissue from the dorsal blastopore lip of Triturus into the ventral ectoderm of another gastrula and thus initiated and "induced" (in another sense of the word induction) gastrulation and embryogenesis in the ventral side of the host that became a double embryo (siamese twins). We explain this induction, i.e. the formation of the double embryo, according to the Child theory and the Turing-Gierer-Meinhardt theory when it is also assumed that cAMP and ATP are the Turing activator and inhibitor, respectively. Spemann and Mangold (W.Roux' Arch.f.Entw.d.Organis.u.mikrosk.Anat.100 (1924) 599) also suggested that the ingressing mesoderm induces the overlying ectoderm to form the neural plate and neural tube. This 'neural induction', the 'primary embryonic induction', became the cornerstone of induction theory, i.e. of the sequential induction concept referred to above. But we argue that the metabolic gradients that precede and accompany neurulation, as obtained by Child, also for Triturus, arise through a Turing self-organization if it is assumed that cAMP and ATP are the Turing morphogens, and these gradients are the cause and primary event of neurulation. Thus there is no need to invoke the 'neural induction'. It is argued that fundamental events such as gastrulation and also organ formation are caused by the Turing-Child field and not by sequential induction. Similar principles, such as bud formation caused by a radial metabolic pattern that transforms to a longitudinal pattern, govern the formation, for example, of the mouth and the gut. The formation and localization of bottle cells is explained according to the Child-Turing field and modern biochemistry. The chemical metabolic pre-pattern precedes, and causes, morphogenesis and differentiation as envisaged by Turing. The Spemann and Mangold (W.Roux' Arch.f.Entw.d.Organis.u.mikrosk.Anat.100 (1924) 599) transplantation experiment when performed on a sea urchin duplicates not only the phenotype but also the metabolic (reduction) pattern. These experimental results, by Horstadius, predicted by Child, follow from the Turing-Gierer-Meinhardt theory if it is assumed that cAMP and ATP are the Turing morphogens. If the transplantation is performed not onto the whole sea urchin but onto only a part of it, that manifests only a part of the metabolic pattern, then from the part a phenotypic whole underlain by a normal and a whole metabolic pattern can be rescued. These experimental results of Horstadius follow from Turing theory if cAMP and ATP are the Turing morphogens. Understanding how to transform a part into a whole can be valuable in regenerative medicine. Unspecific induction of a secondary amphibian embryo is similar to the induction of posterior structures at the anterior pole of an insect, and the "double abdomen" (and Kalthoff's experimental results) of the midge Smittia resulting from UV irradiation of the anterior pole, can be explained by Meinhardt theory of unspecific induction if ATP is the Turing morphogen. When not working on regeneration, Child investigated intact living organisms and his observation method was not disruptive to normal development, whereas workers in induction theory work with pieces and in general disrupt normal development. We conclude that the Turing-Child field causes all development and explains epigenesis. Sequential induction does not explain epigenesis and does not exist in normal development. But induction in the sense of a transplantation leading to double embryo or rescuing a whole phenotype from a part is of interest.     

Toward a theory of evolutionary computation

We outline a theory of evolutionary computation using a formal model of evolutionary computation--the Evolutionary Turing Machine--which is introduced as the extension of the Turing Machine model. Evolutionary Turing Machines provide a better and a more complete model for evolutionary computing than conventional Turing Machines, algorithms, and Markov chains. The convergence and convergence rate are defined and investigated in terms of this new model. The sufficient conditions needed for the completeness and optimality of evolutionary search are investigated. In particular, the notion of the total optimality as an instance of the multiobjective optimization of the Universal Evolutionary Turing Machine is introduced. This provides an automatic way to deal with the intractability of evolutionary search by optimizing the quality of solutions and search costs simultaneously. Based on a new model a very flexible classification of optimization problem hardness for the evolutionary techniques is proposed. The expressiveness of evolutionary computation is investigated. We show that the problem of the best evolutionary algorithm is undecidable independently of whether the fitness function is time dependent or fixed. It is demonstrated that the evolutionary computation paradigm is more expressive than Turing Machines, and thus the conventional computer science based on them. We show that an Evolutionary Turing Machine is able to solve nonalgorithmically the halting problem of the Universal Turing Machine and, asymptotically, the best evolutionary algorithm problem. In other words, the best evolutionary algorithm does not exist, but it can be potentially indefinitely approximated using evolutionary techniques.