The discussion revolves around the distinction between "effectively computable" functions in the informal sense versus the formal sense, particularly in the context of numerical functions. Participants explore the implications of these terms within computational theory and seek clarification on their meanings and examples.
Participants generally agree on the notion that "effectively computable" involves the existence of an algorithm, but there is uncertainty regarding the implications of "effectively" in relation to resource constraints. The discussion remains unresolved regarding the precise definitions and distinctions between informal and formal computability.
Participants highlight the ambiguity in the term "effectively" and its dependence on context, particularly in relation to computational resources and definitions. There is also a mention of the Church-Turing thesis, which suggests a connection between informal and formal computability, but this remains a point of exploration rather than consensus.
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)