# Computation is effectively computable in theory and in practice

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.

• Are you more or less asking for a comparison between Turing computability and models of computation in the real world? In this case, you might expect an answer to talk about physics, hypercomputation, and cogsci. Did you happen to mean efficiently computable (feasible vs very hard computation)? This is a more common question. Otherwise, I don't know what you mean by effectively computable in practice. – mdxn Sep 24 '14 at 2:31

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.)