Branches History Index

◀ ▲ ▶Branches / Theoretical-computer-science / Computability / Theorem: Simulating LOOP Programs Using WHILE Programs

Theorem: Simulating LOOP Programs Using WHILE Programs

Every LOOP program can be simulated using a WHILE program. In other words, the set of all LOOP-computable functions is a subset1 of all WHILE-computable functions:

\[L O O P \subseteq W H I L E.\]

Table of Contents

Proofs: 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

Footnotes

  1. Please note that the conversion is not true. One reason for this is because all LOOP-computable functions are total, but there are also partially WHILE-computable functions (which are not total). ↩