YES
Input TRS:
      1: half(0()) -> 0()
      2: half(s(0())) -> 0()
      3: half(s(s(x))) -> s(half(x))
      4: lastbit(0()) -> 0()
      5: lastbit(s(0())) -> s(0())
      6: lastbit(s(s(x))) -> lastbit(x)
      7: conv(0()) -> cons(nil(),0())
      8: conv(s(x)) -> cons(conv(half(s(x))),lastbit(s(x)))
      9: rand(x) ->= x
      10: rand(x) ->= rand(s(x))
Number of strict rules: 8
Direct POLO(bPol) ... failed.
Uncurrying lastbit half
      1: half^1_0() -> 0()
      2: half^1_s(0()) -> 0()
      3: half^1_s(s(x)) -> s(half(x))
      4: lastbit^1_0() -> 0()
      5: lastbit^1_s(0()) -> s(0())
      6: lastbit^1_s(s(x)) -> lastbit(x)
      7: conv(0()) -> cons(nil(),0())
      8: conv(s(x)) -> cons(conv(half^1_s(x)),lastbit^1_s(x))
      9: rand(x) ->= x
      10: rand(x) ->= rand(s(x))
      11: half(0()) ->= half^1_0()
      12: half(s(_1)) ->= half^1_s(_1)
      13: lastbit(0()) ->= lastbit^1_0()
      14: lastbit(s(_1)) ->= lastbit^1_s(_1)
Number of strict rules: 8
Direct POLO(bPol) ... failed.
Dependency Pairs:
     #1: #lastbit^1_s(s(x)) -> #lastbit(x)
     #2: #lastbit(0()) ->? #lastbit^1_0()
     #3: #half(0()) ->? #half^1_0()
     #4: #half(s(_1)) ->? #half^1_s(_1)
     #5: #lastbit(s(_1)) ->? #lastbit^1_s(_1)
     #6: #half^1_s(s(x)) -> #half(x)
     #7: #conv(s(x)) -> #conv(half^1_s(x))
     #8: #conv(s(x)) -> #half^1_s(x)
     #9: #conv(s(x)) -> #lastbit^1_s(x)
Number of SCCs: 3, DPs: 5
  SCC { #7 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded.
      conv	s: []	p: 2	w: 11802
      s 	s: [1]	p: 0	w: x1
      lastbit^1_s	s: []	p: 3	w: 3
      #conv	s: [1]	p: 0	w: x1 + 1
      #lastbit^1_0	s: []	p: 0	w: 0
      #half	s: []	p: 0	w: 1
      #lastbit	s: 1
      half^1_s	s: 1
      rand	s: []	p: 0	w: x1 + 1
      half	s: 1
      lastbit	s: []	p: 3	w: 3
      0 	s: []	p: 4	w: 1
      nil	s: []	p: 1	w: 11802
      #half^1_s	s: []	p: 0	w: 1
      half^1_0	s: []	p: 4	w: 1
      #lastbit^1_s	s: []	p: 0	w: 1
      cons	s: [2]	p: 1	w: max(x1, x2 + 1)
      #half^1_0	s: []	p: 0	w: 0
      lastbit^1_0	s: []	p: 5	w: 2
    Removed DPs: #7
Number of SCCs: 2, DPs: 4
  SCC { #4 #6 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded.
      conv	s: []	p: 2	w: 20167
      s 	s: [1]	p: 0	w: x1
      lastbit^1_s	s: []	p: 3	w: 8368
      #conv	s: [1]	p: 0	w: x1 + 1
      #lastbit^1_0	s: []	p: 0	w: 0
      #half	s: 1
      #lastbit	s: 1
      half^1_s	s: [1]	p: 0	w: x1
      rand	s: []	p: 0	w: x1 + 1
      half	s: 1
      lastbit	s: []	p: 3	w: 8368
      0 	s: []	p: 4	w: 1
      nil	s: []	p: 1	w: 20167
      #half^1_s	s: 1
      half^1_0	s: []	p: 4	w: 1
      #lastbit^1_s	s: []	p: 0	w: 1
      cons	s: [2]	p: 1	w: max(x1, x2 + 1)
      #half^1_0	s: []	p: 0	w: 0
      lastbit^1_0	s: []	p: 5	w: 8367
    Removed DPs: #4 #6
Number of SCCs: 1, DPs: 2
  SCC { #1 #5 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... succeeded.
      conv	s: []	p: 2	w: 38982
      s 	s: [1]	p: 0	w: x1
      lastbit^1_s	s: []	p: 3	w: 38980
      #conv	s: [1]	p: 0	w: x1 + 1
      #lastbit^1_0	s: []	p: 0	w: 0
      #half	s: 1
      #lastbit	s: 1
      half^1_s	s: [1]	p: 0	w: x1
      rand	s: []	p: 0	w: x1 + 1
      half	s: 1
      lastbit	s: []	p: 3	w: 38980
      0 	s: []	p: 4	w: 1
      nil	s: []	p: 1	w: 38982
      #half^1_s	s: 1
      half^1_0	s: []	p: 4	w: 1
      #lastbit^1_s	s: 1
      cons	s: [2]	p: 1	w: max(x1, x2 + 1)
      #half^1_0	s: []	p: 0	w: 0
      lastbit^1_0	s: []	p: 5	w: 38979
    Removed DPs: #1 #5
Number of SCCs: 0, DPs: 0