We consider universal computability of the LCTRS with only rule scheme Calc:

  Signature: cons   :: Int -> o -> o
             filter :: Int -> o -> o
             if     :: Bool -> Int -> Int -> o -> o
             isdiv  :: Int -> Int -> Bool
             nats   :: Int -> Int -> o
             nil    :: o
             primes :: Int -> o
             sieve  :: o -> o

  Rules: primes(x) -> sieve(nats(2, x)) | x = x
         nats(x, y) -> nil | x > y
         nats(x, y) -> cons(x, nats(x + 1, y)) | y >= x
         sieve(nil) -> nil
         sieve(cons(x, ys)) -> cons(x, sieve(filter(x, ys))) | x = x
         filter(x, nil) -> nil | x = x
         filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) | x = x /\ y = y
         if(true, x, y, zs) -> filter(x, zs) | x = x /\ y = y
         if(false, x, y, zs) -> cons(y, filter(x, zs)) | x = x /\ y = y
         isdiv(x, 0) -> true | x > 0
         isdiv(x, y) -> false | x > y /\ y > 0
         isdiv(x, y) -> isdiv(x, y - x) | y >= x /\ x > 0

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)  primes#(x) => nats#(2, x) | x = x
      (2)  primes#(x) => sieve#(nats(2, x)) | x = x
      (3)  nats#(x, y) => nats#(x + 1, y) | y >= x
      (4)  sieve#(cons(x, ys)) => filter#(x, ys) | x = x
      (5)  sieve#(cons(x, ys)) => sieve#(filter(x, ys)) | x = x
      (6)  filter#(x, cons(y, zs)) => isdiv#(x, y) | x = x /\ y = y
      (7)  filter#(x, cons(y, zs)) => if#(isdiv(x, y), x, y, zs) | x = x /\ y = y
      (8)  if#(true, x, y, zs) => filter#(x, zs) | x = x /\ y = y
      (9)  if#(false, x, y, zs) => filter#(x, zs) | x = x /\ y = y
      (10) isdiv#(x, y) => isdiv#(x, y - x) | y >= x /\ x > 0

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

We compute a graph approximation with the following edges:

  1:  3 
  2:  4 5 
  3:  3 
  4:  6 7 
  5:  4 5 
  6:  10 
  7:  8 9 
  8:  6 7 
  9:  6 7 
  10: 10 

There are 4 SCCs.

Processor output: { D2 = (P2, R UNION R_?, i, c) ; D3 = (P3, R UNION R_?, i, c) ; D4 = (P4, R UNION R_?, i, c) ; D5 = (P5, R UNION R_?, i, c) }, where:

  P2. (1) nats#(x, y) => nats#(x + 1, y) | y >= x

  P3. (1) isdiv#(x, y) => isdiv#(x, y - x) | y >= x /\ x > 0

  P4. (1) filter#(x, cons(y, zs)) => if#(isdiv(x, y), x, y, zs) | x = x /\ y = y
      (2) if#(true, x, y, zs) => filter#(x, zs) | x = x /\ y = y
      (3) if#(false, x, y, zs) => filter#(x, zs) | x = x /\ y = y

  P5. (1) sieve#(cons(x, ys)) => sieve#(filter(x, ys)) | x = x

***** We apply the Integer Function Processor on D2 = (P2, R UNION R_?, i, c).

We use the following integer mapping:

  J(nats#) = arg_2 - arg_1

We thus have:

  (1) y >= x |= y - x > y - (x + 1) (and y - x >= 0)

All DPs are strictly oriented, and may be removed.  Hence, this DP problem is finite.

Processor output: { }.

***** We apply the Integer Function Processor on D3 = (P3, R UNION R_?, i, c).

We use the following integer mapping:

  J(isdiv#) = arg_2

We thus have:

  (1) y >= x /\ x > 0 |= y > y - x (and y >= 0)

All DPs are strictly oriented, and may be removed.  Hence, this DP problem is finite.

Processor output: { }.

***** We apply the Subterm Criterion Processor on D4 = (P4, R UNION R_?, i, c).

We use the following projection function:

  nu(filter#) = 2
  nu(if#)     = 4

We thus have:

  (1) cons(y, zs) |>|  zs
  (2) zs          |>=| zs
  (3) zs          |>=| zs

We may remove the strictly oriented DPs.

Processor output: { D6 = (P6, R UNION R_?, i, c) }, where:

  P6. (1) if#(true, x, y, zs) => filter#(x, zs) | x = x /\ y = y
      (2) if#(false, x, y, zs) => filter#(x, zs) | x = x /\ y = y

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

We obtain 7 usable rules (out of 12 rules in the input problem).

Processor output: { D7 = (P5, R2, i, c) }, where:

  R2. (1) filter(x, nil) -> nil | x = x
      (2) filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) | x = x /\ y = y
      (3) if(true, x, y, zs) -> filter(x, zs) | x = x /\ y = y
      (4) if(false, x, y, zs) -> cons(y, filter(x, zs)) | x = x /\ y = y
      (5) isdiv(x, 0) -> true | x > 0
      (6) isdiv(x, y) -> false | x > y /\ y > 0
      (7) isdiv(x, y) -> isdiv(x, y - x) | y >= x /\ x > 0

***** We apply the Graph Processor on D6 = (P6, R UNION R_?, i, c).

We compute a graph approximation with the following edges:

  1:
  2:

As there are no SCCs, this DP problem is removed.

Processor output: { }.

***** No progress could be made on DP problem D7 = (P5, R2, i, c).