Cover Image

A Characterization of Turing Machines that Compute Primitive Recursive Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Schwartz, Daniel G.
Format:	Preprint
Published:	2025
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Self-Replicating Mechanical Universal Turing Machine
by: Lano, Ralph P.
Published: (2024)

TuringQ: Benchmarking AI Comprehension in Theory of Computation
by: Zahraei, Pardis Sadat, et al.
Published: (2024)

Store Languages of Turing Machines and Counter Machines
by: Friesen, Noah, et al.
Published: (2025)

Cayley Automatic Groups and Numerical Characteristics of Turing Transducers
by: Berdinsky, Dmitry
Published: (2016)

Characterization of Isometric Words based on Swap and Mismatch Distance
by: Anselmo, M., et al.
Published: (2024)

Notes on Stack Machines and Quantum Stack Machines
by: Qiu, Daowen
Published: (2025)

Networks of Moore Machines
by: Yodaiken, Victor
Published: (2015)

Large Language Models and the Extended Church-Turing Thesis
by: Wiedermann, Jiří, et al.
Published: (2024)

Recursive Prime Factorizations: Dyck Words as Numbers
by: Childress, Ralph L.
Published: (2021)

Characterizing normality via automata and random matrix products
by: Bienvenu, Laurent, et al.
Published: (2026)

Computational Complexity of Alignments
by: Schwanen, Christopher T., et al.
Published: (2026)

Digital Circuits as Moore Machines
by: Yodaiken, Victor
Published: (2010)

Recursive numeral systems are highly regular and easy to process
by: Prasertsom, Ponrawee, et al.
Published: (2025)

Algebraic Characterization of FO-definable Languages of Higher-Dimensional Automata
by: Erlich, Enzo, et al.
Published: (2026)

Characterizations of Controlled Generation of Right Linear Grammars with Unknown Behaviors
by: Ise, Daihei, et al.
Published: (2024)

Computational Model for Parsing Expression Grammars
by: Rubtsov, Alexander, et al.
Published: (2024)

Temporal Causal Models as a Model of Computation
by: Gladyshev, Maksim, et al.
Published: (2026)

Visibly Recursive Automata
by: Dubrulle, Kévin, et al.
Published: (2026)

Attributed Tree Transducers for Partial Functions
by: Maneth, Sebastian, et al.
Published: (2024)

Undecidability of the Emptiness Problem for Weak Models of Distributed Computing
by: Principato, Flavio T., et al.
Published: (2025)

Computing measures of weak-MSO definable sets of trees
by: Niwiński, Damian, et al.
Published: (2024)

Inform: From Compartmental Models to Stochastic Bounded Counter Machines
by: Leys, Tim, et al.
Published: (2024)

Spatio-Temporal view on the Topological Functioning Model
by: Spichkova, Maria
Published: (2025)

On the Complexity of Computing the Co-lexicographic Width of a Regular Language
by: Becker, Ruben, et al.
Published: (2024)

Active Inference of Extended Finite State Machine Models with Registers and Guards
by: Groz, Roland, et al.
Published: (2026)

Characterization of deterministically recognizable weighted tree languages over commutative semifields by finitely generated and cancellative scalar algebras
by: Fülöp, Zoltán, et al.
Published: (2025)

Stochastic Process Turing Machines
by: Wolpert, David, et al.
Published: (2024)

Elementary Cellular Automata as Non-Cryptographic Hash Functions
by: McKinley, Daniel
Published: (2025)

Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
by: Bell, Jason P., et al.
Published: (2022)

Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
by: Mazowiecki, Filip, et al.
Published: (2025)

Distribution of Reconfiguration Languages maintaining Tree-like Communication Topology
by: Hausmann, Daniel, et al.
Published: (2024)

Automata Learning with an Incomplete but Inductive Teacher (Technical Report)
by: Stan, Daniel, et al.
Published: (2026)

You May Delay, but Time Will Not: Timed Games Under Delayed Control
by: Larsen, Kim G., et al.
Published: (2025)

Time for Timed Monitorability
by: Grosen, Thomas M., et al.
Published: (2025)

Efficient Runtime Verification of Real-Time Systems under Parametric Communication Delays
by: Fränzle, Martin, et al.
Published: (2024)

Exploiting Assumptions for Effective Monitoring of Real-Time Properties under Partial Observability
by: Cimatti, Alessandro, et al.
Published: (2024)

Characterizing Implementability of Global Protocols with Infinite States and Data
by: Li, Elaine, et al.
Published: (2024)

A Unifying Approach to Picture Automata
by: Meeres, Yvo Ad, et al.
Published: (2025)

A Variety of Request-Response Specifications
by: Aiba, Daichi, et al.
Published: (2025)

A Close Analysis of the Subset Construction
by: Baburin, Ivan, et al.
Published: (2024)