3 ms·
> Isn't every algorithm reversible if you save the inputs? 1. No, it might be probabilistic or non-deterministic. 2. Depends on your definition of reversibili
by einpoklum 6y ago
> Isn't every algorithm reversible if you save the inputs?
1. No, it might be probabilistic or non-deterministic.
2. Depends on your definition of reversibility. Maybe it's the ability to reverse a single, highly-localized, operation, such as an ALU operation; in which it doesn't help that you can repeat the computation all the way from the input to the previous state.
- nfoz 6y agoA pure turing machine doesn't have access to a real random number generator. So whatever your entropy source is, I think you need to consider that as one of your inputs.