Olivier Wang
email: olivier.wang@polytechnique.edu

Christian De

Sainte Marie

Changhai Ke
email: changhai.ke@fr.ibm.com

Leo Liberti
email: liberti@lix.polytechnique.fr

Universality and prediction in business rules

Keywords: Business rules, Statistical learning, Operational semantics, Turing-completeness

published or not. The documents may come

INTRODUCTION

Rules are among the oldest and best studied knowledge representation paradigms for automated reasoning [START_REF] Brachman | Knowledge Representation and Reasoning[END_REF]. Business Rules (BR) are a newer concept, devised to allow corporations to digitally encode business process knowledge into a centralized storage and into a manageable form.

A more complete definition, given in natural (rather than formal) language, is given in the BR manifesto [START_REF] Business | The business rules manifesto <www[END_REF]. The BR manifesto says, among other things, that BRs are sentences in natural language, aimed at business people, but susceptible to be parsed by a computer system into a BR management system. Their goal is to encode business processes into a set of easily and automatically managed digital objects.

The fact that most BR Management Systems (BRMS) are also able to execute those rules as if they were computer programs means that BRs, written by business people in natural language, are eventually turned into formal sentences, as no computer-executed code can ever be ambiguous at the machine level.

Here, we study the problem of parametrizing BRs so their output will conform to a certain prescribed average behaviour. This is necessary when business strategies must be constrained at the global level (by choice or regulatory necessity) without unduly influencing any of the local business processes encoded by BRs. We show that it is impossible to find a single computer algorithm which can solve this problem for any given BR, but we derive an operational semantics for proving formal properties for some BR subsets.

Scope

In this paper we shall consider BRs in their (restricted) interpretation as formal sentences of a programming language.

We note that there is no universally accepted "generic" language for expressing BR with [START_REF] Von Halle | Business Rules Applied: Building Better Systems Using the Business Rules Approach[END_REF][START_REF] Ross | Principles of the Business Rule Approach[END_REF][START_REF] Giurca | Handbook of Research on Emerging Rule-Based Languages and Technologies: Open Solutions and Approaches[END_REF]. Since most of the theoretical part of this paper is concerned with an inexistence theorem, we do not need to concern ourselves with a multitude of dialects. It suffices to consider a rather minimal BR language variant consisting of BRs of the form "if condition then action". The action clause assigns a sequence of values to a corresponding sequence of variables, or executes a script which interacts dynamically with the environment.

We already mentioned that most BRMSs come with execution platforms, called interpreters. As for the BR languages themselves, there are many interpreters, more or less powerful [START_REF] Ligeza | Logical Foundations for Rule-Based Systems[END_REF][START_REF] Hanson | Gator: An optimized discrimination network for active database rule condition testing[END_REF], the classic one being the Rete algorithm [START_REF] Forgy | Rete: A fast algorithm for the many patterns/many objects match problem[END_REF]. For the same reasons as before, we do not need to consider all the variants; a minimal interpreter will suffice.

The research content reported in this paper was commissioned and co-authored by IBM, specifically the research group that develops and maintains the IBM BRMS, called Operational Decision Manager (ODM). Our minimal BR language and interpreter are both acceptable abstract models for the Rete-based engine used in ODM. While many users of industrial BRMS do not exploit the sophisticated Rete-based engine, it is nonetheless used by about twenty percent of BRMS applications, based on private IBM data. Example of rules that use Rete chaining include: price computation, fraud detection, and route planning. The fact that our work rests on an abstract model of ODM makes it relevant in most if not all major BRMS (FICO Blaze, JBoss Rules, Oracle BRE), as they all have a similar Retebased engine. Similarly, some of the major free and/or open-source rule engines are also Rete-based, such as CLIPS [START_REF] Culbert | CLIPS Basic Programming Guide[END_REF], Jess (on which Oracle BRE is based) [START_REF] Friedman-Hill | JESS in Action[END_REF], or DROOLS (on which JBoss Rules is based) [START_REF] Proctor | Drools: a rule engine for complex event processing[END_REF]. This means that potentially up to twenty percent of the whole Business Rules market motivates this work, and it is relevant for the whole of the field, not just IBM.

To summarize, we call a BR program a set of "if condition then action"-formatted BRs executed by a basic BR interpreter. We call the union of all valid BR programs the BR programming language.

Motivation and relevance of the main problem

In this paper we study the following problem: can a given BR program be parametrized so that it behaves statistically according to a prescribed goal on every input? More precisely, the question we answer is the following.

BUSINESS RULES WITH AVERAGE GOALS (BRAG).

Determine whether there exists an algorithm A which takes as an input:

• a BR program ρ = Pp(x), where p is a parameter vector, x is an input vector, and ρ is a scalar output,

• the set X of all possible inputs of P , • a prescribed set G of values for ρ, and which returns, as an output, a vector p * = A(P, G, X) such that:

E(Pp * (x) | x ∈ X) ∈ G, (1)
where E(•) denotes the expectation.

The BRAG problem arose out of the request of many users of the IBM ODM BRMS. Why is this question important to industry? We answer by way of a case scenario proposed by the IBM team which maintains ODM. Consider a bank which has a process (encoded as a parametrizable BR program P p ) for deciding whether to grant a loan to a given customer. The test conditions in P p may verify anagraphic, work-related and credit ranking data about the customer (encoded in a vector x), and p is usually given by acceptable thresholds for customer data or functions thereof. The output ρ of P p in this case might be a YES/NO/REVIEW type value, where REVIEW corresponds to cases requiring a personalized follow-up by a financial advisor. Of course, banks have to consider the volume of REVIEW outputs carefully. Accordingly, banks will try to choose p so that P p automates only a given fraction g ∈ [0, 1] of the decisions over all loan requests on average. An obvious way to deal with the issue could be to pick an appropriate training sample S and run some Machine Learning (ML) algorithm to learn the BR program configuration parameter vector p so as to satisfy Eq. ( 1). This, finally, begs the question above: is this direction even theoretically possible, in full generality? In this paper we will argue that this is not possible in general.

