Why not the standard approach of using Shannon’s state x symbol complexity for Turing machines?
Why choose a Turing machine? They are clearly not a canonical mathematical entity, just a historical artifact. Their level of power is a canonical mathematical entity, but there are many Turing-equivalent models of computation. This just gets us simplicity relative to Turing machines where what we wanted was simplicity simpliciter (i.e. absolute simplicity). If someone came to you with a seemingly bizarre Turing-complete model, where the shortest program for successor was 3^^^3 bits and all the short programs were reserved for things that look crazy to us, how can you show him that Turing machines are the more appropriate model? Of course, it is obvious to us that Turing machines are in some sense a better judge of the notion of simplicity that we want, but can we show this mathematically? If we can, it hasn’t yet been done. Turing machines might look simple to Turing machines (and human brains) but this new model might look simple to itself (e.g. has a 1 bit universal machine etc.).
It looks like we have to settle for a non-canonical concept of simplicity relative to human intuitions or simplicity relative to physics or the like. I think this is a deep point, which is particularly puzzling and not sufficiently acknowledged in Kolmolgorov complexity circles. It feels like there must be some important mathematically canonical measure of complexity of finite strings, just like there is for infinite strings, but all we have are ‘complexity-relative-to-X’ and perhaps this is all there is.
Shane:
Why not the standard approach of using Shannon’s state x symbol complexity for Turing machines?
Why choose a Turing machine? They are clearly not a canonical mathematical entity, just a historical artifact. Their level of power is a canonical mathematical entity, but there are many Turing-equivalent models of computation. This just gets us simplicity relative to Turing machines where what we wanted was simplicity simpliciter (i.e. absolute simplicity). If someone came to you with a seemingly bizarre Turing-complete model, where the shortest program for successor was 3^^^3 bits and all the short programs were reserved for things that look crazy to us, how can you show him that Turing machines are the more appropriate model? Of course, it is obvious to us that Turing machines are in some sense a better judge of the notion of simplicity that we want, but can we show this mathematically? If we can, it hasn’t yet been done. Turing machines might look simple to Turing machines (and human brains) but this new model might look simple to itself (e.g. has a 1 bit universal machine etc.).
It looks like we have to settle for a non-canonical concept of simplicity relative to human intuitions or simplicity relative to physics or the like. I think this is a deep point, which is particularly puzzling and not sufficiently acknowledged in Kolmolgorov complexity circles. It feels like there must be some important mathematically canonical measure of complexity of finite strings, just like there is for infinite strings, but all we have are ‘complexity-relative-to-X’ and perhaps this is all there is.