-4

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

I am trying to write C code that would be acceptable to computer scientists in the field of the theory of computation.

It looks like anything that can be construed as a mapping from a tuple of natural numbers to a natural number is a computable function no matter what occurs in-between.

We can assume that the function takes a finite string (or machine address of a finite string) input and derives a Boolean output. There is a dearth of material regarding the correspondence between C functions and computable functions.

I have been told that computable functions must be a pure function of their inputs. Several reviewers indicated that this may forbid the use of static local data.

https://en.wikipedia.org/wiki/Computable_function

https://math.stackexchange.com/questions/2993807/what-is-a-computable-function

25
  • 1
    In general, all C functions are computable unless they never return, as a CPU can obviously compute them. You typically need to exclude external events and memory-modifying interrupts, as these aren't covered by computability considerations. In addition, the semantics of a C function depends not only on the program code, but also on compiler and hardware behavior. Commented Sep 24, 2021 at 21:23
  • 3
    Perhaps you need a very precise definition of what a "computable function" is and read it very carefully. A "function" in mathematics maps input values to output values in a deterministic way. Without side effects.
    – gnasher729
    Commented Sep 24, 2021 at 21:38
  • 3
    Static local data indeed makes a C function incompatible with the concept of computability unless you consider the static variables part of the input and output of the function. Commented Sep 24, 2021 at 21:42
  • 4
    @polcott I think you misunderstand both the Halting problem and what "computable" means. I don't understand why you seem to think you're correct after everyone else in this thread, and your other post (both downvoted to oblivion) is disagreeing with you.
    – Dai
    Commented Sep 25, 2021 at 0:22
  • 1
    @polcott As far as you're concerned, C functions are not mathematical functions, that's the point we're trying to get you to understand.
    – Dai
    Commented Sep 25, 2021 at 0:26

1 Answer 1

3

The formal definition for "computable functions" is given behind the two links you already posted in the question, and they are better than anything I could repost here again, but let me try to explain some things here:

  • A computable function f is a mathematical function f: A->B, where its mapping from the set A to B can be effectively computed by some model of computation. Note that A and B have to be finite or infinite countable set (often it is assumed A = N^k, B = N , N =set of natural numbers).

  • A function in a programming language like C is not a mathematical function, it is a language construct which was modeled in analogy to mathematical functions. To make the difference more apparent, one could use the language-agnostic term subroutine for them (though in C, "function" is definitely the more common name). C functions operate on strings and/or finite numbers, they can also take pointers to other functions as input, and they can have "side effects" as well as become influenced by side effects.

Hence it is easy to mix up these two concepts since both use the same term "function" for different things. It also shows that when reading your question literally, a "C function" is never a computable function, since it is not even a function - in the strictly mathematical sense.

But what is the relationship between "C functions" and "computable functions"?

Well, if we use the C programming language as our "model of computation", we could say that in a less rigourous sense, a mathematical function f:A->B is computable when there is a corresponding C function F which is a "sufficiently good approximation" for f. What does that mean?

My understanding about this is the following: for ease of explanation let us take A to be the set of finite character strings and B={0,1}. Then we would expect f(x) = F(x) for all values in x from A, assumed our C function would run on an idealized machine with no restrictions on memory and string lengths. Note this definition can be expanded to arbitrary countable sets A and B which map to tuples of data types in the language C.

So if C functions are our model of computation, would that not make any C function "computable" by definition?

No. To my understanding, it makes only sense to apply the term "computable" to a C function F when there is a mathematical function f where F can be used to proof its computability. For this, only a certain class of C functions are suitable, they need to fulfill the following conditions:

  1. F must be guaranteed to return a value, it must not run in an infinite loop or exit program

  2. F must not be influenced by any side-effects (since it would make it impossible to guarantee F(x)=f(x) for all x). Note that F having any side-effects itself, however, does not necessarily preclude this, but side-effects could be also seen as a "disturbing additional return value", hence it is generally better to exclude C functions of this type as well.

There is a well-known name for this kind of programming language functions in computer science: they are called pure functions, to cite Wikipedia:

a pure function is a computational analogue of a mathematical function

Note from condition 1, it follows that a "computable C function" (or pure function) F must not take another C function as input (or at least: must not call such another function passed as parameter), since it cannot be guaranteed that a call to that other function would ever return. Condition 2 forbids, for example the usage of statics (neither locally or globally), since it could influence the output of the computation.

Hope this helps to bring some light into it.

13
  • "A and B have to be infinite countable set" Thus a TM that picks out the even numbers from the subset of natural numbers from 1 to 100 is not a computation. Your wording needs improvement.
    – polcott
    Commented Sep 25, 2021 at 14:22
  • Another answer is a different group seemed to indicate that only the first element of pure function is required for C code to be a computable function.
    – polcott
    Commented Sep 25, 2021 at 14:27
  • "The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams)." This seems to say that as long as "the function return values are identical for identical arguments" all of the other items on this list don't make any difference because there is {no variation} with any of them.
    – polcott
    Commented Sep 25, 2021 at 14:30
  • @polcott: 1. see my edit. 2. I have no idea what you mean by "first element". 3. what do you mean by "this list"?
    – Doc Brown
    Commented Sep 26, 2021 at 7:07
  • ... and if you are unsure whether a certain C function is pure, you may ask a new question on this site where you post the function's code and explain why the Wikipedia article about pure functions did not help you to answer your question. Also, I would recommend to stop using the term "computable" for programming language functions, that's the term to be used for mathematical functions.
    – Doc Brown
    Commented Sep 26, 2021 at 7:30

Your Answer

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

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