Partial functions computed by a machine under fixed encodings

Let $X$ and $Y$ be sets, let $e_X:X\to \{0,1{\}}^{\ast },e_Y:Y\to \{0,1{\}}^{\ast }$ be effective binary encodings in the sense of Effective binary encodings and total decoders, let $M=(Q,\{0,1\},\mathrm{\Gamma },\bigsqcup ,q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}},\delta )$ be a deterministic one-tape Turing machine, and let $f:D\to Y$ be a function with domain $D\subseteq X$.

The machine $M$ computes the partial function $f$ under the fixed encodings $e_X,e_Y$ if:

• for every $x\in D$, the computation of $M$ on input $e_X(x)$ halts and its final configuration outputs the binary word $e_Y(f(x))$, and
• for every $x\in X\setminus D$, the computation of $M$ on input $e_X(x)$ diverges.

Thus the machine's input and output are ordinary finite binary words, while the mathematical function lives on the underlying sets $X$ and $Y$ through the chosen encodings.

• This definition intentionally separates the machine from the represented function. Changing the encoding can change which partial function a fixed machine computes.

• Nothing in the definition requires any particular behaviour on malformed binary strings outside the image of $e_X$.