The discussion centers on the distinction between "effectively computable" functions in both informal and formal contexts. It clarifies that "effectively" refers to functions that can be computed with reasonable resources, such as time and storage, and can be precisely defined using computational models like Turing machines. The Church-Turing thesis asserts that informal and formal computability are equivalent. Participants emphasize the importance of defining "reasonable" in the context of computation theory versus engineering.
PREREQUISITESThis discussion is beneficial for computer scientists, mathematicians, and students studying computational theory, particularly those interested in the foundations of algorithmic efficiency and computability.
Evgeny.Makarov said:It would be helpful to know the context. If "effectively" means "with reasonable resources, i.e., time and storage", then it means precisely that: with reasonable resources, which is not a precise judgment. We could make it more precise, for example, by saying that the function is computable in polynomial time, or in time $O(t^5)$ on an unlimited register machine. If "effectively" means computable at all, then it means there is an something like an algorithm, which can be implemented on reasonable devices like a modern computer with unlimited memory. Here "reasonable" means in the context of computation theory, not engineering. For example, a pushdown automaton is not a reasonable device because its computational power is known to be strictly less than that of a Turing machine. Showing that a function is computable in the formal sense would involve showing that it is computable according to a precise definition of some universal device, such as Turing machines, Markov algorithms, Kleene recursive functions, etc. The Church-Turing thesis says that the informal and the formal senses of computability coincide.[/QUOTE
Thank you very much. So, if we state that a function is effectively computable in the informal sense, we are simply acknowledging the existence of an algorithm that can be used to compute it for each value of its domain. Is that correct?
Again thanks a lot for helping me out, agapito
Evgeny.Makarov said:I would say, yes. Plus, if "effectively" is a statement about resources, then the algorithm takes reasonable time and storage. But it may sound this way to me only because in Russian there are no two different words for "effectively" and "efficiently". I am not sure "effective" is about resources here. (Smile)