In Kolmogorov complexity, there is a notion: length of the shortest program that describes the data. I can use Lempel-Ziv compression to estimate this value. What if I want to estimate this value by writing a program for Turing Machine.

  1. What is the formula to calculate the length of this program?
  2. What is the length of 1 instruction: sigma(state, tape): state, tape, move. Is it 5? You can represent instruction as 01011 (state, tape,...)
  3. Let's say I have 2 strings: 01010101, 00000000. What is the code of the shortest programs?
  • 1
    $\begingroup$ I don't think it matters exactly how you represent your Turing machines. The basic concept of Kolmogrov complexity is not sensitive to the details of the representation scheme - or even to the programming language that you use. It is the relative lengths of the programs that are important here, not their absolute lengths. $\endgroup$ – gandalf61 Aug 22 '19 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.