Computable function

A function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ on words from ${\Sigma }^{\ast }$ is computable if there is a deterministic Turing Machine $M_f$ s.t.: (or there is a lambda-term)

• $M_f$ accepts all input words $w\in {\Sigma }^{\ast }$
• when started in configuration $(q_{\text{init}},ϵ,w)$, the machine eventually terminates in configuration $(q_{\text{accept}},ϵ,f(w))$.

The machine transforms the contents of the tape from $w$ to $f(w)$ and returns the tape head to the start of the word.