I think that Tim is pointing out that there is no available mathematical measure for the ‘tinyness’ of this machine which is not circular. You seem to be saying that the machine looks simple to most people and that all other machines which people class as simple could be simulated on this machine within a few hundred bits. This has two problems. Firstly, it is not provable that all other machines which we class as similarly simple will be simulated within a few hundred bits as it is an empirical question which other machines people find simple. I’ll grant that we can be reasonably confident though. The second problem is that we haven’t defined any canonical mathematical measure of simplicity, just a measure of ‘simplicity relative to the empirical facts about what humans find simple’. Perhaps we could use physics instead of humans and look at physically small Turing machines and then have ‘simplicity relative to the empirical facts about what can be done in small volumes’. These are no doubt interesting, but are still concepts of relative simplicity, not a canonical absolute simplicity/complexity. No such measure has been discovered, and perhaps there can be no such measure. We can contrast this with complexity of infinite strings, where there is a convergence between all base machines and thus an absolute measure of simplicity. The problem is that we are now looking for something to deal with finite strings, not infinite ones.
Shane:
That’s why a tiny reference machine is used.
I think that Tim is pointing out that there is no available mathematical measure for the ‘tinyness’ of this machine which is not circular. You seem to be saying that the machine looks simple to most people and that all other machines which people class as simple could be simulated on this machine within a few hundred bits. This has two problems. Firstly, it is not provable that all other machines which we class as similarly simple will be simulated within a few hundred bits as it is an empirical question which other machines people find simple. I’ll grant that we can be reasonably confident though. The second problem is that we haven’t defined any canonical mathematical measure of simplicity, just a measure of ‘simplicity relative to the empirical facts about what humans find simple’. Perhaps we could use physics instead of humans and look at physically small Turing machines and then have ‘simplicity relative to the empirical facts about what can be done in small volumes’. These are no doubt interesting, but are still concepts of relative simplicity, not a canonical absolute simplicity/complexity. No such measure has been discovered, and perhaps there can be no such measure. We can contrast this with complexity of infinite strings, where there is a convergence between all base machines and thus an absolute measure of simplicity. The problem is that we are now looking for something to deal with finite strings, not infinite ones.