Branches History Index

◀ ▲ ▶Branches / Theoretical-computer-science / Computability / Corollary: The set of WHILE-computable functions is included in the set of partially WHILE-computable functions

Corollary: The set of WHILE-computable functions is included in the set of partially WHILE-computable functions

(related to Definition: WHILE-Computable Functions)

There are functions \(f : \mathbb N^k \to \mathbb N\), which are partially WHILE-computable, but are not WHILE-computable. In particular, the set of all WHILE-computable functions is a proper subset of the set of all partially WHILE-computable functions:

\[W H I L E\subset W H I L E^{part}.\]

Note: This corollary actually makes sure that partially WHILE-computable functions are well-defined.

Table of Contents

Proofs: 1

Mentioned in:

Theorems: 1

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

Github:
bookofproofs

References

Bibliography

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