Formal vs. informal - Numerical Functions

[agapito]

The literature mentions "functions that are effectively computable in the informal sense". What is meant by that? It would be helpful to have an example involving "informal sense" vs. "formal sense" for some numerical function.

All help appreciated. am

 

[Evgeny.Makarov]

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.

 

[agapito]

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]

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)

 

[agapito]

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)

Thanks again for your patience, you have been very helpful. agapito