Weak theories of concatenation and minimal essentially undecidable theories

We consider weak theories of concatenation, that is, theories for strings or texts. We prove that the theory of concatenation \({\mathsf{WTC}^{-\varepsilon}}\) , which is a weak subtheory of Grzegorczyk’s theory \({\mathsf{TC}^{-\varepsilon}}\) , is a minimal essentially undecidable theory, that is, the theory \({\mathsf{WTC}^{-\varepsilon}}\) is essentially undecidable and if one omits an axiom scheme from \({\mathsf{WTC}^{-\varepsilon}}\) , then the resulting theory is no longer essentially undecidable. Moreover, we give a positive answer to Grzegorczyk and Zdanowski’s conjecture that ‘The theory \({\mathsf{TC}^{-\varepsilon}}\) is a minimal essentially undecidable theory’. For the alternative theories \({\mathsf{WTC}}\) and \({\mathsf{TC}}\) which have the empty string, we also prove that the each theory without the neutrality of \({\varepsilon}\) is to be such a theory too.