Structures Determined by Properties of Finite Families of Algorithms
Wiktor Dańko · Fundamenta Informaticae · 1985
In the paper the following problem stated by Tajtslin in 1979 is investigated: Let A = ⟨ A; f1, …, fn; r1, …, rm ⟩ be a structure. Are there functions f′1, …, f′p and relations r′1, …, r′q definable in A by means of algorithms such that every function relation definable over A by an algorithm is first-order definable in A + = ⟨ A; f1, …, fn, f′1, …, f′p; r1, …, rm, r′1, …, r′q⟩?