The step function does not encode memory. The step function is a function that takes memory state 1 as input, and outputs memory state 2 as output. The step function itself doesn't change, it stores no information.
In physical terms, the step function is the CPU, minus the caches, registers and other modifiable state. Memory is the disk and ram and all the CPUs caches and registers. You can't tell me anything about what the input to the CPU is, or what it is actually doing (other than that it is capable of running arbitrary x64 assembly), without looking at the state.
Computation can be seen as some act of carrying out logic. And in turn, logic can be approached via entropy. There are a lot of people working in QM, computation and entropy. But the simpler definition is just via partitions (and you especially don't have to insist on it being in the world of QM either). [1]
(Sorry about replying so late, I know it's unlikely you will see this, oh well)
Edit: Doesn't that step function encode all of memory implicitly?