-1
$\begingroup$

Are pure functions always computable functions?

In computer programming, a Pure function is a function that has the following properties:
(1) the function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams), and

(2) the function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams).

Computable functions are the basic objects of study in computability theory.
Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output.

Alternative versions of similar questions:
How do we define the term "computation" across models of computation?

To what extent is an x86 machine equivalent to a Turing Machine?

How can I tell if my C function is a computable function in computer science?

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You can define the Halting problem as a decision problem, where the function takes in a program and input, and determines whether the program will terminate or not. This is a pure function, but it's well-known that the Halting problem has no algorithm.

$\endgroup$
2
  • $\begingroup$ None-the-less I really need to know whether or not every pure function is always a computable function. $\endgroup$
    – polcott
    Jul 17, 2022 at 2:43
  • 4
    $\begingroup$ "I really need to know whether or not every pure function is always a computable function" – This very answer gives an example of a pure function that is not computable, so clearly the answer is no. (Disproving a universally quantified statement only requires a single counterexample for obvious reasons.) $\endgroup$
    – Jörg W Mittag
    Jul 17, 2022 at 8:39
2
$\begingroup$

It depends what you mean by "pure function". You have to carefully define it.

If "pure function" refers to computer code to compute some function, and if that code is guaranteed to always terminate, then yes, it computes a computable function.

If "pure function" refers to computer code to compute some function, and if that code is not guaranteed to always terminate, then no, it doesn't necessarily compute a computable function.

If "pure function" refers to a mathematical function (rather than an implementation in code), then it might or might not be computable.

When you need a precise definition, Wikipedia is not a reliable source. Terms like "computable function" are a mathematical concept that have a precise definition. To find the exact definition, I recommend studying a good textbook on the subject of computability. You might find discussion of computable functions in many places (including Wikipedia), where people talk informally about the notion of a computable function; there they speak with the understanding that others who have studied the subject can translate that informal discussion into precise mathematics if needed. I am speaking informally here in my answer. It is beyond the scope of an answer on this site to teach you the subject of computability theory; that's self-study you'll need to do on your own.

In my experience, the term "pure function" does not have a standard, accepted definition. Different people may use that phrase in similar but slightly different ways. So if you are working on a subject where the exact definition matters, you may need to define what you mean by "pure function" (which particular definition you are using) to enable clear communication and clear thinking.

$\endgroup$
3
  • $\begingroup$ I have Linz, Sipser and Kozen, none of them give more than a paragraph on what a computable function is. From extensive discussions on other forums and several questions on SE it seems that an impure function (violating the Wikipedia specification) is not a computable function. $\endgroup$
    – polcott
    Jul 17, 2022 at 4:02
  • $\begingroup$ I am trying to correctly determine whether or not a specific "C" function is Turing computable. Please see my recent edits that have added much more background. $\endgroup$
    – polcott
    Jul 17, 2022 at 14:31
  • $\begingroup$ @polcott A computable function is one that a Turing machine can compute. (if a precise definition of a Turing machine is needed then it depends on who is asking the question, but generally, all of the versions with slightly different details are still able to compute the same functions, so it doesn't matter a whole lot) $\endgroup$
    – user253751
    Dec 14, 2022 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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