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..." |
→List of Turing-complete systems: Add Fractran |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
A Turing-complete system is a system that can compute every computable | A Turing-complete system is a system that can compute every computable function. 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. | The halting problem is uncomputable on any Turing-complete system. | ||
To be Turing-complete, a system must be able to store unbounded memory | To be Turing-complete, a system must be able to store unbounded memory and having access to the memory. There must be also infinitely many different non-halting programs (like "while" loops or recursion). | ||
=== List of Turing-complete systems === | === List of Turing-complete systems === | ||
| Line 9: | Line 9: | ||
* [[Turing machine]] | * [[Turing machine]] | ||
* Lambda calculus | * [[Lambda calculus]] | ||
* Minsky machine | * [[General Recursive Function|General Recursive Functions]] | ||
* Rule 110 | * [[Minsky machine]] | ||
* [[Fractran]] | |||
* Rule 110 automaton | |||
* Conway's game of life | * Conway's game of life | ||
* 2-Tag system | * 2-Tag system | ||
* Cyclic | * [[Cyclic Tag]] | ||
* Tree | * [[Tree Rewriting System]] | ||
Latest revision as of 16:56, 17 December 2025
A Turing-complete system is a system that can compute every computable function. 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 and having access to the memory. There must be also infinitely many different non-halting programs (like "while" loops or recursion).
List of Turing-complete systems
This list is non-exhaustive.
- Turing machine
- Lambda calculus
- General Recursive Functions
- Minsky machine
- Fractran
- Rule 110 automaton
- Conway's game of life
- 2-Tag system
- Cyclic Tag
- Tree Rewriting System