Computational versus Causal Complexity

The main claim of this paper is that notions of implementation based on an isomorphic correspondence between physical and computational states are not tenable. Rather, ``implementation' has to be based on the notion of ``bisimulation' in order to be able to block unwanted implementation results and incorporate intuitions from computational practice. A formal definition of implementation is suggested, which satisfies theoretical and practical requirements and may also be used to make the functionalist notion of ``physical realization' precise. The upshot of this new definition of implementation is that implementation cannot distinguish isomorphic bisimilar from non-isomporphic bisimilar systems anymore, thus driving a wedge between the notions of causal and computational complexity. While computationalism does not seem to be affected by this result, the consequences for functionalism are not clear and need further investigations.     

A cellular framework for structural analysis and optimization

The present paper describes the implementation of a cellular automata based computational approach in structural analysis and design. This approach assumes that a computational domain can be subdivided into a number of discrete cells, with state variables associated with each cell. Collectively, these cell states define the state of the entire domain, and which may be evolved through application of local rules of interaction that apply to a defined neighborhood around each cell. The computational process is intrinsically parallel in nature, and allows for a natural implementation on parallel computers. The paper describes an overview of this computational model for the analysis of structural systems, and demonstrates how it can be extended for a fine-grained parallel implementation of the genetic algorithm based optimization strategy. The paper also illustrates an extension of the proposed model in solving problems of simultaneous analysis and optimization.     

Fault tolerant machine learning for nanoscale cognitive radio

We introduce a machine learning-based classifier that identifies free radio channels for cognitive radio. The architecture is designed for nanoscale implementation, under nanoscale implementation constraints; we do not describe all physical details but believe future physical implementation to be feasible. The system uses analog computation and consists of cyclostationary feature extraction and a radial basis function network for classification. We describe a model for nanoscale faults in the system, and simulate experimental performance and fault tolerance in recognizing WLAN signals, under different levels of noise and computational errors. The system performs well under expected non-ideal manufacturing and operating conditions.     

PARALLEL PROCESSING FOR CHROMOSOME RECONSTRUCTION FROM PHYSICAL MAPS - A CASE STUDY OF MIMD PARALLELISM ON THE HYPERCUBE

Ordering clones from a genomic library into physical maps of whole chromosomes presents a pivotal computational problem in genetics. Previous research has shown the physical mapping problem to be isomorphic to the NP-complete Optimal Linear Arrangement (OLA) problem for which no polynomial-time algorithm for determining the optimal solution is known. Serial implementations of stochastic global optimization techniques such as simulated annealing yielded very good results but proved computationally intensive. The design, analysis and implementation of coarse-grained parallel MIMD algorithms for simulated annealing on the Intel iPSC/860 hypercube is presented. Data decomposition and control decomposition strategies based on Markov chain decomposition, perturbation methods and problem-specific annealing heuristics are proposed and applied to the physical mapping problem. A suite of parallel algorithms are implemented on an 8-node Intel iPSC/860 hypercube, exploiting the nearest-neighbor communication pattern on the Boolean hypercube topology. Convergence, speedup and scalability characteristics of the various parallel algorithms are analyzed and discussed. Results indicate a deterioration of performance when a single Markov chain of solution states is distributed across multiple processing elements in the Intel iPSC/860 hypercube.     

Innovation approach to reduced-order estimation of complementary states.

A reduced-order filler algorithm is developed for estimation of the complementary states of a linear system driven by white noise. The estimator gives an unbiased estimate of the states, and the error in the estimate is orthogonal to the subspace of the observations of those states that are common to the observations and the estimated states, The filter performance is suboptimal relative to the full-order optimal linear filter, but benefits are reaped from computational savings in the filtering and associated Riccati equations. The algorithms are developed using a concept of the ‘reduced-order innovation process’. The design uses only a priori information for z, the states to be estimated. The estimator is shown to be unique. The requirements of the stability of the filter are also presented, and its determination can precede its implementation. The basic limitation of this approach is that one is constrained by the minimum order of the filter, because of the assumption in (2.11) that the states to be estimated are complementary to the observed states.     

