Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-18T06:41:45.402Z Has data issue: false hasContentIssue false
  • English
  • Français

Computation over algebraic structures and a classification of undecidable problems

Published online by Cambridge University Press:  20 June 2016

CHRISTINE GAßNER
CHRISTINE GAßNER*
Affiliation:
Institut für Mathematik und Informatik, Ernst-Moritz-Arndt-Universität, Walther-Rathenau-Straße 47, D-17487, Greifswald, Germany Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a uniform model of computation over algebraic structures resulting from a generalization of the Turing machine and the BSS model of computation. This model allows us to gain more insight into the reasons for unsolvability of algorithmic decision problems from different perspectives. For example, classes of undecidable problems can be introduced in several ways by analogy with the classical arithmetical hierarchy and, for many structures, the different definitions lead to different hierarchies of undecidable problems. Here, we will investigate some classes of a hierarchy that is defined semantically by our deterministic oracle machines and that can be syntactically characterized by formulas whose quantifiers range only over an enumerable set. Starting from machines over algebraic structures endowed with some relations and containing an infinite recursively enumerable sequence of individuals, we will also consider this hierarchy for BSS RAM's over the reals and some undecidable problems defined by algebraic properties of the real numbers.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 8: Continuity, Computability, Constructivity: From Logic to Algorithms 2013 , December 2017 , pp. 1386 - 1413
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Asveld, P.R.J. and Tucker, J.V. (1982). Complexity theory and the operational structure of algebraic programming systems. Acta Informatica 17 451–476. http://dx.doi.org/10.1007/BF00264163.Google Scholar
Blum, L., Cucker, F., Shub, M. and Smale, S. (1998). Complexity and Real Computation, Springer.CrossRefGoogle Scholar
Blum, L., Shub, M. and Smale, S. (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society 21 1–46. http://projecteuclid.org/euclid.bams/1183555121.CrossRefGoogle Scholar
Börger, E. (1992). Berechenbarkeit, Komplexität, Logik, Vieweg.CrossRefGoogle Scholar
Bournez, O., Cucker, F., de Naurois, P.J. and Marion, J.-Y. (2003). Computability over an arbitrary structure: Sequential and parallel polynomial time. In: Proceeding FOSSACS'03/ETAPS'03 185–199. http://dx.doi.org/10.1007/3-540-36576-1_12.CrossRefGoogle Scholar
Bournez, O., Cucker, F., de Naurois, P.J. and Marion, J.-Y. (2006). Implicit complexity over an arbitrary structure: Quantifier alternations. Information and Computation 202 (2) 210–230. http://dx.doi.org/10.1016/j.ic.2005.07.005 Google Scholar
Calvert, W., Kramer, K. and Miller, R. (2011). Noncomputable functions in the Blum-Shub-Smale model. Special Issue for the “Seventh International Conference on Computability and Complexity in Analysis (CCA 2010)”; Logical Methods in Computer Science 7 (2:15) (2011), 1–20. http://dx.doi.org/10.2168/LMCS-7(2:15)2011.Google Scholar
Cucker, F. (1992). The arithmetical hierarchy over the reals. Journal of Logic and Computation 2 (3) 375–395. http://dx.doi.org/10.1093/logcom/2.3.375.CrossRefGoogle Scholar
Cucker, F. and Koiran, P. (1995). Computing over the reals with addition and order: Higher complexity classes. Journal of Complexity 11 358–376. http://dx.doi.org/10.1006/jcom.1995.1018.CrossRefGoogle Scholar
Dobkin, D. and Lipton, R.J. (1978). A lower bound of $\frac12n^2$ on linear search programs for the knapsack problem. Journal of Computer and System Sciences 16 (3) 413–417. http://dx.doi.org/10.1016/0022-0000(78)90026-0.CrossRefGoogle Scholar
Friedman, H. and Mansfield, R. (1992). Algorithmic procedure. Transactions of the AMS 332 297–312.Google Scholar
Gaßner, C. (1997). On NP-completeness for linear machines. Journal of Complexity 13 259–271. http://dx.doi.org/10.1006/jcom.1997.0444.CrossRefGoogle Scholar
Gaßner, C. (2009). Oracles and relativizations of the P =? NP question for several structures. Journal of Universal Computer Science 15 (6) 1186–1205. http://dx.doi.org/10.3217/jucs-015-06-1186.Google Scholar
Gaßner, C. (2013). Strong Turing degrees for additive BSS RAM's. Logical Methods in Computer Science 9 (4:25) 1–18. http://dx.doi.org/10.2168/LMCS-9(4:25)2013.Google Scholar
Grädel, E. (2007). Finite model theory and descriptive complexity. In: Grädel, E., Kolaitis, P.G., Libkin, L., Marx, M., Spencer, J., Vardi, M.Y., Venema, Y. and Weinstein, S. (eds.) Finite Model Theory and Its Applications, Springer, 125–230.CrossRefGoogle Scholar
Hemmerling, A. (1998). Computability of string functions over algebraic structures. Mathematical Logic Quarterly 44 1–44. http://dx.doi.org/10.1002/malq.19980440102.CrossRefGoogle Scholar
Kleene, S.C. (1952). Introduction to Metamathematics, North-Holland Publ. Co.Google Scholar
Koiran, P. (1995). Computing over the reals with addition and order. Theoretical Computer Science 133 35–47. http://dx.doi.org/10.1016/0304-3975(93)00063-B.Google Scholar
Meer, K. and Ziegler, M. (2008). An explicit solution to post's problem over the reals. Journal of Complexity 24 3–15. http://dx.doi.org/10.1016/j.jco.2006.09.004.CrossRefGoogle Scholar
Moschovakis, Y.N. (1969). Abstract first order computability. I. Transactions of the American Mathematical Society 138 427–464. http://dx.doi.org/10.2307/1994926.Google Scholar
Moschovakis, Y.N. (1980). Descriptive set theory. Studies in Logic and the Foundations of Mathematics 100, North-Holland.Google Scholar
Poizat, B. (1995). Les Petits Cailloux. Aléas.Google Scholar
Preparata, F.P. and Shamos, M.I. (1985). Computational Geometry: An Introduction, Springer.Google Scholar
Scott, D. (1967). Some definitional suggestions for automata theory. Journal of Computer and System Sciences 1 (2) 187–212. http://dx.doi.org/10.1016/S0022-0000(67)80014-X.Google Scholar
Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer.Google Scholar
Spreen, D. (1995). On some decision problems in programming. Information and Computation 122 120–139. http://dx.doi.org/10.1006/inco.1995.1143. Corrigendum ibid. 148 (1999) 241–244. http://dx.doi.org/10.1006/inco.1998.2758 CrossRefGoogle Scholar
Spreen, D. (2010). Every Δ0 2-set is natural, up to Turing equivalence. In: Ferreira, F. et al., (eds.) CiE2010, Lecture Notes in Computer Science 6158, Springer (2010), 386–393. http://dx.doi.org/10.1007/978-3-642-13962-8_43 Google Scholar
Tavana, N. and Weihrauch, K. (2011). Turing machines on represented sets, a model of computation for analysis. Logical Methods in Computer Science 7 (2) 1–21. http://dx.doi.org/10.2168/LMCS-7(2:19)2011.Google Scholar
Tucker, J.V. and Zucker, J.I. (2001). Computable functions and semicomputable sets on many-sorted algebras. Handbook of Logic in Computer Science 5 397–525.Google Scholar