Turing machine
A "lossy Turing machine" is a Turing machine in which part of the tape may non-deterministically disappear. The Halting problem is decidable for lossy Turing machine but non-primitive recursive.