Adaptive output feedback tracking control for a class of uncertain nonlinear systems using neural networks.

This correspondence addresses the problem of designing robust tracking control for a class of uncertain nonlinear MIMO second-order systems. An adaptive neural-network-based output feedback tracking controller is constructed such that all the states and signals involved are uniformly bounded and the tracking error is uniformly ultimately bounded. Only the output measurement is required for feedback. The implementation of the neural network basis functions depends only on the desired reference trajectory. Therefore, the intelligent adaptive output feedback controller developed here possesses the properties of computational simplicity and easy implementation. A simulation example of controlling mass-spring-damper mechanical systems is made to confirm the effectiveness and performance of the developed control scheme.     

Quantum circuits for spin and flavor degrees of freedom of quarks forming nucleons

We discuss the quantum-circuit realization of the state of a nucleon in the scope of simple simmetry groups. Explicit algorithms are presented for the preparation of the state of a neutron or a proton as resulting from the composition of their quark constituents. We estimate the computational resources required for such a simulation and design a photonic network for its implementation. Moreover, we highlight that current work on three-body interactions in lattices of interacting qubits, combined with the measurement-based paradigm for quantum information processing, may also be suitable for the implementation of these nucleonic spin states.     

Unambiguous discrimination between two unknown qudit states

We consider the unambiguous discrimination between two unknown qudit states in n-dimensional (n ???2) Hilbert space. By equivalence of unknown pure states to known mixed states and with the Jordan-basis method, we demonstrate that the optimal success probability of the discrimination between two unknown states is independent of the dimension n. We also give a scheme for a physical implementation of the programmable state discriminator that can unambiguously discriminate between two unknown states with optimal probability of success.     

A new technique for the solution of the Saha equation

A new computational technique for solving the Saha equation, which calculates the ionization states of gases, is presented. The algorithm is safe, converges quickly and is simple to implement. Pseudocode of the program is given to assist such implementation. Accuracy checks are described. Limitations of the technique at high ionization are discussed.     

Computation, Implementation, Cognition

Putnam (Representations and reality. MIT Press, Cambridge, 1988) and Searle (The rediscovery of the mind. MIT Press, Cambridge, 1992) famously argue that almost every physical system implements every finite computation. This universal implementation claim, if correct, puts at the risk of triviality certain functional and computational views of the mind. Several authors have offered theories of implementation that allegedly avoid the pitfalls of universal implementation. My aim in this paper is to suggest that these theories are still consistent with a weaker result, which is the nomological possibility of systems that simultaneously implement different complex automata. Elsewhere I (Shagrir in J Cogn Sci, 2012) argue that this simultaneous implementation result challenges a computational sufficiency thesis (articulated by Chalmers in J Cogn Sci, 2012). My focus here is on theories of implementation. After presenting the basic simultaneous implementation construction, I argue that these theories do not avoid the simultaneous implementation result. The conclusion is that the idea that the implementation of the right kind of automaton suffices for a possession of a mind is dubious.     

Confirmation and the computational paradigm (or: Why do you think they call itartificial intelligence?)

The idea that human cognitive capacities are explainable by computational models is often conjoined with the idea that, while the states postulated by such models are in fact realized by brain states, there are no type-type correlations between the states postulated by computational models and brain states (a corollary of token physicalism). I argue that these ideas are not jointly tenable. I discuss the kinds of empirical evidence available to cognitive scientists for (dis)confirming computational models of cognition and argue that none of these kinds of evidence can be relevant to a choice among competing computational models unless there are in fact type-type correlations between the states postulated by computational models and brain states. Thus, I conclude, research into the computational procedures employed in human cognition must be conducted hand-in-hand with research into the brain processes which realize those procedures.     

平行测量:复杂测量系统的一个新型理论框架及案例研究

