Can computation always be reduced to permutation of certain states of a certain subtrate, or be performed by permutation of these, in every possible model of computation, classical or quantum? Or is it too general statement?

5 hours ago, Hrvoje1 said:

Can computation always be reduced to permutation of certain states of a certain subtrate, or be performed by permutation of these, in every possible model of computation, classical or quantum? Or is it too general statement?

Would you like to explain further, ?

Check this out: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4309123/#idm140111704079712title 

Here it says: 

A reversible computation ℭΠ(S) is the task of performing, with or without side-effects, a permutation Π over some set S of at least two possible attributes of some substrate

14 hours ago, Hrvoje1 said:

Can computation always be reduced to permutation of certain states of a certain subtrate, or be performed by permutation of these, in every possible model of computation, classical or quantum? Or is it too general statement?

No. Consider the computation that maps every input to zero. That's not reversible and is not a permutation.

OK, thanks wtf. I have probably misrepresented the theory from that paper a bit, so let me please rephrase my question. Is permutation the essence of reversible computation? Can reversible computation always be reduced to a permutation, ie be performed by it?

8 hours ago, Hrvoje1 said:

OK, thanks wtf. I have probably misrepresented the theory from that paper a bit, so let me please rephrase my question. Is permutation the essence of reversible computation? Can reversible computation always be reduced to a permutation, ie be performed by it?

Not sure what the paper is about. But any reversible process may be represented as a group; and every group may be represented as a group of permutations. That's the famous Cayley's theorem. https://en.wikipedia.org/wiki/Cayley's_theorem

I think you are right, I believe that is a general idea on which that definiton from the paper is based on. Thank you wtf.