Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
2,667
result(s) for
"Turing machines"
Sort by:
Majority Logic Gate for Magnetic Quantum-Dot Cellular Automata
We describe the operation of, and demonstrate logic functionality in, networks of physically coupled, nanometer-scale magnets designed for digital computation in magnetic quantum-dot cellular automata (MQCA) systems. MQCA offer low power dissipation and high integration density of functional elements and operate at room temperature. The basic MQCA logic gate, that is, the three-input majority logic gate, is demonstrated.
Journal Article
Free Agency and Determinism: Is There a Sensible Definition of Computational Sourcehood?
Can free agency be compatible with determinism? Compatibilists argue that the answer is yes, and it has been suggested that the computer science principle of “computational irreducibility” sheds light on this compatibility. It implies that there cannot, in general, be shortcuts to predict the behavior of agents, explaining why deterministic agents often appear to act freely. In this paper, we introduce a variant of computational irreducibility that intends to capture more accurately aspects of actual (as opposed to apparent) free agency, including computational sourcehood, i.e., the phenomenon that the successful prediction of a process’ behavior must typically involve an almost-exact representation of the relevant features of that process, regardless of the time it takes to arrive at the prediction. We argue that this can be understood as saying that the process itself is the source of its actions, and we conjecture that many computational processes have this property. The main contribution of this paper is technical, in that we analyze whether and how a sensible formal definition of computational sourcehood is possible. While we do not answer the question completely, we show how it is related to finding a particular simulation preorder on Turing machines, we uncover concrete stumbling blocks towards constructing such a definition, and demonstrate that structure-preserving (as opposed to merely simple or efficient) functions between levels of simulation play a crucial role.
Journal Article
A Symmetry-Based Computational Framework for Motor Skill Optimization: Integrating Screw Theory and Ecological Perception
This study introduces a computational framework for understanding the symmetry and asymmetry of human movement by integrating Laban Movement Analysis (LMA). By conceptualizing movement refinement as a structured computational process, we model the golf swing as a series of state transitions where perceptual invariants guide biomechanical optimization. The golf club’s motion is analyzed using the instantaneous screw axis (ISA) and inertia tensor revealing how expert golfers dynamically adjust movement by detecting and responding to invariant biomechanical structures. This approach extends Gibson’s ecological theory by proposing that movement execution follows an iterative optimization process analogous to a Turing machine updating its states. Furthermore, we explore the role of symmetry in motor control by aligning Laban’s X-scale with structured computational transitions, demonstrating how movement coordination emerges from dynamically balanced affordance–action couplings. This insight gained from the study suggests that AI-driven sports training and rehabilitation can leverage symmetry-based computational principles to enhance motion learning and real-time adaptation in virtual and physical environments.
Journal Article
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP
For a size parameter s:ℕ→ℕ, the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}n →{0,1} (represented by a string of length N := 2n) is at most a threshold s(n). A recent line of work exhibited “hardness magnification” phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant μ1 > 0, if MCSP[2μ1⋅n] cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time N1.01, then P≠NP. In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs: (1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute MCSP[2μ2⋅n] in time N1.99, for some constant μ2 > μ1. (2) A non-deterministic (or parity) branching program of size o(N1.5/logN) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. (3) The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least N1.5−o1. These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola, Electron. Colloq. Comput. Complexity (ECCC) 26, 51, 2019). En route, we obtain several related results: (1) There exists a (local) hitting set generator with seed length O~(N) secure against read-once polynomial-size non-deterministic branching programs on N-bit inputs. (2) Any read-once co-non-deterministic branching program computing MCSP must have size at least 2Ω~(N).
Journal Article
On Turing Machines Deciding According to the Shortest Computations
In this paper we propose and analyse from the computational complexity point of view several new variants of nondeterministic Turing machines. In the first such variant, a machine accepts a given input word if and only if one of its shortest possible computations on that word is accepting; on the other hand, the machine rejects the input word when all the shortest computations performed by the machine on that word are rejecting. We are able to show that the class of languages decided in polynomial time by such machines is PNP[log]. When we consider machines that decide a word according to the decision taken by the lexicographically first shortest computation, we obtain a new characterization of PNP. A series of other ways of deciding a language with respect to the shortest computations of a Turing machine are also discussed.
Journal Article
SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality constraints (linear and nonlinear). We assume that first derivatives are available and that the constraint gradients are sparse. Second derivatives are assumed to be unavailable or too expensive to calculate. We discuss an SQP algorithm that uses a smooth augmented Lagrangian merit function and makes explicit provision for infeasibility in the original problem and the QP subproblems. The Hessian of the Lagrangian is approximated using a limited-memory quasi-Newton method. SNOPT is a particular implementation that uses a reduced-Hessian semidefinite QP solver (SQOPT) for the QP subproblems. It is designed for problems with many thousands of constraints and variables but is best suited for problems with a moderate number of degrees of freedom (say, up to 2000). Numerical results are given for most of the CUTEr and COPS test collections (about 1020 examples of all sizes up to 40000 constraints and variables, and up to 20000 degrees of freedom).
Journal Article
Symmetric Instruction Machines and Symmetric Turing Machines
Symmetric instruction machines (SIAs) and symmetric Turing machines (STMs) are models of computation involving concepts derived from those of classical Turing machines such as tape (memory) and head (processor), but with different functional and structural characteristics. The former model (SIAs) introduced in this paper and preferred by Mark Burgin is a result of a reformulation of the latter model (STMs) published in several articles by the second author in the past. The properties of both models are analyzed and compared. The word “symmetric” in both cases represents the feature of the design which is distinct from classical Turing machines where only cells on the tape change under the action of the head. In both models, symmetric computing involves changes of the tape and parallel (“symmetric”) changes of instructions listed in the head. The key difference between SIAs and STMs is in the dynamic of the changes, which in the former model has the form of compound one-way actions and in the latter model, it has the form of uniform mutual interactions, which only in specific realizations can be separated into a pair of actions. Because of the untimely passing of Mark Burgin, the discussion of the two models and cooperation on the paper has never been finished. For this reason, the arguments of both authors are reported even though, in some cases, they are mutually inconsistent or even contradictory.
Journal Article
Is Every Cognitive Phenomenon Computable?
According to the Church–Turing thesis, the limit of what is computable is bounded by Turing machines. Following from this, given that general computable functions formally describe the notion of recursive mechanisms, it is sometimes argued that every organismic process that specifies consistent cognitive responses should be both limited to Turing machine capabilities and amenable to formalization. There is, however, a deep intuitive conviction permeating contemporary cognitive science, according to which mental phenomena, such as consciousness and agency, cannot be explained by resorting to this kind of framework. In spite of some exceptions, the overall tacit assumption is that whatever the mind is, it exceeds the reach of what is described by notions of computability. This issue, namely the nature of the relation between cognition and computation, becomes particularly pertinent and increasingly more relevant as a possible source of better understanding the inner workings of the mind, as well as the limits of artificial implementations thereof. Moreover, although it is often overlooked or omitted so as to simplify our models, it will probably define, or so we argue, the direction of future research on artificial life, cognitive science, artificial intelligence, and related fields.
Journal Article