Turing completeness: Difference between revisions
Jump to navigation
Jump to search
→List of Turing-complete systems: Add Fractran |
Added See Also category |
||
| Line 5: | Line 5: | ||
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). | 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. | This list is non-exhaustive. | ||
* [[Turing machine]] | * [[Turing machine]] | ||
* [[Lambda calculus]] | * [[Lambda calculus]] | ||
* SK calculus | |||
* [[General Recursive Function|General Recursive Functions]] | * [[General Recursive Function|General Recursive Functions]] | ||
* [[Minsky machine]] | * [[Minsky machine]] | ||
| Line 18: | Line 19: | ||
* [[Cyclic Tag]] | * [[Cyclic Tag]] | ||
* [[Tree Rewriting System]] | * [[Tree Rewriting System]] | ||
* Brainfuck | |||
== See Also == | |||
Wikipedia article about computability: https://en.wikipedia.org/wiki/Computability | |||
Latest revision as of 13:21, 22 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
- SK calculus
- General Recursive Functions
- Minsky machine
- Fractran
- Rule 110 automaton
- Conway's game of life
- 2-Tag system
- Cyclic Tag
- Tree Rewriting System
- Brainfuck
See Also
Wikipedia article about computability: https://en.wikipedia.org/wiki/Computability