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))

***** No progress could be made on DP problem D1 = (P1, R UNION R_?, i, c).