分析了复杂测量系统的溯源研究现状,指出现有的研究已不能满足复杂测量系统的动态化溯源需求,提出了建立人工测量系统的必要性.基于ACP（Artificial societies,computational experiments,and parallel execution）方法建立了平行测量系统的理论框架,通过构建与物理测量系统行为和特性等价的人工测量系统,借助人工测量系统的计算实验,确定测量优化控制策略,引导物理测量系统的运行,并进行评估,实现物理测量系统和人工测量系统的平行执行和平行控制,将物理测量系统溯源至人工测量系统的理论模型上,解决复杂测量系统的溯源问题.并以齿轮在位测量系统为例,对平行齿轮测量系统进行了设计和平行控制研究.     

Reduced-complexity nonlinear H/sup /spl infin// control of discrete-time systems

In this note, we describe a reduced-complexity solution to the nonlinear H/sup /spl infin// control problem. This reduction applies to systems where some of the states are perfectly known, and is an intermediate problem between full state feedback and the standard measurement feedback problem. The reduction of computational complexity is significant and of practical importance. Online implementation is feasible with 2003 computer technology for a range of practical engineering design problems.     

The computational solution of optimal control problems with time lag

A gradient computational procedure is developed for discrete-time optimal control problems in which the current cost and rule governing state transitions depend on the entire past history of states and decisions. A condition necessary for optimality is also deduced in two ways and given physical interpretation.     

A differential operator technique for restoring degraded signals and images

A technique is described for restoring signals, images, and other physical quantities that have been distorted or degraded by an imperfect measurement system. This technique is based upon the application of a specific differential operator to the measured quantity. For digital implementation, its advantages compared to other restoration techniques are simplicity, computational efficiency, and reduced core memory requirements. Calculations for a one-dimensional example indicate that restorations comparable in quality to Wiener-filter restorations are obtained with better than an order of magnitude decrease in computation time.     

Significance of Models of Computation,from Turing Model to Natural Computation

The increased interactivity and connectivity of computational devices along with the spreading of computational tools and computational thinking across the fields, has changed our understanding of the nature of computing. In the course of this development computing models have been extended from the initial abstract symbol manipulating mechanisms of stand-alone, discrete sequential machines, to the models of natural computing in the physical world, generally concurrent asynchronous processes capable of modelling living systems, their informational structures and dynamics on both symbolic and sub-symbolic information processing levels. Present account of models of computation highlights several topics of importance for the development of new understanding of computing and its role: natural computation and the relationship between the model and physical implementation, interactivity as fundamental for computational modelling of concurrent information processing systems such as living organisms and their networks, and the new developments in logic needed to support this generalized framework. Computing understood as information processing is closely related to natural sciences; it helps us recognize connections between sciences, and provides a unified approach for modeling and simulating of both living and non-living systems.     

On implementing a computation

To clarify the notion of computation and its role in cognitive science, we need an account of implementation, the nexus between abstract computations and physical systems. I provide such an account, based on the idea that a physical system implements a computation if the causal structure of the system mirrors the formal structure of the computation. The account is developed for the class of combinatorial-state automata, but is sufficiently general to cover all other discrete computational formalisms. The implementation relation is non-vacuous, so that criticisms by Searle and others fail. This account of computation can be extended to justify the foundational role of computation in artificial intelligence and cognitive science.     

Evolved Computing Devices and the Implementation Problem

The evolutionary circuit design is an approach allowing engineers to realize computational devices. The evolved computational devices represent a distinctive class of devices that exhibits a specific combination of properties, not visible and studied in the scope of all computational devices up till now. Devices that belong to this class show the required behavior; however, in general, we do not understand how and why they perform the required computation. The reason is that the evolution can utilize, in addition to the “understandable composition of elementary components”, material-dependent constructions and properties of environment (such as temperature, electromagnetic field etc.) and, furthermore, unknown physical behaviors to establish the required functionality. Therefore, nothing is known about the mapping between an abstract computational model and its physical implementation. The standard notion of computation and implementation developed in computer science as well as in cognitive science has become very problematic with the existence of evolved computational devices. According to the common understanding, the evolved devices cannot be classified as computing mechanisms.