On the Turing Completeness of Modern Neural Network Architectures
Authors: Jorge Pérez, Javier Marinković, Pablo Barceló
ICLR 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show both models to be Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. [...] Theorem 3.4. The class of Transformer networks with positional encodings is Turing complete. Proof Sketch. [...] Theorem 4.1. The class of uniform Neural GPUs is Turing complete. Proof sketch. |
| Researcher Affiliation | Academia | Jorge P erez, Javier Marinkovi c, Pablo Barcel o Department of Computer Science, Universidad de Chile & IMFD Chile {jperez,jmarinkovic,pbarcelo}@dcc.uchile.cl |
| Pseudocode | No | The paper describes theoretical constructions and proofs, but it does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is a theoretical work focusing on Turing completeness proofs and does not mention releasing any source code. |
| Open Datasets | No | The paper is a theoretical study and does not use or reference any datasets for training. |
| Dataset Splits | No | The paper is a theoretical study and does not involve empirical validation with data splits. |
| Hardware Specification | No | The paper is theoretical and does not conduct experiments requiring hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, hyperparameters, or training configurations. |