Timeline for For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 20, 2017 at 12:06 | comment | added | Yuval Filmus | Personally I am not too interested in Turing machines, and even less in their encodings, but perhaps you'll find a more sympathetic expert in the crowd. | |
| Apr 20, 2017 at 12:06 | comment | added | Yuval Filmus | The answer to your question is that it is (i) ill-defined, and (ii) the property you want holds for algorithmic prefix complexity. This suggests that instead of exploring encodings of Turing machines (which is not well-defined), you should just stick to the usual notions of Kolmogorov complexity, which are intended to capture such properties. | |
| Apr 20, 2017 at 12:01 | comment | added | StefanH | In what sense does this answers the question if we can encode a fixed argument just with a constant overhead independent of the argument into a new machine? Do you got what I was asking? | |
| Apr 20, 2017 at 11:41 | history | answered | Yuval Filmus | CC BY-SA 3.0 |