To achieve this negative result, we look at the question from the point of view of the expressiveness of the BR programming language. Within the panorama of programming languages, one can distinguish two main categories: imperative and declarative. Since both categories contain Turing-complete languages, a separation of the two categories according to computational expressive power is impossible. On the other hand, by looking at three basic building blocks present in all imperative languages (assignments, tests and loops), we can informally segment programming languages more finely: purely imperative languages have explicit constructs for all three blocks, and purely declarative languages do not have explicit constructs for any of those building blocks. One of the earliest computational models, the lambda-calculus [START_REF] Church | A set of postulates for the foundation of logic[END_REF], embodies loops within the language itself by using recursion, while tests and assignments may be simulated using boolean variables and arithmetic operators; the situation of Prolog [START_REF] Clocksin | Programming in Prolog[END_REF] is similar. Constraint Programming [START_REF] Apt | Principles of Constraint Programming[END_REF] and Mathematical Programming [START_REF] Williams | Model Building in Mathematical Programming[END_REF] appear to be purely declarative, in the sense that the language itself does not provide constructs of assignments, tests or loops. Perhaps the purest form of a declarative language is given by systems of Diophantine equations, famously shown to be Turing-complete when Hilbert's 10th problem was solved in the negative [START_REF] Matiyasevich | Hilbert's Tenth Problem[END_REF]. In this taxonomy, the BR language explicitly provides assignments and tests, but has no loop construct. Among the other programming languages we mentioned, recursive functions have been famously proved to be equivalent to Turing Machines (TM) by A. Turing himself [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF]. For inference rules, including Prolog, we refer the reader to [START_REF] Sneyers | The computational power and complexity of constraint handling rules[END_REF]. For Mathematical Programming, see [START_REF] Liberti | Mathematical programming: Turing completeness and applications to software analysis[END_REF].

Contributions

This paper makes the following contributions: (a) it provides a constructive proof of Turing-completeness for the BR language; (b) it formally shows that this language is unlearnable in the Probably Approximately Correct (PAC) framework (see Sect. 4), and therefore that ML tools cannot be used in general to "learn the behavior" of BR programs statistically; (c) it proposes an operational semantics for the BR language. As a token of the practical applicability of our ideas, we show that on a few small but interesting examples our operational semantics can prove termination of entire sets of programs having some input parameter ranging over a given interval. We note that the same operational semantics can also be used to prove non-termination. Moreover, failure to prove termination can be taken as indicative of a risk of non-termination.

With respect to [START_REF] Wang | The learnability of business rules[END_REF], the Turing-completeness proof presented here, the operational semantics, and the associated proof-of-concept implementation, are new. We remark that since the BR language itself is Turing-complete, the termination of its programs, which we claim can be computed by our operational semantics, is obviously an undecidable problem. As a consequence, operational semantics can prove termination and non-termination of some sets of programs, but not of every program. We also remark that, as far as we could ascertain, ours is the first proof in the literature of the PAC-unlearnability of BR programs.

Structure of the negative result

In order to prove that the BRAG problem has no solution, we argue that the dynamics of a generic BR program cannot be machine-learned in a certain well-known abstract learning model (PAC learning, see Sect. 4). We achieve this by showing that certain functions witnessing non-PAC-learnability can be implemented using BR programs; and we prove this latter property by showing that the BR programming language is Turing-complete.

That certain declarative rule-based languages are Turing-complete is already known [START_REF] Sneyers | The computational power and complexity of constraint handling rules[END_REF], but we provide here a new proof that also opens the door to the construction of a positive result: an operational semantics for BRs that can be used empirically to determine wether some given BR programs terminate or not (as mentioned above, since BRs are Turing-complete, determining termination in general is impossible -our operational semantics can prove termination/nontermination of certain instances, but certainly not all).

More specifically, our proof that the BR language is Turing-complete is centered around the idea that BR programs, when executed via an appropriate execution algorithm, behave like WHILE programs, which are known to be Turing-complete [START_REF] Harel | On folk theorems[END_REF]. From Turingcompleteness, we conclude that any computable function can be simulated by a (universal) BR program, including functions that output pseudo-random numbers. This is the main idea behind the proof of PAC-unlearnability. Our operational semantics for BR programs is derived from the reduction from the WHILE language in the Turing-completeness proof.

Contents

The rest of this paper is organized as follows. Section 2 is used to formalize the notations and concepts of BRs we use in this paper. Section 3 exhibits our constructive proof of Turingcompleteness, and recalls another, non-constructive one. Section 4 uses Pseudorandom Functions (PRF) and a chaotic map to prove PAC-unlearnability in both a weak and a strong sense. Section 5 showcases an operational semantics for BRs, discusses a proof-of-concept implementation, and illustrates some of its possible applications on small number of test cases.

PRELIMINARIES

Limited to the scope of this paper (Sect. 1.1), BR programming can be seen as programming for non-programmers. The two most difficult computer programming concepts for a layperson to understand appear to be loops and function calls. BR disposes of the former by automatically executing programs over a loop construct embedded in the interpreter, and of the latter by removing them entirely. In commercial BR management systems such as ODM function calls are replaced by entities called "meta-variables", which have no relevance to the present discussion.

Formalization

A BR program simply consists of an ordered set of rules. Given a variable sequence x, a rule is defined as shown in Alg. 1; T is the condition and A describes the action. While the variables are sometimes typed, we dispense with this distinction in the general discussion.

Algorithm 1 A Business Rule if T (x) then x ← A(x) end if
At least one of the variables, say x 1 without loss of generality, is selected to be the output of the BR program.

