Image de couverture de livre

Constant Bit-size Transformers Are Turing Complete

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Li, Qian, Wang, Yuyi
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity Machine Learning
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Efficient Turing Machine Simulation with Transformers
par: Li, Qian, et autres
Publié: (2025)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
par: Li, Qian, et autres
Publié: (2026)

On the Expressive Power and Limitations of Multi-Layer SSMs
par: Zubić, Nikola, et autres
Publié: (2026)

Ask, and it shall be given: On the Turing completeness of prompting
par: Qiu, Ruizhong, et autres
Publié: (2024)

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
par: Liu, Yuxi
Publié: (2025)

New Hardness Results for Low-Rank Matrix Completion
par: Chawin, Dror, et autres
Publié: (2025)

Flat origami is Turing Complete
par: Hull, Thomas C., et autres
Publié: (2023)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
par: Li, Zhiyuan, et autres
Publié: (2024)

On the Computational Hardness of Transformers
par: Saha, Barna, et autres
Publié: (2026)

Unlocking the Theory Behind Scaling 1-Bit Neural Networks
par: Daliri, Majid, et autres
Publié: (2024)

A Logic for Expressing Log-Precision Transformers
par: Merrill, William, et autres
Publié: (2022)

Infinite Time Turing Machines and their Applications
par: Weerawarana, Rukmal, et autres
Publié: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
par: Amiri, Alireza, et autres
Publié: (2025)

Turing Completeness and Sid Meier's Civilization
par: de Wynter, Adrian
Publié: (2021)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
par: Merrill, William, et autres
Publié: (2025)

Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
par: Bertschinger, Daniel, et autres
Publié: (2022)

Fundamental Limitations on Subquadratic Alternatives to Transformers
par: Alman, Josh, et autres
Publié: (2024)

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
par: Wang, Xiao
Publié: (2026)

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
par: Brösamle, Moritz, et autres
Publié: (2026)

No Complete Problem for Constant-Cost Randomized Communication
par: Fang, Yuting, et autres
Publié: (2024)

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
par: Wang, Jie, et autres
Publié: (2024)

Certifiable Boolean Reasoning Is Universal
par: Li, Wenhao, et autres
Publié: (2026)

Provably Overwhelming Transformer Models with Designed Inputs
par: Stambler, Lev, et autres
Publié: (2025)

Polyhedral Instability Governs Regret in Online Learning
par: Li, Yuetai, et autres
Publié: (2026)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
par: Chen, Bo, et autres
Publié: (2024)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
par: Hu, Jerry Yao-Chieh, et autres
Publié: (2024)

Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding
par: Chen, Yifang, et autres
Publié: (2025)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
par: Li, Xiaoyu, et autres
Publié: (2024)

Learning Tree Pattern Transformations
par: Neider, Daniel, et autres
Publié: (2024)

On the Hardness of Learning Regular Expressions
par: Attias, Idan, et autres
Publié: (2025)

Low-Rank Matrix Approximation for Neural Network Compression
par: Cherukuri, Kalyan, et autres
Publié: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
par: Cao, Yang, et autres
Publié: (2025)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
par: Huang, Jizhou, et autres
Publié: (2025)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
par: Rohatgi, Dhruv, et autres
Publié: (2025)

How Global Calibration Strengthens Multiaccuracy
par: Casacuberta, Sílvia, et autres
Publié: (2025)

Diffusion Language Models are Provably Optimal Parallel Samplers
par: Jiang, Haozhe, et autres
Publié: (2025)

Additive Models Explained: A Computational Complexity Approach
par: Bassan, Shahaf, et autres
Publié: (2025)

Smoothed Agnostic Learning of Halfspaces over the Hypercube
par: Kou, Yiwen, et autres
Publié: (2025)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
par: Jacot, Arthur
Publié: (2025)

Learnability of Parameter-Bounded Bayes Nets
par: Bhattacharyya, Arnab, et autres
Publié: (2024)