Can a non-deterministic Turing machine accurately simulate a deterministic one? If not, how much redundancy would be needed to be 99.999% certain that an error would not occur under standard operating conditions within the universe's life span?
Name:
Anonymous2014-07-15 17:05
Let c be the chance that a NDTM compute unit will produce an incorrect result. Let T be the time in seconds until the death of the universe. Let n be the count of NDTM compute units. Let X be a random variable signifying the length of time before failure. Let p = c(n/2-1), the probability that more than half of the compute units return an incorrect result. Let g be the number of operations, during which a compute unit may return an incorrect result, performed per second. Let N = ngT, the total operations performed. Let L = Nc, the expected number of incorrect results returned.
Assume all the assumptions of a Poisson process.
Note that P(X>T)=P(X(t)=0)=e-Lt 0.99999=e-cngT -ln(0.99999)/cgT=n