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,932 papers · 148 categories
Trend · papers per month
48 results for “Universal Turing Machine”
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.
New memory in neural networks mimics computer architectures.
problem Learning algorithms and complex tasks with neural networks.
method Introducing a new memory to store weights for a neural controller, similar to stored-program memory in computers.
result Neural Stored-program Memory enhances neural networks' adaptability and learning capabilities.
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.
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.
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.
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.
Turing test relevance questioned in age of AI.
problem Relevance of Turing test in AI age.
method Examining cultural and technological context.
result Turing test may not fully capture AI capabilities.
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…
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.
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…
Graphs can't learn certain tasks due to depth vs width limitations.
problem Understanding limitations of graph neural networks in learning specific tasks.
method Analyzing expressive power of GNNmp under depth, width, and node attributes.
result GNNmp can lose significant power when depth and width are restricted.
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.
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 …
The paper proposes a test for trading intelligence similar to the Turing Test.
problem Determining if trading programs exhibit intelligent behavior.
method Develops a test based on the Turing Test for financial trading programs.
result Introduces a method to assess trading intelligence in financial markets.
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…
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.
Framework evaluates medical image classification methods using a probabilistic model and a Twenty Questions paradigm.
problem Lack of detailed understanding of how machine learning methods make decisions in medical imaging.
method Inspired by the Turing Test, uses a probabilistic model and a Twenty Questions paradigm to evaluate classification methods based on task-specific concepts.
result Probabilistic model exposes dataset and method biases, reducing the number of queries needed for confident performance evaluation.
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.
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. …
Sapir, Birget and Rips showed how to construct groups from Turing machines. To achieve such a construction they introduced the notion of S-machine. Then considering a simplified S-machine Sapir and Olshanskii showed how to construct a group such that each of its asymptotic cone is non-simply connected. Still using the …
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…
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.
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.
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…
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…
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…
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.
Memory-Augmented Recurrent Networks improve dialogue coherence by expanding conversation history storage.
problem Fixed-size vectors limit dialogue coherence; attention mechanisms are computationally expensive.
method Introduce Neural Turing Machines (NTMs) to provide flexible and permanent storage for dialogue history.
result Improved perplexity performance compared to existing baselines.
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.
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…
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.
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.
sktime toolkit benchmarks time series classification algorithms for correctness and efficiency.
problem Benchmarking correctness and efficiency of time series classification algorithms.
method Implementation and comparison of six classifiers in sktime with their tsml equivalents.
result Significant differences in accuracy and efficiency between algorithms, with one causing debugging issues.
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.
Recent empirical results on long-term dependency tasks have shown that neural networks augmented with an external memory can learn the long-term dependency tasks more easily and achieve better generalization than vanilla recurrent neural networks (RNN). We suggest that memory augmented neural networks can reduce the ef…
The problem of attempting to learn the mapping between data and labels is the crux of any machine learning task. It is, therefore, of interest to the machine learning community on practical as well as theoretical counts to consider the existence of a test or criterion for deciding the feasibility of attempting to learn…
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…
Memory-augmented neural networks improve machine translation performance.
problem Improving machine translation accuracy and flexibility.
method Evaluation of Neural Turing Machines and Differentiable Neural Computers for machine translation tasks.
result Memory-augmented neural networks perform similarly to attentional encoders on Vietnamese to English tasks but have lower BLEU scores on Romanian to English tasks.
Unified theorem for deep and shallow joint-equivariant machines.
problem Universal approximation of joint-equivariant machines.
method Constructive universal approximation theorem based on ridgelet transform.
result Unified approximation of deep and shallow networks.
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.
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…
Recurrent neural networks (RNNs) are powerful constructs capable of modeling complex systems, up to and including Turing Machines. However, learning such complex models from finite training sets can be difficult. In this paper we empirically show that RNNs can learn models of computer peripheral devices through input a…
We show that deep narrow Boltzmann machines are universal approximators of probability distributions on the activities of their visible units, provided they have sufficiently many hidden layers, each containing the same number of units as the visible layer. We show that, within certain parameter domains, deep Boltzmann…