Turing completeness: Difference between revisions
Jump to navigation
Jump to search
Created page with "A Turing-complete system is a system that can compute every computable functions. A Turing-complete system can be used to simulate any Turing machine or other Turing-complete systems. The halting problem is uncomputable on any Turing-complete system. To be Turing-complete, a system must be able to store unbounded memory, access it and must contain non-halting programs (like "while" loops or recursion). === List of Turing-complete systems === This list is non-exhaustiv..." |
(No difference)
|
Revision as of 09:35, 17 December 2025
A Turing-complete system is a system that can compute every computable functions. A Turing-complete system can be used to simulate any Turing machine or other Turing-complete systems.
The halting problem is uncomputable on any Turing-complete system.
To be Turing-complete, a system must be able to store unbounded memory, access it and must contain non-halting programs (like "while" loops or recursion).
List of Turing-complete systems
This list is non-exhaustive.
- Turing machine
- Lambda calculus
- Minsky machine
- Rule 110
- Conway's game of life
- 2-Tag system
- Cyclic tag
- Tree rewrite system