Arithmetic Function

math

Definition

Arithmetic Function

An arithmetic function is a function from a tuple of natural numbers to a natural number.

Computability

Computation of an Arithmetic Function

Denote as the binary representation of an . The initial configuration of a Turing machine with alphabet . The input works on input:

where must not contain leading zeros.

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

Example Initial Configuration

Let and with binaries . Here, the initial configuration is:

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

with (final state), (tape words), and emits .

Parsing " "

• The head is position at the leftmost bit because (final state) precedes .
• Right after the number there is a blank (a delimiter).
• The machine is in an accepting (final) state , i.e., it has halted.
• Therefore, the output is .

is arbitrary content elsewhere. It doesn’t matter what’s left in or .

Computation of

A Turing machine with input alphabet computes an arithmetic function if works on as input, and outputs . Denote .

Example with input

Let . Let be:

State/Input

For instance, let be the input. Thus, the tape contains :

The Turing machine halts at . The output is , see final configuration.

The computed function is , whereby .

Note: The same Turing machine , when the pair is encoded on the tape as , computes , whereby:

Here is the binary length:

Link to original