Arithmetic Function

math

Definition

Arithmetic Function

An arithmetic function $f:{\mathbb{N}}^k\to \mathbb{N}$ is a function from a tuple of natural numbers to a natural number.

Computability

Computation of an Arithmetic Function

Denote $[n{]}_2$ as the binary representation of an $n\in \mathbb{N}$. The initial configuration of a Turing machine $M$ with alphabet $\Sigma =\{0,1\}$. The input works on input:

$$(n_1,n_2,\dots ,n_k)\in {\mathbb{N}}^k\cong ([n_1{]}_2,[n_2{]}_2,\dots ,[n_k{]}_2)\in ({\Sigma }^{+}{)}^k$$

where ${\Sigma }^{+}$ must not contain leading zeros.

The initial configuration of $M$ is where $B$ (blank symbol) separates each block.

$$q_0[n_1{]}_{2}B[n_2{]}_{2}B\dots B[n_k{]}_2$$

Example Initial Configuration

Let $k=3$ and $(n_1,n_2,n_3)=(5,2,7)$ with binaries $(101,10,1111)$. Here, the initial configuration is:

$$q_{0}101B10B1111$$

The end configuration of a (function-computing) Turing machine $M$ is given by:

$$xp[n{]}_{2}By$$

with $p\in F$ (final state), $x,y\in {\Gamma }^{\ast }$ (tape words), and $M$ emits $n\in \mathbb{N}$.

Parsing " $xp[n{]}_{2}By$"

• The head is position at the leftmost bit because $p\in F$ (final state) precedes $[n{]}_2$.
• Right after the number there is a blank $B$ (a delimiter).
• The machine is in an accepting (final) state $p$, i.e., it has halted.
• Therefore, the output is $n$.

$x,y\in {\Gamma }^{\ast }$ is arbitrary content elsewhere. It doesn’t matter what’s left in $x$ or $y$.

Computation of $f:{\mathbb{N}}^k\to \mathbb{N}$

A Turing machine $M$ with input alphabet $\Sigma =\{0,1\}$ computes an arithmetic function $f:{\mathbb{N}}^k\to \mathbb{N}$ if $M$ works on $(n_1,\dots ,n_k)$ as input, and outputs $f(n_1,\dots ,n_k)$. Denote $F(M)=f$.

Example with input $6$

Let $M=(\{q_0,q_1,q_2\},\{0,1\},\{0,1,B\},\delta ,q_0,B,\{q_2\})$. Let $\delta$ be:

State/Input	$0$	$1$	$B$
$q_0$	$(q_0,0,R)$	$(q_0,1,R)$	$(q_1,0,S)$
$q_1$	$(q_1,0,L)$	$(q_1,1,L)$	$(q_2,B,R)$

For instance, let $6$ be the input. Thus, the tape contains $[6{]}_2=110$:

$$\begin{array}{rl}{q}_{0}110& ⟹1q_{0}10⟹11q_{0}0⟹110q_0[B]⟹110q_{1}0\\ ⟹11q_{1}00& ⟹1q_{1}100⟹q_{1}1100⟹q_{1}B1100⟹q_{2}1100\end{array}$$

The Turing machine halts at $q_2\in F$. The output is $1100=[12{]}_2$, see final configuration.

The computed function is $f_1=F(M):\mathbb{N}\to \mathbb{N}$, whereby $f_1(n)=2n$.

Note: The same Turing machine $M$, applied on number pairs, computes $f_2=f(M):{\mathbb{N}}^2\to \mathbb{N}$, whereby:

$$f_2(m,n)=m\cdot 2^{bl(n)+1}+n$$

where $\mathrm{bl}$ is the binary length:

$$\begin{array}{rl}\mathrm{bl}(0)& =1\\ \mathrm{bl}(k+1)& =\lfloor {\log }_2(k+1)\rfloor +1\end{array}$$

Link to original