YES

Problem:
 0(*(x1)) -> *(1(x1))
 1(*(x1)) -> 0(#(x1))
 #(0(x1)) -> 0(#(x1))
 #(1(x1)) -> 1(#(x1))
 #($(x1)) -> *($(x1))
 #(#(x1)) -> #(x1)
 #(*(x1)) -> *(x1)

Proof:
 KBO Processor:
  weight function:
   w0 = 1
   w(#) = w(1) = w(0) = w(*) = 1
   w($) = 0
  precedence:
   $ > # > 1 > 0 > *
  problem:
   
  Qed