Hilbert’s tenth problem for term algebras with a substitution operator

Issue title: CiE 2022

Guest editors: Ulrich Berger, Johanna Franklin and Elvira Mayordomo

Article type: Research Article

Authors: Murwanashyaka, Juvenal^{a; b; *}

Affiliations: [a] Department of Mathematics, University of Oslo, Norway | [b] Institute of Mathematics, Czech Academy of Sciences, Czech Republic

Correspondence: [*] Corresponding author. murwanashyaka@math.cas.cz.

Abstract: The analogue of Hilbert’s 10th Problem for a first-order structure A with signature L asks whether there exists an algorithm that given an L-sentence of the form ∃x→[s=t] decides whether ∃x→[s=t] is true in A. In this paper, we consider term algebras over a finite signature with at least one constant symbol and one function symbol of arity at least two. We investigate the structure we obtain by extending the term algebra with a substitution operator. We prove undecidability of the analogue of Hilbert’s 10th problem without relying on the solution to the original Hilbert’s 10th Problem.

Keywords: Hilbert’s 10th problem, term algebras, substitution operator

DOI: 10.3233/COM-230444

Journal: Computability, vol. 13, no. 3-4, pp. 433-457, 2024