Inductive Logic Programming (ILP) systems use logic programming languages like Prolog as computational models. Expressivity of these languages is often built on fixed Herbrand vocabulary, thus requires encoding arbitrarily large structures as nested functions. However, most learning systems process structures directly on relations and cannot handle function symbols. To solve this, we propose an alternative problem framework to measure the expressivity of learning systems, by considering any Turing computable mapping between arbitrarily large graphs, namely Computable Relations Mapping (CRM). CRM is a useful framework for its connection to Turing machine and straightforward representation of most computational tasks. Then, we propose a minimal CRM-complete fragment of Horn clauses with default negation and function symbols, by constructing programs corresponding to all CRMs. The correctness is given by combining a checked implementation and some proof. Since smaller rules can be more efficiently searched and analyzed, we consider it a potentially better representation and reasoning model for expressive inductive inference systems.