3
$\begingroup$

Some days ago I read about the Church-Turing Thesis and it establishes that any function can be described as an algorithm, so being defined as computable, and no function mismatches the Thesis. But, what about random function? If our computers are Turing Machines, and pure randomness cannot be obtained in a computer, is the random function non computable?

$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure computability is that rigorously defined. Also, what is the random function? What is the input that it takes, and how is its output defined on that input? Usually, a PRNG implemented in a computer can take no input at all and produce a non-repeating output, so it's unclear that it can be mapped onto the notion of a function well enough for us to discuss its computability. $\endgroup$
    – Brian Tung
    Sep 14, 2015 at 23:17

1 Answer 1

4
$\begingroup$

One of the properties that a function has is that it gives a unique output when given a particular input. The random "function" does not possess this property, and hence the Church-Turing Thesis does not apply to it.

$\endgroup$
1
  • $\begingroup$ Touché. Now I can sleep this night. Thanks! $\endgroup$ Sep 14, 2015 at 23:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .