Weak Essentially Undecidable Theories of Concatenation II

2021/12/27 by Juvenal Murwanashyaka, Murwanashyaka, Juvenal
Computer Science · #Computability, Logic, AI Algorithms #semigroups and automata theory #Numerical Methods and Algorithms

paper · pdf · doi:10.48550/arxiv.2112.13907

Abstract

We show that we can interpret concatenation theories in arithmetical theories without coding sequences.

Related

• Notes on Fragments of First-Order Concatenation Theory
• Mutual Interpretability of Weak Essentially Undecidable Theories
• First-Order Concatenation Theory with Bounded Quantifiers
• Arithmetic with Limited Exponentiation
• There are no minimal essentially undecidable Theories