We consider universal computability of the STRS with no additional rule schemes:

  Signature: fapp  :: o -> o -> o
             lam   :: o -> o
             subst :: o -> o -> o
             v     :: o

  Rules: fapp(lam(X), Y) -> subst(X, Y)
         subst(v, Y) -> Y
         subst(lam(X), Y) -> lam(X)
         subst(fapp(X, Z), Y) -> fapp(subst(X, Y), subst(Z, Y))

The system is accessible function passing by a sort ordering that equates all sorts.

We start by computing the initial DP problem D1 = (P1, R UNION R_?, i, c), where:

  P1. (1) fapp#(lam(X), Y) => subst#(X, Y)
      (2) subst#(fapp(X, Z), Y) => subst#(X, Y)
      (3) subst#(fapp(X, Z), Y) => subst#(Z, Y)
      (4) subst#(fapp(X, Z), Y) => fapp#(subst(X, Y), subst(Z, Y))

***** We apply the Usable Rules Processor on D1 = (P1, R UNION R_?, i, c).

All known rules are usable, but the Usable Rules method is applicable so the extra rules are not usable, and may be dropped.

Processor output: { D2 = (P1, R, i, c) }.

***** No progress could be made on DP problem D2 = (P1, R, i, c).