Turing-Computable Arithmetic Function

computation

Definition

Turing-Computable Arithmetic Function

An arithmetic function $f:{\mathbb{N}}^k\to \mathbb{N}$ is called Turing-computable if there exists a Turing machine $M$ with $F(m)=f$ (see Turing machine).

According to Church-Turing thesis, computability is equivalent to Turing-compatibility.