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.
- What is the formula to calculate the length of this program?
- What is the length of 1 instruction: sigma(state, tape): state, tape, move. Is it 5? You can represent instruction as 01011 (state, tape,...)
- Let's say I have 2 strings: 01010101, 00000000. What is the code of the shortest programs?