Translatability of schemas over restricted interpretations

摘要

We study a notion of translatability between classes of schemas when restrictions are placed on interpretations. Unlike the usual notion of translatability, our translatability lets the translation depend on the interpretation.We consider five classes of schemas. Three of these have been extensively studied in the literature: flow-chart, flow-chart with counters, and recursive. The two others are defined herein; the first of which is a class of “maximal power” and is equivalent to similarly motivated classes of other investigators; while the second is, in some sense, a nontrivial class of “minimal power”.Our main results specify restrictions on interpretations that will allow the translatability of a class into a class , not being translatable into over all (or unrestricted) interpretations. Additional results specify restrictions on interpretations under which is not translatable into ; the proofs of these clarify the mechanisms in the main results. Last, we consider the notion of effective computability in algebraic structures in the light of the main results.