Questions tagged [universal-turing-machines]

Filter by
Sorted by
Tagged with
9
votes
1answer
338 views

Is Kolmogorov complexity a surjective function?

Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,x) outputs whatever T outputs on input x (possibly both running forever). Define the Kolmogorov complexity ...
28
votes
2answers
1k views

Can we not output the Kolmogorov complexity?

Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on ...