Turing completeness: Difference between revisions
Jump to navigation
Jump to search
m Capitalsisation |
→List of Turing-complete systems: Added sections for TC systems. |
||
| Line 8: | Line 8: | ||
This list is non-exhaustive. | This list is non-exhaustive. | ||
=== [[Turing machine]] === | |||
* [[Lambda calculus]] | |||
* [[SKI Calculus | * Multi-tape | ||
* Multi-headed | |||
* [[Reversible Turing Machine|Reversible]] | |||
=== [[Lambda calculus]] === | |||
* [[SKI Calculus|SK Calculus]] | |||
* [[SKI Calculus]] | * [[SKI Calculus]] | ||
* [[SKI Calculus|BCKW Calculus]] | |||
* [https://esolangs.org/wiki/Iota Iota] | |||
* [https://esolangs.org/wiki/Jot Jot] | |||
=== Other === | |||
* [[General Recursive Function|General Recursive Functions]] | * [[General Recursive Function|General Recursive Functions]] | ||
* [[Minsky machine]] | * [[Minsky machine]] | ||
* [[Fractran]] | * [[Fractran]] | ||
Revision as of 18:34, 16 August 2026
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
- Multi-tape
- Multi-headed
- Reversible
Lambda calculus
Other
- 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