A Criterion of Undecidability of Algorithmic Theories
Wiktor Dańko · Fundamenta Informaticae · 1981
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.