Turing completeness: Difference between revisions
Jump to navigation
Jump to search
→Other: Added Diophantine equations |
m Fixed grammar |
||
| Line 3: | Line 3: | ||
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 and | To be Turing-complete, a system must be able to store unbounded memory and have 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 == | ||
Revision as of 09:06, 17 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 have 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
- Turmite
- Multi-dimensional tape
- Branching tape
Lambda calculus
Brainfuck
Cellular automata
- Rule 110 automaton
- Conway's game of life
- Doodle automaton
- Pebble automaton
Tag systems
- 2-Tag system
- Cyclic tag system
- Tree Rewriting System
- String rewriting system
Counter machines
Other
See Also
Wikipedia article about computability: https://en.wikipedia.org/wiki/Computability