Skip to main content
1 of 4

Example of strong reducibility but not an effective interpretation?

A countable structure A is strongly reducible to a structure B if there is a uniform turing functional which, given a copy of the atomic diagram of B, computes a copy of the atomic diagram of A.

A is said to be effectively interpretable in B if A is strongly reducible to B via a computable functor from the category of copies of A to the category of copies of B.

What is an example of two countable structures A,B such that A is strongly reducible to B but A is not effectively interpretable in B?