A Criterion of Undecidability of Algorithmic Theories

Article type: Research Article

Authors: Dańko, Wiktor

Affiliations: University of Warsaw, Division Białystok

Abstract: In this paper a criterion of undecidability of theories based on algorithmic logic [1,8] is formulated. By the application of this criterion we are able to assert undecidability of algorithmic theory finite fields, theories of date structures e.g. dictionaries, storage management system and others theories of structures with finite universes. It is also proved that every decidable algorithmic theory admits elimination of iteration quantifiers and examples of decidable algorithmic theories are given.

Keywords: Algorithmic logic, formalized theory, algorithmic properties, decidability, undecidability

DOI: 10.3233/FI-1981-4307

Journal: Fundamenta Informaticae, vol. 4, no. 3, pp. 605-628, 1981