As stated in Sect. 1.1, there are many variations of BR interpreters, but we need only employ a very basic one. Most deterministic interpreters are semantically equivalent to the RIF formalization (de Sainte [START_REF] De Sainte | Rif production rule dialect[END_REF]. We therefore use the interpreter I 0 consisting of the following algorithm:

(1) select the rules for which the condition is True, using the current values of the variables;

(2) execute the action of the first rule in the current selection or stop if there is no such rule;

(3) repeat from Step (1).

The selection of the rule to be executed in Step ( 2) is referred to as conflict resolution. Our algorithm has a simplistic conflict resolution strategy: whenever more than one rule instance could be executed, the one selected is obtained from a fixed total order on rule instances. An example of the execution of such an algorithm is described in Fig. 1.

While we have used a very simple execution algorithm where conflict resolution is based on a fixed ordering of rules, most BR execution algorithms are more complex. Any nontrivial interpreter, however, can be simulated by the basic one I 0 (except in extreme cases, such as a conflict resolution strategy leading to a bounded number of execution loops).

The Variables

int x ← 1 int age ← 90
The Rules (in order) In the total order considered by the algorithm, they are: R 1 :

if

(age 1∧x = 2) then(age ← 0,x ← 0) R 2 : if (x = 1) then(x ←x+1) R 3 : if (age 60) then(age ←age+1)
The Execution

Iteration 1: Truth value of conditions:

t(R 1 ) = False t(R 2 ) = True t(R 3 ) = True
Rule instances selected (in order): R 2 Rule executed: R 2 Variable values: x = 2 age = 90

Iteration 2: t(R 1 ) = True t(R 2 ) = False t(R 3 ) = True Rules selected: R 1 , R 3 Rule executed: R 1 Variable values: x = 0 age = 0 Iteration 3: t(R 1 ) = False t(R 2 ) = False t(R 3 ) = False Rules selected: None Rule executed: None END FIGURE 1.
Example illustrating the execution algorithm

Some remarks on non-trivial BR program interpreters

The most common BR interpreters use an execution algorithm with a structure similar to ours, but with a different conflict resolution strategy in step 2. Common conflict resolution strategies combine at least the following three elements (de Sainte Marie et al., 2013):

• Refraction which prevents a rule instance from firing (being selected by the conflict resolution algorithm) again unless its condition clause has been reset.

• Priority which is a kind of partial order on rules, leading of course to a partial order on rule instances.

• Recency which orders rule instances in decreasing order of continued validity duration (when rule instances are created at run time, it is often expressed as increasing order of rule instance creation time).

We will see in the last section that these other interpreters do not preclude the use of the operational semantics techniques we introduce in this paper.

TURING-COMPLETENESS

Basic notions

A Universal Turing Machine (UTM) is a Turing Machine (TM) which can simulate any other TM on arbitrary input [START_REF] Shannon | A universal Turing machine with two internal states[END_REF][START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF]. Let L be a programming language for the UTM U , described for example by its formal grammar. By means of a special program I called interpreter, programs written in L can be executed on U [START_REF] Minsky | Computation: Finite and Infinite Machines[END_REF]. If a programming language L can be used to write all possible programs of a UTM so they are executed via an interpreter, then L is said to be Turing-complete.

Definition 1 (Turing-completeness): Let U be a UTM, which takes as input a string (T, x) consisting of a TM description and its input. A programming language L is Turing-complete if there exists an interpreter I such that for each possible input (T, x) of U there is a program p in L with I (p) = (T, x).

Note that in Defn. 1, I is seen as a function that maps programs p in L to the input (T, x) of the UTM U . It is assumed that U will then execute with (T, x) as input. The output of this computation is the effect that the program p has when executed on U via the interpreter I . We can replace "UTM" in Defn. 1 by any universal computer described in any Turingcomplete language L , since interpreters can be composed via translators. Given two programming languages L, L with interpreters I , I running on UTMs U, U , a translator is a pair of functions (T , τ ), where T maps programs of L to programs of L and τ maps valid outputs of U to valid outputs of U , such that:

∀p ∈ L U (I (p)) = τ (U (I (T (p)))). (2)
In other words, the effect of running p through I is related to the effect of running the translation of p through I . Most commonly τ is the identity, i.e. we want the translated program to yield the same output as the same program.

The type of translators we are interested in are the faithful ones, i.e. those for which T is surjective and τ is bijective. The meaning of a surjective mapping T is technical (see the proof of Thm. 1) and can be relaxed. In particular, if one were to write I as a program p of L , mapping every p to the interpreter p could suffice. The bijection on the ranges of the UTMs, on the other hand, is essential, and ensures universality. Such translators allow the "expressive power" of the corresponding languages to match. Next, we will state and prove a theorem that formalizes the concept of translation needed in this paper.

Theorem 1: Let L be a Turing-complete programming language with interpreter I running on a UTM U . Let L be another programming language, U another UTM, and (T , τ ) a faithful translator from L to L . Then there exists an interpreter I of L on U that makes L Turing-complete.

Proof. Let (T , x ) be an input of U . Since τ is a bijection, there is an input (T, x) of U such that

U (T, x) = τ (U (T , x )). ( * )
Since L is Turing-complete, there is a program p ∈ L such that I (p) = (T, x). Let p = T (p), and define I (p ) = (T , x ). Since T is surjective, I is defined for all p ∈ L . Now by definition of translator we have U (I (p)) = τ (U (I (T (p)))). Since I (p) = (T, x), by ( * ) the latter equality gives τ (U (I (p ))) = τ (U (T , x )) which, since τ is a bijection, implies U (I (p )) = U (T , x ), which proves that the definition of I is consistent with an interpreter. We have shown that for each input (T , x ) of U there is a program p of L that is interpreted to (T , x ), which makes L Turing-complete.

The computability concepts discussed above are at the basis of computability theory, and have been well known for at least 60 years. Thm. 1 could also be proved using a result of [START_REF] Curtis | A Turing Machine simulator[END_REF], which states that since a UTM is defined as a TM which is able to simulate any other TM, L can be proven Turing-complete by showing that for any TM, L can be used to describe that TM via its interpreter. It would then suffice to give an explicit mapping between the formal grammars of L and L , leading to a semantics for L in terms of L. We strongly suspect that even the statement and proof of Thm. 1 given above is not new, at least in its main traits, though we could not find it in the (overwhelmingly rich) literature on the matter. Most of these observations hold under the Church-Turing thesis [START_REF] Church | An unsolvable problem of elementary number theory[END_REF][START_REF] Turing | Systems of Logic Based on Ordinals[END_REF][START_REF] Gandy | Church's thesis and the principles for mechanisms[END_REF], according to which any effectively computable function is Turing-computable. In other words, no device or program can compute a function that a UTM cannot.

WHILE programs

The Turing-completeness of WHILE-programs is well-known [START_REF] Harel | On folk theorems[END_REF]. We exploit this fact and the previous results to prove the Turing-completeness of BR programs. We show that any WHILE-program can be programmed using a set of BRs and the basic BR interpreter. Furthermore, any non-trivial BR interpreter involving a loop is also Turingcomplete, as it can simulate the basic interpreter used in this article.

The WHILE programming language has been studied with or without a name as the simplest form of imperative programming since 1969 [START_REF] Hoare | An axiomatic basis for computer programming[END_REF]. It has three simple syntactic elements: assignments, conditional actions (if. . . then blocks), and while loops.

A WHILE program has the canonical (recursive) form [START_REF] Harel | On folk theorems[END_REF][START_REF] Hirose | Some results in general theory of flow charts[END_REF]:

while T 0 (x) do ifblock 1 (T 1 , A 1 , x) . . . ifblock K (T K , A K , x) end while where, for each k K, ifblock k (T k , A k , x) is defined either as: if T 1 k (x) then x ← A 1 k (x) ifblock(T k , A k , x) end if
or as an empty command. The interpretation of the symbols T i k (x) and A i k (x) is: T are (possibly jagged) tensors of Boolean conditions on the variables x, which evaluate to True or False, and A is a (possibly jagged) tensor of functions of x yielding values to be assigned to the variables.

In other words, a WHILE program is a single conditional loop containing a sequence of (possibly nested) test conditions followed by a conditional assignment action.

Translation of WHILE to BR

We prove that the BR language is Turing-complete (under the basic interpreter) by providing a translation of WHILE programs using BRs.

Theorem 2: Any WHILE program is computable by an equivalent BR program.

We prove this by showing that a generic WHILE program can be interpreted into a BR program. The only requirement of the interpretation is to be computable. We first prove this for WHILE programs without nested if statements, then we describe a sequence of syntactical steps on the symbols of a generic WHILE program which transforms it into a WHILE program without nested if statements.

Lemma 1: Any WHILE program without nested if statement can be translated to a BR program.

Proof. Given the following WHILE program without nested if statements:

1: while T0(x) do 2: if T1(x) then 3: x ← A1(x) 4: end if 5:
. . .

6:

if TK (x) then 7:

x ← AK (x) x ← AK (x) 10: end if Using previous notations, rule R 0 has T (x) = ¬B 0 (x) with Stop as action, while for k ∈ {1, ..., K} rule R k has T (x) = B k (x) and A(x) = A k (x). This is obviously equivalent to the WHILE program considered.

Lemma 2: Any WHILE program can be transformed into an equivalent WHILE program without nested if statements.

Proof. This is an easy proof, as the lemma amounts to saying any nested if statements can be unnested. A simple inductive reasoning on the depth of the nesting proves the result (possibly adding boolean variables to store the value of intermediate levels tests). The property applied to each ifblocks of a WHILE program transforms it into the form we want.

We summarize the discussion in the following proposition.

Proposition 1: There is a faithful translator (T , τ ) from the WHILE language to the BR language.

Proof. Note that τ is the identity, which is a bijection.

Finally, we invoke Thm. 1.

Corollary 1: The BR language is Turing-complete.

A direct proof

While the above proof is sufficient to justify the Turing-completeness of BRs, we can also use a much more direct proof by exhibiting a BR program that simulates a UTM. Such a BR program is exhibited in Fig. 2. We use meta-variables to make the BR program readable, as R 1 would otherwise be written as

Q × 3 × Q × S distinct rules.
We suppose the variables include the following: • many (static) state objects of type "state": q 1 , . . . , q Q • many (static) symbol objects of type "symbol": s 1 , . . . , s S • a (static) finite set of terminal states of type "terminal": Ter • a (static) blank symbol of type "symbol": s b • a (static) set of Turing rules of type "rules", of the form (state initial , symbol initial , right|left|stay, statenext, symbol written ): R = {(q i r , s i r , actr, q f r , s f r ) | actr ∈ {"left", "right", "stay"}}r • the current state of type "state": q • the length of the visible tape data, of type "length": l • the current visible tape data of type "tape":

T = {(i, s i ) | i ∈ N, 0 i l -1}
where l is the length of the visible tape data • the current place on the tape of type "position": p We use the following meta-variables in the BR program that simulates a UTM:

• α q f of type "state" • α s f of type "symbol"
The BR program to simulate a UTM is then written in a compact form:

R 1 : if (q, T (p), act, α q f , α s f ) ∈ R then q ← α q f T ← (T \ {(p, T (p))}) ∪ {(p, α s f )}
αp ← ("position", p ± 1)(Depending on the value of act) α l ← ("length", l ± 1)(Depending on the respective values of act, p and l)

R 2 : if (q ∈ Ter) then Stop; FIGURE 2. A UTM written in the BR language.
The UTM in Fig. 2 terminates correctly for any valid input (T, x) where T is a TM and x is its input. We have made simplifications for the sake of clarity: R 1 should clearly be at least three different rules each replacing act with one of {"left", "right", "stay"}, and its complete formally correct form would in fact have two more rules, to be able to increase the length of the tape as needed (using the variable s b as necessary).

PAC-UNLEARNABILITY

Because BRs are Turing-complete, as shown in Sect. 3, their computability is undecidable. We now introduce the main feature concerning the BRAG problem: the parameters. Suppose BRs have tuning parameters, such as the threshold for α 1 in R 1 from Fig. 1. A common goal of BR users is to achieve an average result, such as having an average number of manually treated loan requests for a BR modeling a loan application process. This begs the following question: is there an algorithm for deciding the values of the parameters of a BR program in such a way that it statistically behaves according to a given target? As BR programs are Turing-complete, we know that this algorithm cannot exist in the most general terms, since BR programs might not even terminate in finite time.

We now look at those BR programs which do terminate. The question can be considered as a learnability problem. Does there exist an algorithm A that efficiently "learns" p, given as input: (a) a class P p of terminating BR programs parametrized over p, (b) a data distribution D over its input domain X and (c) a goal g for the value of the average output E D (P p )? We prove that the answer is still negative.

Basics of computational learning theory

The first thing to establish is the exact meaning of the word "learns", used informally above. Describing ML algorithms and their applicability to different problems is the concern of computational learning theory. There exist several approaches to this task, which can be broadly divided in two: those that specify that a successful learning algorithm must learn an unknown function f exactly from data observation, and those that accept learning an approximation of f . We focus on the second category, and, among the several abstract models of learning, we look at the well-established Probably Approximately Correct (PAC) framework [START_REF] Valiant | A theory of the learnable[END_REF].

A PAC learning algorithm aims at identifying a concept (i.e. a function X → {0, 1}) in a concept class C (i.e. a family of concepts). For a concept f ∈ C and a list S of data points in X of length λ, an algorithm A is an ( , δ)-PAC learning algorithm for C if for all sufficiently large λ it outputs a function h such that:

P[h is an -approximation of f ] 1 -δ.
We note that A has access to an oracle for f . Moreover:

• A is said to be efficient if the time complexity of A and h are polynomial in 1/ , 1/δ and λ;

• A is said to weakly learn C if there exist some polynomials p (λ); p δ (λ) for which 1 2 -1 p (λ) and δ 1 -1 p δ (λ) . • We say a concept class is PAC learnable if it is both efficiently and weakly learnable. Otherwise, it is unlearnable.

The question is now whether the BRAG is PAC learnable, i.e. whether the correct parametrizations of arbitrary BR programs leading to good control of the average can be learned weakly and efficiently. We shall prove that the answer is negative in the general case. Within the same notation and context, another question that arises is whether there even exists an algorithm which learns p with < 1 2 and δ < 1. Again, the answer is negative in the general case. The learning problem has been looked at within the context of other Turing-complete languages. Algorithms for learning some restricted classes of programs exist for inductive logic programming [START_REF] Blockeel | Top-down induction of first-order logical decision trees[END_REF] or nonmonotonic inductive logic programming (De Raedt and Džeroski, 1994). Here, similarly to [START_REF] Wang | The learnability of business rules[END_REF], we wish to examine the general case of learning in all terminating programs.

Pseudorandom Functions

Pseudorandom functions (PRF), introduced by Goldreich, Goldwasser and Micali [START_REF] Goldreich | How to construct random functions[END_REF], are indexed families of functions F p for which there exists a polynomial time algorithm to evaluate F p (x), but no probabilistic polynomial time algorithm can distinguish the function from a truly random function F rand without knowing p, even if allowed access to an oracle.

It is known that PRF are unlearnable using PAC algorithms [START_REF] Goldreich | How to construct random functions[END_REF][START_REF] Cohen | Aggregate pseudorandom functions and connections to learning[END_REF]. This allows us to prove that the general class of terminating BR programs is not PAC-learnable (i.e. that no PAC algorithm can learn the concept weakly and efficiently). We will then use a known chaotic map, the logistic map (defined by f n+1 (x) = af n (x)(1 -f n (x)) with 0 a 4), to look at learnability in a stronger sense, and prove that BR programs cannot be learned by PAC learning algorithms at all, in full generality.

In the rest of this section, we consider F p to be a PRF, and denote by Eval p,x (F p (x)) the complexity of evaluating F p (x).

Weak unlearnability

We call (P p ) p∈π a class of terminating BR programs indexed by p, S a list of items from the input domain X with |S| = λ, and g a goal for the value of the average output E S (P p ). We consider C to be the concept class whose members are f : (P p ) p∈π → {0, 1}.

Next, we prove that there is no practically viable algorithm that can learn a BR program out of a class of BR programs in the general case, even with access to a perfect oracle. This is a consequence of both the Turing-completeness of BR programs and the unlearnability of PRF.

Proposition 2: The concept h ∈ C defined as h(p) = 1 iff E S (P p ) = g cannot be learned using a PAC learning algorithm in the general case.

Proof. As BR programs are Turing-complete, we let the family (P p ) p∈π to consist of PRFs. Any algorithm which learns C also learns (1 f (p)) p ⊂ C, where 1 f (p) = 1 iff P p = f . Learning the latter is trivially the same as learning a PRF, which is impossible by [START_REF] Cohen | Aggregate pseudorandom functions and connections to learning[END_REF].

Corollary 2: The concept class C is unlearnable.

Hence, it is impossible to provide a single algorithm that is able to adjust the average behavior of BR programs according to a predefined goal.

Corollary 3: The BRAG is PAC-unlearnable.

Complete Unlearnability

We have used the fact that PRFs are not PAC learnable in the sense that no PAC algorithm can efficiently and weakly learn a PRF. We now demonstrate an example of a concept class that cannot be learned by PAC algorithms at all (i.e. not just because the "weakly" and "efficiently" qualifiers do not apply). This example is based on the intuition that chaos cannot be predicted, and so it cannot be learned.

We use the logistic map, as a known chaotic map. We note f n+1 (x) = af n (x)(1f n (x)), f 0 (x) = x and choose the parameter a = 4. We call C n (x) the concept class such that C n (x) = 1 iff f n (x) 0.5 and C x (n) = 0 otherwise, where x ∈ [0, 1] follows the arcsine distribution, i.e. the probability density function is p

(x) = 1 π √ x(1-x)
, and with n ∈ N following the uniform distribution.

Theorem 3: The concept class C n (x) cannot be learned with any accuracy. To be precise, for all algorithms A calling the oracle C n (x) a finite number of times, we have:

P n∈N (P x∈X (A(C n )(x) = C n (x)) = 0.5) = 1.
Proof. The proof relies heavily on properties of the logistic map proved by Berliner [START_REF] Berliner | Statistics, probability and chaos[END_REF]. From it, we know that as the logistic map is chaotic, each sequence (f n (x)) n is either eventually periodic or is dense in [0, 1]. We also know that as X follows the arcsine distribution, the C n (X) are independent identically distributed Bernoulli random variables, such that P x∈X (C n (x) = 1) = 0.5.

Suppose A calls C n (x) for values of x ∈ {x 1 , . . . , x k }. We call n 0 the value such that A(C n ) = C n 0 . As P x∈X (C n 0 (x) = 1) = 0.5 does not depend on n 0 , and the C n (X) are i.i.d., we have

P x∈X (C n 0 (x) = C n (x)) = 0.5 iff n 0 = n and P x∈X (C n 0 (x) = C n (x)) = 0
otherwise. The theorem is thus the same as saying that A almost certainly (in the probabilistic sense) cannot match n 0 to the exact value of n. We now prove that there almost always exists

n 1 = n which is indistinguishable from n by A, i.e. C n 1 (x 1 ) = C n (x 1 ), . . . , C n 1 (x k ) = C n (x k ). Let us call Y 1 i = C i (x 1 ), . . . , Y k i = C i (x l ) with i ∈ N.
Some of the sequences Y j are periodic after some rank, and some are not. Without loss of generality, we assume Y 1 , . . . , Y k 1 are periodic, and Y k 1 +1 , . . . , Y k are not. Notice that, almost certainly, (Y 1 ) i n , . . . , (Y k 1 ) i n are periodic (for n large enough). Using P ∈ N to denote the smaller common multiple of the periods of those sequences, we also note that

C n+P i (x 1 ) = C n (x 1 ), . . . , C n+P i (x k 1 ) = C n (x k 1 )
, and that y i = n + P i.

As the sequences Y k 1 +1 , . . . , Y k are not periodic, we know that each sequence

(f n (x k 1 +1 )) n , . . . , (f n (x k )) n is dense in [0, 1].
Consequently, for any sequence of k -k 1 bits, there exists a countable number of n 1 ∈ (Y i ) i∈N such that it is equal to Y k 1 +1 , . . . , Y k . In particular, if this sequence is C n (x k 1 +1 ), . . . , C n (x k ), any of those n 1 different from n proves the theorem.

Thm. 3 is a theoretical result: no practical application is ever likely to require the learning this type of concept class. Chaotic behaviour, however, is exhibited by many practical algorithms, so that results of this type (rather than this result) might have practical relevance. On the other hand, a key part of the proof is allowing the concept class to be infinite and indexed by an unbounded natural number. This is unlikely to happen in industrial settings. Another difficulty is representing and computing with real numbers, which can be done using Real RAM machines [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines[END_REF]. In the case of the logistic map with parameter a = 4, the task is made slightly easier by the existence of an exact solution, but other chaotic maps would require expensive recursive computations. The existence of such extreme cases of unlearnability is nevertheless something to be careful of: unlikely does not mean impossible.

OPERATIONAL SEMANTICS APPLICATION

While a non-constructive proof of the Turing-completeness of BR programs is trivial, our constructive proof shows how easy it is to transition from BR programs to a more standard programming language. Indeed, we only need to construct a canonical WHILE form of BR programs to apply known operational semantics methods to BR programs, such as the standard Structural Operational Semantics (SOS) described by Plotkin in [START_REF] Plotkin | A structural approach to operational semantics[END_REF].

Current operational semantics for BR mostly follow the structural approach introduced in that work in that they use small-step semantics. The standard semantics defined in W3C's Production Rule Dialect of the Rule Interchange Format (RIF-PRD) (de Sainte [START_REF] De Sainte | Rif production rule dialect[END_REF] is mostly used to specify different variants of BR interpreters. Other attempts at creating operational semantics for BRs have focused on being compatible with either declarative semantics or ontologies (or both) [START_REF] Rezk | Formalizing production systems with rule-based ontologies[END_REF][START_REF] Zaniolo | A unified semantics for active and deductive databases[END_REF]. Such semantics keep the structure of the BR program divided into rules, which helps with making sense of complex BR programs and creating better user experiences. On the other hand, existing BR semantics are not suitable for proofs. We can use WHILE programs to obtain a SOS interpretation that is not unique to a syntax or execution algorithm. As shown in the rest of this section, using this semantics can help in proving properties of rule programs such as termination [START_REF] Cousot | Semantic foundations of program analysis[END_REF].

WHILE form of BR programs

A canonical WHILE program equivalent to a BR program is easy to establish using the execution algorithm we consider. The main idea is to introduce an additional integer variable x 0 to serve as a control variable, and to write each rule instance explicitly in the WHILE program itself. The Fig. 5 shows the WHILE form of the example in Fig. 1. Note that our construction provides a "reverse translator" to the one used in Sect. 3.3.

For an ordered set of BRs R 1 , . . . , R m with conditions T 1 , . . . , T m and actions A 1 , . . . , A m , and a set of variables x 1 , . . . , x n , the WHILE program equivalent to the BR program with the above-mentioned execution mode is written as in Fig. 3. It uses a single additional integer variable x 0 . Line 4 in the pseudocode of Fig. 3 An interesting side note is that other BR program interpreters do not forbid the canonical conversion of a BR program to a WHILE program. While the specifics depend on each

The typed Variables (in order) int x ← 1 int age ← 90

The WHILE program 1: x 0 ← -1 2: while x 0 = 0 do 3:

if x 0 = -1 then 4:
if age 1∧x= 2 then 5:

x 0 ← 1 6:

else if x = 1 then 7:

x 0 ← 2 8:
else if age 60 then 9:

x 0 ← 3 10: 1 execution algorithm, we can remember the three most common elements found in such algorithms from Section 2.2:

• Refraction results in the use of an additional boolean variable per rule instance in the WHILE program.

• Priority partially decides the order of the if-then-else of the WHILE program.

• Recency is the most complicated. An easy workaround would add an incremental integer variable per rule instance in the WHILE program and use a max() function in the tests of the if-then-else.

A structural operational semantics

Let us consider the SOS described by Plotkin in [START_REF] Plotkin | A structural approach to operational semantics[END_REF] applied to WHILE programs. It describes the execution of a program as a finite automaton, with each simple command corresponding to a state transition relation. Its usefulness in proving properties of programs, such as sets of input resulting in termination or non-termination, has been established [START_REF] Burstall | Proving properties of programs by structural induction[END_REF]. Fig. 6 shows the state transition relations corresponding to the WHILE language under an easily readable form, using an Inference Rule syntax wherein the premises are listed above a horizontal line, the conclusion below, and the condition, if present, to its right.

We use an example to demonstrate that such a transformation of a BR program into a WHILE program can be used to prove properties of BR programs through those same SOS methods. Consider the simple example of a loan request application with three integer variables: amount, duration and income. We use the naive rule described in Fig. 7. The input value of amount is the requested loan value, while its final value is the total repaid sum.

We provide a proof-of-concept implementation of our SOS, and perform a few computational experiments on the issue of termination of BR programs. Obviously, since we now know that the BR language is Turing-complete, we do not mean that our SOS is able to systematically predict termination correctly. We simply mean to say that we test our SOS on a few given BR programs.

We use Prolog [START_REF] Clocksin | Programming in Prolog[END_REF] to code the SOS of the WHILE programming language as rules in a rule inference engine using the form displayed in Fig. 6. Similar rules encode the evaluation of Boolean and Numerical variables. We then encode the WHILE FIGURE 6. The inference rules encoding the operational semantics of commands in WHILE, starting from a state s of the machine's memory

The Rule R:

if (amount income • duration) then(amount ← 1.1 amount, duration ← duration + 1)

The WHILE program 1: x 0 ← -1 2: while x 0 = 0 do 3:

if x 0 = -1 then 4:
if amount income • duration then 5:

x 0 ← 1 6: else 7:

x 0 ← 0 8:

end if

9:

else if x 0 = 1 then 10:

amount ← 1.1 amount 11:

duration ← duration + 1

12:

x 0 ← -1 13: else 14:

x 0 ← 0 15:

end if

16: end while

The Prolog encoding We use the variables X = amount × 10 i and Y = income × 10 i where i is the number of times the rule executes.

1: C = seq(C1,C2) 2: C1 = assign('X0',-1) 3: C2 = whiledo(neq('X0',0),C3) 4: C3 = ifthenelse(eq('X0',-1),C4,C5) 5: C4 = ifthenelse(geq('X',mult('Y','Dur')), assign('X0',1),assign('X0',0))

6: C5 = ifthenelse(eq('X0',1),seq(seq(seq( assign('Dur',add('Dur',1)), assign('X',mult('X',11))), assign('Y',mult('Y',10))), assign('X0',-1)), assign('X0',0)) FIGURE 7. A naive BR program for Loan Applications program itself as a series of rules in Prolog1 . It is then a simple matter to ask Prolog about the termination of this program by simply asking about the truth value of assertions including 'X0 f in ' = 0 and constraint over the inputs.

Proving Termination

Termination of a program for a given input is one of the easiest properties of programs to look into using SOS. Because of the Turing completeness of the BR language, our methodology for proving (or disproving) termination will obviously not work on every BR program. We proceed as follows: given a BR program, we tranform it into its WHILE form, which we then use to derive the SOS. We implement the SOS as a set of constraints in two Prolog dialects (SWI-Prolog [START_REF] Wielemaker | SWI-Prolog[END_REF] and XSB Prolog [START_REF] Sagonas | XSB as an efficient deductive database engine[END_REF]), so as to use the corresponding interpreter to try and establish feasibility or infeasibility of the constraint set.

We coded the WHILE programs for three examples in Prolog. We first used SWI-Prolog to test termination for an interval range of inputs by using a Prolog query containing the input and the specific output x 0 = 0 (i.e. the WHILE loop ends). The results for the program in Fig. 7 show some of the advantages and limits of using basic Prolog. For some intervals of values for amount, we can prove in a few seconds of CPU time that for duration = 5 and income = 10, the BR program always terminates. On the other hand, we are unable to prove non-termination using SWI-Prolog as it lacks loop detection algorithms. We then used the tabling included in XSB-Prolog [START_REF] Swift | XSB: Extending prolog with tabled logic programming[END_REF] to test non-termination. We observe that we can now detect non-terminating inputs, however given an interval we can only detect the absence of a terminating input, i.e. we cannot distinguish between a set of input that all terminate and another where only some values lead to termination. Furthermore, the results for the program in Fig. 9 show that even then, not all inputs can be determined to be terminating or non-terminating (this is expected as the halting problem is undecidable). We remark, however, that the most useful contribution of an SOS is to prove termination of programs (rather than non-termination), making even the basic Prolog application important. Amongst its many advantages, our semantics can be used for automatic validation of a BR program, for example. A search algorithm could also be used to identify the cutoff point of amount 62 as containing every terminating input, if one were to take the monotonicity of the program into account.

Along with the example from Fig. 7, a slightly more realistic example is seen in Fig. 8, adding the boolean variable approval and the integer variable age to the BR program. On the other hand, Fig. 9 is a less trivial example: a BR program that chooses the interest rate interest depending on the credit score score using a made-up algorithm which simulates the logistic map, where score ∈ [300,850].

The results for the examples in Fig. 7 and Fig. 8 are displayed in Fig. 1, while the results for the example in Fig. 9 are in Fig. 2. Fig. 1 is indicative of a practical use of studying the termination of BR programs this way: a bank might wish to check that their loan application BR program terminates for a given range of values. Studying unexpected failures can point out a missing rule or variable in the BR program.

On the other hand, the results from Fig. 2 are somewhat more difficult to interpret. While the BR program in Fig. 9 is somewhat contrived, it shows that some failures can be not only unexpected, but unpredictable. The SWI-Prolog ERROR: Out of local stack looks like yet another inconclusive answer, but tracing the execution of the Prolog interpreter shows that some errors are the result of infinitely repeated goals, and a simple alteration to the Prolog interpreter can detect most infinite recursion loops of that kind [START_REF] Van Gelder | Efficient loop detection in prolog using the tortoise-and-hare technique[END_REF]. This is proved by looking at the result of the tabling-enabled XSB-Prolog execution, which gives us proof of non-termination for the input r = 3.82843 (score = 813.541375). Such non-terminating inputs might be found by looking at the internal states of a classic BR engine, but the automation provided by existing research on SOS and Prolog remains valuable and time-saving. On the other hand, some values have a convergent but non-periodic behavior which we cannot detect using either of our implementations. The tested input r = 3 (score = 637.5) has such a behavior. The Prolog algorithm actually simulates the fixed The WHILE program 1: x 0 ← -1 2: while x 0 = 0 do 3:

if x 0 = -1 then

4:

if approval = True ∧ age < 18 then 5:

x 0 ← 1 6:

else if approval = True ∧ duration > 10 then 7:

x 0 ← 2 8:

else if approval = True ∧ amount income • duration then 9:

x 0 ← 3 10:

else 11:

x 0 ← 0 12:

end if

13:

else if x 0 = 1 then 14:

approval ← False 15:

x 0 ← -1 16:

else if x 0 = 2 then 17:

approval ← False 18:

x 0 ← -1

19:

else if x 0 = 3 then 20:

amount ← 1.1 amount

21:

duration ← duration + 1

22:

x 0 ← -1

23:

else 24:

x 0 ← 0

25:

end if 26: end while The WHILE program 1: x 0 ← -1 2: while x 0 = 0 do 3:

if x 0 = -1 then 4:
if n 1000 then 5:

x 0 ← 1 6:

else if x 0.51 then 7:

x 0 ← 2 8:

else if x 0.49 then 9:

x 0 ← 3 10:

else 11:

x 0 ← 0 12:

end if

13:

else if x 0 = 1 then 14:

x ← r • x(1 -x)

15:

n ← n + 1 16:

x 0 ← -1

17:

else if x 0 = 2 then 18:

x ← r • x(1 -x)

19:

x 0 ← -1 20:

else if x 0 = 3 then 21:

x ← r • x(1 -x)

22:

x 0 ← -1

23:

else 24:

x 0 ← 0

25:

end if 26: end while [1.41, 3.57], i.e. score∈ [300, 758], the higher values fall within the chaotic part of the logistic map. In particular, some specific values have a periodic behavior, such as the tested r = 3.82843 (score = 813.541375). The use of SOS derived from the WHILE form of BR programs helps in this and similar cases by automatically identifying with certainty some non-terminating inputs, assuming Prolog is configured to identify infinite recursive goals.

ming language [START_REF] Wang | Analytics learning for rule-based systems[END_REF]. The Turing-completeness of BR programs using any looping interpreter is important to theoretical research into the properties of BRs.

We also proved the PAC-unlearnability of the concept class of BR programs. That proof is stronger than the usual PAC-learnability approach as the example of the logistic map shows that some BR programs are completely PAC-unlearnable regardless of how inefficient the learning algorithm is. This showcases how complex and nontrivial BR programs are. This invites future research into learning BR programs with statistical objectives as it may well be possible to achieve our stated purpose for less general, but still useful classes of BR programs. That is a problem that industrial BR systems would be very interested in. In (Wang and Liberti, 2017) we look at discrete distributions, for example, but many other possibilities exist.

The theoretical limits discussed in this paper do not imply that the BRAG problem is hopeless, but only that more research is needed in order to delimit a reasonable class of BRAG instances for which the BRAG can be solved, see e.g. (Wang et al., 2017).

The constructive proof we used to prove the Turing-completeness of BRs allows us to introduce the WHILE forms of BR programs. WHILE programs are simple programming languages that are easily linked to others, and can already provide some insight on their own. Using SOS analysis techniques on the transformed BR programs highlights a marked difference with the existing operational semantics of BRs. These might inspire new techniques for studying the properties of BR programs. In particular, the study of which inputs or sets of input allow for the termination or non-termination of BR programs is made more practical by the use of this standardized operational semantics.

FIGURE 3 .

 3 FIGURE 3. Universal WHILE translation of BR programs. we have separated for the sake of readability, see Fig. 4. 1: if T1(x1, . . . , xn) = True then 2: x0 ← 1 3: else if T2(x1, . . . , xn) = True then 4: . . . 5: else if Tm(x1, . . . , xn) = True then 6: x0 ← m 7: else 8: x0 ← 0 9: end if

FIGURE 4 .

 4 FIGURE 4. Code corresponding to line 4 in Fig. 3.

FIGURE 5 .

 5 FIGURE 5. Example: WHILE form of the BR program in Fig. 1

FIGURE 8 .

 8 FIGURE 8. A more realistic BR program for Loan Applications, the input should always have approval = True

FIGURE 9 .

 9 FIGURE 9. A nontrivial BR program and corresponding WHILE program, the input should always have n = 1

Notably, we use the variables X = Amount × 10 i and Y = income × 10 i where i is the number of times the rule executes, so as to benefit from SWI-Prolog's CLP(FD) library(Triska,

2014) and XSB-Prolog's bounds library.

Acknowledgments

The first author (OW) is supported by an IBM France/ANRT CIFRE Ph.D. thesis award.

Supposing C are commands, E are expressions and s are memory states, the following inference rules encode the operational semantics of the commands of the WHILE language. The assignment command:

The sequential composition command:

The if command:

The while command: Business Rules form an unexpectedly expressive programming language compared to their practical use in business. While BR programs are syntactically very simple, the language contains hidden complexity in the details of its interpreters. In particular, any interpreter that uses a looping algorithm can make the set of all BR programs Turing-complete. We hope that our formalization will open the doors to further research into BR as a program-