Given a function
which takes a finite string as input and produces a finite string as output, a randomized Turing machine M is defined to compute
if, for any input string x,
, where the probability here is taken with respect to the coins flipped by M on input x. For deterministic functions from finite strings to finite strings, randomized Turing machines can compute some function that ordinary Turing machines cannot.