Modified dynamical systems retain Turing universality.
problem Embedding Turing machines into dynamical systems.
method Exploring flows with adapted 1-forms and homogeneity.
result Even slight modifications can lead to Turing universality.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Turing universality”
The Navier-Stokes equations on certain manifolds can perform universal computation.
problem Computational universality in viscous fluids.
method Cosymplectic geometry and harmonic 1-forms.
result Stationary Navier-Stokes solutions exhibit Turing completeness.
New neural stack and Turing Machine architectures prove stability and computational power.
problem Designing stable neural network architectures for Turing Machine simulation.
method Introducing neural stack and Turing Machine architectures, proving stability and computational equivalence.
result Differentiable nnTM with bounded neurons can simulate Turing Machine in real-time and is equivalent to UTM.
Survey on computational models in dynamical systems, including new universality concepts.
problem Understanding the relationship between computational models and dynamical systems.
method Review of recent works on Turing universality, Topological Kleene Field Theories, and dynamical bordisms.
result Introduction of new perspectives on computability through dynamical systems.
Turing complete flow on 4-sphere preserves volume.
problem Creating a Turing complete flow on a 4-sphere.
method Smooth, conservative flow on the 4-sphere.
result Achieved a Turing complete, volume-preserving flow.
Reservoir Memory Machines solve benchmark tasks faster than Neural Turing Machines.
problem Training Neural Turing Machines is hard and limits their applicability.
method Proposes Reservoir Memory Machines, combining neural network flexibility with Turing machine capabilities, but with faster training via alignment and linear regression.
result Reservoir Memory Machines solve benchmark tasks as well as Neural Turing Machines but are much faster to train.
Every homomorphism from finite index subgroups of a universal lattices to mapping class groups of orientable surfaces (possibly with punctures), or to outer automorphism groups of finitely generated nonabelian free groups must have finite image. Here the universal lattice denotes the special linear group G=SL_m(Z[x1,..…
This study calculates the maximum error of a famous estimation method.
problem Estimating rare items not seen in a sample.
method Characterizes the maximal mean-squared error of the Good-Turing estimator.
result Characterizes the maximal mean-squared error of the Good-Turing estimator.
A universal learner achieves best rates for all distributions.
problem Improving learning algorithm rates under various settings.
method Simple extension of Levin's universal search.
result Achieves best-possible rates for all distributions.
Researchers prove Transformers are Turing-complete and analyze their components.
problem Understanding the computational power and limitations of Transformers.
method Analyzed Turing-completeness of vanilla and modified Transformers, and necessity of components.
result Transformers with positional masking and positional encodings are Turing-complete.
We propose Turing Learning, a novel system identification method for inferring the behavior of natural or artificial systems. Turing Learning simultaneously optimizes two populations of computer programs, one representing models of the behavior of the system under investigation, and the other representing classifiers. …
We present chemlambda (or the chemical concrete machine), an artificial chemistry with the following properties: (a) is Turing complete, (b) has a model of decentralized, distributed computing associated to it, (c) works at the level of individual (artificial) molecules, subject of reversible, but otherwise determinist…
This study explains how adversarial interaction creates non-homogeneous patterns using a pseudo-Reaction-Diffusion model.
problem Understanding how adversarial interaction leads to non-homogeneous patterns in systems.
method Developed a pseudo-Reaction-Diffusion model to explain the mechanism.
result Turing instability is involved in creating non-homogeneous patterns.
This study shows neural nets can approximate Turing machines with meaningful statistical properties.
problem Theoretical limitations in approximating Turing machines with neural networks.
method Formal definition of statistically meaningful approximation, analysis of boolean circuits and Turing machines using neural nets.
result Transformers can statistically meaningfully approximate Turing machines with polynomial sample complexity.
A note on lattice knotsmath.GT
One type of switch simplifies operations on lattice knots.
problem Operations on lattice knots are complex.
method Reduced operations to one type of local switch.
result Simplified set of operations on lattice knots.
The aim of this work is to address the question of whether we can in principle design rational decision-making agents or artificial intelligences embedded in computable physics such that their decisions are optimal in reasonable mathematical senses. Recent developments in rare event probability estimation, recursive ba…
The problem of replicating the flexibility of human common-sense reasoning has captured the imagination of computer scientists since the early days of Alan Turing's foundational work on computation and the philosophy of artificial intelligence. In the intervening years, the idea of cognition as computation has emerged …
Neural networks powered with external memory simulate computer behaviors. These models, which use the memory to store data for a neural controller, can learn algorithms and other complex tasks. In this paper, we introduce a new memory to store weights for the controller, analogous to the stored-program memory in modern…
Estimates stationary mass and frequency from non-i.i.d. data.
problem Estimating stationary mass and frequency from non-i.i.d. data.
method Combines plug-in estimator with WingIt modification for exponentially -mixing processes.
result Universal consistency in for total variation distance estimation.
New framework for manifold convolutions using toric embeddings.
problem Computational intractability of manifold convolutions.
method Isometric embeddings into tori for global manifold convolutions.
result Global definition of manifold convolutions on finite approximations.
Alternatives to recurrent neural networks, in particular, architectures based on attention or convolutions, have been gaining momentum for processing input sequences. In spite of their relevance, the computational properties of these alternatives have not yet been fully explored. We study the computational power of two…
sktime is an open source, Python based, sklearn compatible toolkit for time series analysis developed by researchers at the University of East Anglia (UEA), University College London and the Alan Turing Institute. A key initial goal for sktime was to provide time series classification functionality equivalent to that a…
No universal trading strategy exists due to mathematical impossibilities.
problem The impossibility of universally winning trading strategies in competitive markets.
method Three mathematical paradigms: measure-theoretic, No-Free-Lunch theorem, and adversarial Cantor diagonalization.
result No-arbitrage and free-lunch principles are mathematically precluded in competitive markets.
A new restart criterion for k-means++ improves clustering quality and adapts to data difficulty.
problem Arbitrary restart counts in k-means++ lead to inconsistent results and wasted computation.
method GTRC combines Good-Turing estimates, bounds, and user-specified tolerance to dynamically decide restarts.
result GTRC achieves clustering quality comparable to fixed restart counts, varying restarts based on data difficulty.
This work investigates how multi-round reasoning improves LLM performance.
problem Improving problem-solving abilities in complex tasks with LLMs.
method Investigates approximation, learnability, and generalization properties of multi-round auto-regressive models.
result Transformers with finite context windows are universal approximators for Turing-computable functions and can approximate any Turing-computable sequence-to-sequence function through multi-round reasoning.
This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNNm…
Abstract sketches historical development of Lie brackets, crossed modules, and Lie-Rinehart algebras.
problem Characterizing and understanding the relationships between Lie brackets, crossed modules, and Lie-Rinehart algebras.
method Historical review and combinatorial group theory considerations.
result The mutual relationship between Lie-Rinehart algebras and Lie brackets, and the historical development of these concepts.
In this paper, we study quatization condition of logsymplectic struc- ture using integrality of such structue on the complement of associated divisor D.
In this article, we introduce a new mode for training Generative Adversarial Networks (GANs). Rather than minimizing the distance of evidence distribution and the generative distribution , we minimize the distance of and . This adversarial pattern can be…
There are (at least) three approaches to quantifying information. The first, algorithmic information or Kolmogorov complexity, takes events as strings and, given a universal Turing machine, quantifies the information content of a string as the length of the shortest program producing it. The second, Shannon information…
A framework to quantify deployment risk in ML systems, especially for rare states.
problem Under-supported rare states in ML models lead to unreliable performance in unseen data.
method Blind-Spot Mass (B_n(tau)) using Good-Turing unseen-species estimation.
result Identifies and quantifies the risk of under-supported states in ML models.
New tools quantify deep generative models' performance.
problem Measuring the quality-diversity trade-off in deep generative models.
method Established non-asymptotic bounds on sample complexity and introduced frontier integrals.
result Smoothed estimators improve convergence rates of divergence frontiers.
Neural Turing Machines (NTMs) are an instance of Memory Augmented Neural Networks, a new class of recurrent neural networks which decouple computation from memory by introducing an external memory unit. NTMs have demonstrated superior performance over Long Short-Term Memory Cells in several sequence learning tasks. A n…
We construct a financial "Turing test" to determine whether human subjects can differentiate between actual vs. randomized financial returns. The experiment consists of an online video-game (http://arora.ccs.neu.edu) where players are challenged to distinguish actual financial market returns from random temporal permut…
Given samples from a population of individuals belonging to different types with unknown proportions, how do we estimate the probability of discovering a new type at the -th draw? This is a classical problem in statistics, commonly referred to as the missing mass estimation problem. Recent results by Ohannes…
Estimating a large alphabet probability distribution from a limited number of samples is a fundamental problem in machine learning and statistics. A variety of estimation schemes have been proposed over the years, mostly inspired by the early work of Laplace and the seminal contribution of Good and Turing. One of the b…
Study computability of real numbers from group properties.
problem Computability of real numbers from group properties.
method Analyzing -Betti numbers and -torsion of groups.
result Real numbers as -Betti numbers or -torsion are computable.
The goal of this paper, using lifting theory it is to produce almost paracomplex struc- tures on the tangent bundle of almost Lorentzian r-paracontact manifold endowed with almost Lorentzian r-paracontact structure. Finally, we discuss the effect over dynamics systems of the produced geometrical structures.
BigBird improves transformer performance on NLP tasks with longer sequences.
problem Quadratic dependency on sequence length in transformer models.
method Sparse attention mechanism reducing quadratic dependency to linear.
result Significant improvement in performance on NLP tasks like QA and summarization.
Estimates missing mass in Markovian sequences with linear runtime and near-optimal risk.
problem Estimating missing mass in Markovian sequences.
method Windowed Good-Turing (WingIt) estimator.
result Risk decays as , independent of state space size.
Popular culture has contemplated societies of thinking machines for generations, envisioning futures from utopian to dystopian. These futures are, arguably, here now-we find ourselves at the doorstep of technology that can at least simulate the appearance of thinking, acting, and feeling. The real question is: now what…
Under appropriate assumptions, we generalize the concept of linear almost Poisson struc- tures, almost Lie algebroids, almost differentials in the framework of Banach anchored bundles and the relation between these objects. We then obtain an adapted formalism for mechanical systems which is illustrated by the evolution…
Recurrent neural networks (RNNs) sequentially process data by updating their state with each new data point, and have long been the de facto choice for sequence modeling tasks. However, their inherently sequential computation makes them slow to train. Feed-forward and convolutional architectures have recently been show…
Private KL distribution estimation improved with instance-optimality.
problem Minimizing KL divergence between true and estimated distributions.
method Construct minimax optimal private estimators, then focus on instance-optimality.
result Achieved instance-optimality up to constant factors for KL estimation.
We begin with a review of the notion of a braid group. We then discuss some known solutions to decision problems in braid groups. We then move on to proving new results in braid group algorithmics. We offer a quick solution to the generalized word problem in braid groups, in the special case of cyclic subgroups. We ill…
On sphere-filling ropesmath.GT
What is the longest rope on the unit sphere? Intuition tells us that the answer to this packing problem depends on the rope's thickness. For a countably infinite number of prescribed thickness values we construct and classify all solution curves. The simplest ones are similar to the seamlines of a tennis ball, others e…
DynamicPPL speeds up probabilistic modeling in Julia.
problem Developing and executing complex dynamic probabilistic models efficiently.
method Modular Julia library with a DSL, tracing data structure, and contextual dispatch.
result Achieves computational performance close to or better than Stan.
GT estimator shows convergence for Markov samples, improving i.i.d. results.
problem Estimating missing mass in Markov samples.
method Analyzed convergence of Good-Turing estimator for Markov samples, considering spectral properties of transition matrices.
result The convergence of the GT estimator for Markov samples depends on the spectral properties of the transition matrices, leading to a new minimax rate of for rank-2 Markov chains.