An Example of a Complete First-Order Theory with All Models Algorithmically Trivial but Without Locally Finite Models

Abstract

We show an example of a first-order complete theory T, with no locally finite models and such that every program schema, total over a model of T, is strongly equivalent in that model to a loop-free schema. For this purpose we consider the notion of an algorithmically prime model, what enables us to formulate an analogue to Ryll-Nardzewski Theorem.