2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – mdxn
    Sep 24 '14 at 2:31
7
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Hm, one might say "effectively computable" means "Turing-computable". We'd like to think that's the same as "computable", of course. Regarding your example for "computable in practice": we find such examples in P, too. $\endgroup$
    – Raphael
    Sep 22 '14 at 17:00
1
$\begingroup$

this question relates to the Church-Turing thesis which asserts that all possible computation is captured by Turing complete functions. there is a historical reference to "effective methods" that goes back in earlier math research. most mainstream computer scientists consider the Church-Turing thesis as unequivocal (and yet not provable, hence its name) as can be seen in [1] with many refs, although there is a small minority faction that asserts there is some kind of possible gap, but those assertions are very controversial and largely rejected within the mainstream. there is also some theory of hypercomputation which (roughly) attempts to look "beyond" the Church-Turing thesis. see also [2] for a strong argument against any theoretical deviation outside of the Church-Turing thesis.

[1] Applicability of Church-Turing thesis to interactive models of computation tcs.se

[2] The enduring legacy of the Turing machine. Fortnow, Ubiquity, 2010, December 2010

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.