Turing and Church had considered various computational

models, such as

Turing machines, random-access machines, and so on. All

these computational

models could be implemented through physical systems subject to

the laws of classical mechanics. While studying many such

computational

models, computer scientists came up with the following Holy

Grails:

1

1. Church-Turing thesis: This states that any computational

model

is as powerful as the Turing machine. In other words, given

any computational

model, we can simulate computations on that model using

the Turing machine. The simulation may of course involve a

blow-up

in time taken as well as in space used.

2. Strong Church-Turing thesis: This states that for any

computational

model, a polynomial-time algorithm for a decision problem in

that computational model can be simulated by a

polynomial-time algorithm

in the Turing machine model. In looser language, if we think

of polynomial time as the notion of tractability, then

tractability in

any computational model is equivalent to tractability in the

Turing

machine model.

3. Strong Church-Turing thesis (randomized version): This states

that for any computational model, a bounded-error

probabilistic polynomial

time algorithm for a decision problem in that computational

model can be simulated by a bounded-error probabilistic

polynomial

time algorithm for the problem in the Turing machine model.

In looser

language, if we think of BPP as the notion of tractability,

then BPP

is any computational model is equivalent to tractability in

the Turing

machine model.