Cheap and Secure Web Hosting Provider : See Now

[Solved]: Computation is effectively computable in theory and in practice

, , No Comments
Problem Detail: 

My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice?

In trying to understand these concepts further, I have a couple of sub-questions as well:

  1. Is there a relationship between a computation being EC in theory and being EC in practice? (It seems just by taking the usual meaning of the words, EC in practice should imply EC in theory.)

  2. Is there an example of a computation that is EC in theory but not EC in practice?

  3. How about EC in practice but not EC in theory?

Either explanations or links to where these explanations may be will be helpful.

Asked By : Haikal Yeo

Answered By : David Richerby

The only definitions of the term "effectively computable" that I can find online are that the phrase just means "computable" (which is usually taken to mean "Turing-computable"). As such, computability is an absolute concept: either a function is computable or it is not. Are you asking about whether a function that is computable can actually be computed in practice? If so, the answer is clearly no: it's easy to construct families of problem instances that would require more time than the expected lifetime of the sun, for example. For example, take large instances of EXP-complete problems: $2^{100}$ exceeds the age of the universe in nanoseconds. (That is, a 1GHz computer that had been running since the beginning of time wouldn't have executed $2^{100}$ instructions yet.)

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback