YES

Problem:
 half(0()) -> 0()
 half(s(0())) -> 0()
 half(s(s(x))) -> s(half(x))
 lastbit(0()) -> 0()
 lastbit(s(0())) -> s(0())
 lastbit(s(s(x))) -> lastbit(x)
 zero(0()) -> true()
 zero(s(x)) -> false()
 conv(x) -> conviter(x,cons(0(),nil()))
 conviter(x,l) -> if(zero(x),x,l)
 if(true(),x,l) -> l
 if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))

Proof:
 DP Processor:
  DPs:
   half#(s(s(x))) -> half#(x)
   lastbit#(s(s(x))) -> lastbit#(x)
   conv#(x) -> conviter#(x,cons(0(),nil()))
   conviter#(x,l) -> zero#(x)
   conviter#(x,l) -> if#(zero(x),x,l)
   if#(false(),x,l) -> lastbit#(x)
   if#(false(),x,l) -> half#(x)
   if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
  TRS:
   half(0()) -> 0()
   half(s(0())) -> 0()
   half(s(s(x))) -> s(half(x))
   lastbit(0()) -> 0()
   lastbit(s(0())) -> s(0())
   lastbit(s(s(x))) -> lastbit(x)
   zero(0()) -> true()
   zero(s(x)) -> false()
   conv(x) -> conviter(x,cons(0(),nil()))
   conviter(x,l) -> if(zero(x),x,l)
   if(true(),x,l) -> l
   if(false(),x,l) -> conviter(half(x),cons(lastbit(x),l))
  Usable Rule Processor:
   DPs:
    half#(s(s(x))) -> half#(x)
    lastbit#(s(s(x))) -> lastbit#(x)
    conv#(x) -> conviter#(x,cons(0(),nil()))
    conviter#(x,l) -> zero#(x)
    conviter#(x,l) -> if#(zero(x),x,l)
    if#(false(),x,l) -> lastbit#(x)
    if#(false(),x,l) -> half#(x)
    if#(false(),x,l) -> conviter#(half(x),cons(lastbit(x),l))
   TRS:
    zero(0()) -> true()
    zero(s(x)) -> false()
    lastbit(0()) -> 0()
    lastbit(s(0())) -> s(0())
    lastbit(s(s(x))) -> lastbit(x)
    half(0()) -> 0()
    half(s(0())) -> 0()
    half(s(s(x))) -> s(half(x))
   Arctic Interpretation Processor:
    dimension: 1
    usable rules:
     zero(0()) -> true()
     zero(s(x)) -> false()
     half(0()) -> 0()
     half(s(0())) -> 0()
     half(s(s(x))) -> s(half(x))
    interpretation:
     [if#](x0, x1, x2) = -4x0 + -1x1 + 0,
     
     [conviter#](x0, x1) = x0 + 1,
     
     [conv#](x0) = 2x0 + 12,
     
     [zero#](x0) = 0,
     
     [lastbit#](x0) = -2x0 + 0,
     
     [half#](x0) = -4x0 + 0,
     
     [cons](x0, x1) = x0 + x1 + -16,
     
     [nil] = 2,
     
     [false] = 6,
     
     [true] = 1,
     
     [zero](x0) = 3x0 + 4,
     
     [lastbit](x0) = -4x0 + 0,
     
     [s](x0) = 3x0 + 4,
     
     [half](x0) = -2x0 + 1,
     
     [0] = 0
    orientation:
     half#(s(s(x))) = 2x + 3 >= -4x + 0 = half#(x)
     
     lastbit#(s(s(x))) = 4x + 5 >= -2x + 0 = lastbit#(x)
     
     conv#(x) = 2x + 12 >= x + 1 = conviter#(x,cons(0(),nil()))
     
     conviter#(x,l) = x + 1 >= 0 = zero#(x)
     
     conviter#(x,l) = x + 1 >= -1x + 0 = if#(zero(x),x,l)
     
     if#(false(),x,l) = -1x + 2 >= -2x + 0 = lastbit#(x)
     
     if#(false(),x,l) = -1x + 2 >= -4x + 0 = half#(x)
     
     if#(false(),x,l) = -1x + 2 >= -2x + 1 = conviter#(half(x),cons(lastbit(x),l))
     
     zero(0()) = 4 >= 1 = true()
     
     zero(s(x)) = 6x + 7 >= 6 = false()
     
     lastbit(0()) = 0 >= 0 = 0()
     
     lastbit(s(0())) = 0 >= 4 = s(0())
     
     lastbit(s(s(x))) = 2x + 3 >= -4x + 0 = lastbit(x)
     
     half(0()) = 1 >= 0 = 0()
     
     half(s(0())) = 2 >= 0 = 0()
     
     half(s(s(x))) = 4x + 5 >= 1x + 4 = s(half(x))
    problem:
     DPs:
      
     TRS:
      zero(0()) -> true()
      zero(s(x)) -> false()
      lastbit(0()) -> 0()
      lastbit(s(0())) -> s(0())
      lastbit(s(s(x))) -> lastbit(x)
      half(0()) -> 0()
      half(s(0())) -> 0()
      half(s(s(x))) -> s(half(x))
    Qed