Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Turing Machine Question

Name: Anonymous 2014-07-14 15:14

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: Anonymous 2014-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

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List