Structures Determined by Properties of Finite Families of Algorithms

Abstract

In the paper the following problem stated by Tajtslin in 1979 is investigated: Let $A$ = ⟨ A; f₁, …, f_n; r₁, …, r_m ⟩ be a structure. Are there functions f^′₁, …, f^′_p and relations r^′₁, …, 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; f₁, …, f_n, f^′₁, …, f^′_p; r₁, …, r_m, r^′₁, …, r^′_q⟩?

Keywords

algorithms programmability logics of programs algorithmic definability

Get full access to this article

View all access options for this article.