Interested to Buy Any Domain ? << Click Here >> for more details...
Answer Posted / aki
Sorry for not explaining well.
got from :
http://www.cmi.ac.in/~ramprasad/lecturenotes/algcomp/lecture20.pdf
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.
| Is This Answer Correct ? | 0 Yes | 0 No |
Post New Answer View All Answers
What do you know about the psychophysics and neurophysiology of selective, visual or focal attention?
What is the significance of modelling and which model types do you know?
Explain the term 'ms-dos'?
In humans, brown eyes (B) are dominant over blue (b). A brown-eyed man marries a blue-eyed woman and they have 8 children, all brown -eyed. What are the genotypes of the parents and offspring?
What is a place code?
Describe the trichromacy vs. opponency theories of color processing.
Derive the conditions for stability of a two-dimensional linear system.
Describe the main biophysical characteristics of one type of ionic channel and how its biophysical properties contribute to its physiological function?
Explain how a system of chemical reactions can be represented as ODEs and PDEs?
How does the diffusion equation differ from the cable equation?
What are the main categories of application software?
What do you know about population coding in subcortical like superior colliculus or cortical structures?
what are the frontal and pre-frontal cortical areas?
What causes high-frequency oscillations in invertebrates or vertebrates?
Explain what is movements?
