some steps, e.g ap-get, are not deterministic and practically, it would be painful to make them so (usually controlling updates with an external mirror, ignoring phased upgrades, bunch of other misc stuff).

You then start looking at immutable OSes, then get to something like NixOS.