Algorithmic Triviality of Abstract Structures
Paweł Urzyczyn · Fundamenta Informaticae · 1981
In the present paper we investigate algorithmically trivial structures, that is structures where every recursive function (relation) is definable by a first-order open formula. We prove that algorithmic triviality is equivalent to a property called the unwind property. We also study the notion of effective interpretation of structures and its relation to algorithmic triviality.