How do we define the term computation / computable function generically across models of computation?

Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function".

A function f with domain f is said to be Turing-computable of just computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F) such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D (Linz:1990:243)

Computable Functions A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape. (Sipser:1997:190)

Definition 5.12 A function f: Σ* → Σ* is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape. (Sipser:1997:190)

A partial function σ: Σ* → Σ* is said to be a computable function if σ(x) = M(x) for some Turing machine M. (Kozen:1997:347)

I need to have the term [computable function] defined generically across models of computation so that I can know whether or not a specific C function is a [computable function].

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: PWS Publishing Company

Kozen, Dexter 1997. Automata and Computability. New York: Springer-Verlag.


2 Answers 2


Definition 5.12 is a standard way of defining a "computable function". I see that you wish it was defined generically, but things are not as you wish they were; computability is typically defined with respect to a single model of computation.

That said, if you have any other Turing-complete notion of computation, then it is easy to prove that you can replace "Turing machine" with "machine in that model of computation" and you'll get an equivalent notion: in other words, there will be a Turing machine that computes $f$ iff there is a machine in that model of computation that computes $f$. So the concept is indeed quite generic, even if the definition is not articulated that way.

See also https://en.wikipedia.org/wiki/Computable_function#Definition.

The exact semantics of C are messy and hard to formalize, and there appears to be some debate about whether C is Turing-complete, so C code is typically not a good way to prove that a function is computable or to reason about whether a function is computable.

  • $\begingroup$ I think that I am looking for a way to know whether or not an arbitrary C function that might require static local data is a Turing computable function. It looks like that Church-Turing thesis may be far more nuanced than I thought. en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis $\endgroup$
    – polcott
    Commented May 3, 2021 at 1:57
  • 1
    $\begingroup$ @polcott, I think you're not going to find a good answer for that question, for the reasons I already articulated in my last paragraph. I understand that you want it, but it doesn't change the situation. This is not an issue with the Church-Turing thesis; it is an issue with formalizing the semantics of C. I suggest you look for a different angle to approach your situation, without bringing C into it. $\endgroup$
    – D.W.
    Commented May 3, 2021 at 2:13

When we unify on the Sipser and Kozen definitions of "computable function" we have the mapping from one possibly empty finite string to another possibly empty finite string.

This can be generalized to all models of computation that operate on finite strings. C functions deriving 0/1 integer return values from finite string inputs would seem to meet the above specification.

Language acceptor of the Chomsky hierarchy:
int Accept(char* S); // returns 0 or 1

It would seem that the above C function could implement every Turing computable language acceptor that does not require more memory than is available.

Please critique this I am aiming for the best quality answer.


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.