Suppose that one has a Blum–Shub–Smale machine. Is it possible to write down a program of finite length that produces a series of numbers, with each consisting of a finite number of digits, such that these numbers are truly random in the sense of Kolmogorov randomness, that is, no program of finite length on a Turing machine can produce the same series of numbers?

  • 1
    $\begingroup$ I don’t think so. Their Kolmogorov complexity would be logarithmic. $\endgroup$ – Yuval Filmus Apr 19 at 11:18

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.