**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 computation / computable function defined generically across models of computation so that I can know whether or not a specific C function is a computation / computable function. I have a C function that uses static local data and some reviewers say that this does not count as a computation / 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.