Reversible computers are turing-complete. The only requirement is you either have to store all intermediate results (no erasing), or you have to periodically "u

Reversible computers are turing-complete. The only requirement is you either have to store all intermediate results (no erasing), or you have to periodically "uncompute" them. I don't remember what the minimum bound on the overhead is, but it's manageable.