# Definition: WHILE-Computable Functions

A function $$f : \mathbb N^k \to \mathbb N$$ is WHILE-computable, if there exists a unit-cost Random Access Machine $$M$$ with a finite $$W H I L E$$ program $$P$$, such that the machine $$M$$ computes the output $$m\in \mathbb N$$ for every input of $$k$$ natural numbers $$(n_1,\ldots,n_k)\in\mathbb N^k$$, i.e.

$f(n_1,\ldots,n_k)=m$

in the following way: Given the initial state of registers of $$M$$ $$r_i:=n_i$$ for $$1\le i\le k$$ and $$r_i:=0$$ for $$i > k$$, $$M$$ starts the $$W H I L E$$ program $$\mathtt {P}$$ and terminates at a new state such that * $$r_i=n_i$$ for $$1\le i\le k$$ (i.e. the initial register states remain unchanged), * $$r_{k+1}=m$$ (i.e. the next register contains the output), and * $$r_i=0$$ for $$i > k + 1$$.

The set of all WHILE-computable functions is denoted by $$W H I L E$$.

The function $$f : \mathbb N^k \to \mathbb N$$ is partially WHILE-computable, if there is a subset $$S^k\subseteq\mathbb N^k$$, for which the restriction $${f|}_{S^k} : \mathbb N^k \to \mathbb N$$ is WHILE-computable and for every input $$(n_1,\ldots,n_k)\in\mathbb N^k\setminus S^k$$ the machine $$M$$ behaves as follows: Given the initial state of registers of $$M$$ $$r_i:=n_i$$ for $$1\le i\le k$$ and $$r_i:=0$$ for $$i > k$$, $$M$$ starts the $$W H I L E$$ program $$\mathtt {P}$$ and never terminates. In this case, we set $f(n_1,\ldots,n_k)=\text{undefined}.$

The set of all partially WHILE-computable functions is denoted by $$W H I L E^{part}$$.

Corollaries: 1

Corollaries: 1
Proofs: 2 3
Theorems: 4 5

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition