3 ms·
In Kolmogorov complexity you typically do not care about constant offsets. You assume you are free to choose the language to implement the program in and in the
by laszlokorte 5y ago
In Kolmogorov complexity you typically do not care about constant offsets. You assume you are free to choose the language to implement the program in and in the worst case if someone else choses another language you just have to prefix all your programs with an interpreter of your language written in the other language. The size of that interpreter might be huge but it‘s a constant length for all your programs so you dont care.
Same for program vs literal: just include one prefix symbol in your language to mark your program as either literal output or real program.
That makes all your programs one symbol longer but as you only care about relative program size inside your language you do not care.