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.
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
16 results for “Turing-completeness”
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 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.
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…
We introduce and demonstrate a new approach to inference in expressive probabilistic programming languages based on particle Markov chain Monte Carlo. Our approach is simple to implement and easy to parallelize. It applies to Turing-complete probabilistic programming languages and supports accurate inference in models …
This paper considers the computational power of constant size, dynamic Bayesian networks. Although discrete dynamic Bayesian networks are no more powerful than hidden Markov models, dynamic Bayesian networks with continuous random variables and discrete children of continuous parents are capable of performing Turing-co…
This paper explores the limits of Transformers in learning new patterns from scratch.
problem Understanding when Transformers can learn new patterns from scratch.
method Introducing the 'globality degree' to measure learnability and developing scratchpad techniques.
result Distributions with high globality cannot be learned efficiently by Transformers.
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…
While Recurrent Neural Networks (RNNs) are famously known to be Turing complete, this relies on infinite precision in the states and unbounded computation time. We consider the case of RNNs with finite precision whose computation time is linear in the input length. Under these limitations, we show that different RNN va…
We propose Edward, a Turing-complete probabilistic programming language. Edward defines two compositional representations---random variables and inference. By treating inference as a first class citizen, on a par with modeling, we show that probabilistic programming can be as flexible and computationally efficient as t…
Probabilistic programming languages (PPLs) are receiving widespread attention for performing Bayesian inference in complex generative models. However, applications to science remain limited because of the impracticability of rewriting complex scientific simulators in a PPL, the computational cost of inference, and the …
This work offers a broad perspective on probabilistic modeling and inference in light of recent advances in probabilistic programming, in which models are formally expressed in Turing-complete programming languages. We consider a typical workflow and how probabilistic programming languages can help to automate this wor…
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.
Two impossibility theorems show formal alignment certification is impossible for AI systems.
problem Formal certification of AI alignment over open-ended domains is impossible.
method Two independent impossibility theorems: Semantic and Statistical barriers.
result No procedure can simultaneously satisfy soundness, completeness, and tractability.
We describe Venture, an interactive virtual machine for probabilistic programming that aims to be sufficiently expressive, extensible, and efficient for general-purpose use. Like Church, probabilistic models and inference problems in Venture are specified via a Turing-complete, higher-order probabilistic language desce…
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…