Turing completeness: Difference between revisions
Jump to navigation
Jump to search
RobinCodes (talk | contribs) m grammar fix |
→Turing machine: Added PAF and TM variations. |
||
| (12 intermediate revisions by 3 users not shown) | |||
| 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 == | |||
This list is non-exhaustive. | This list is non-exhaustive. | ||
* [[Turing | === [[Turing machine]] === | ||
* Lambda calculus | |||
* | * Multi-tape | ||
* Multi-headed | |||
* [[Reversible Turing Machine|Reversible]] | |||
* [[Terminating Turmite|Turmite]] | |||
* Multi-dimensional tape | |||
* [[Branching Beaver|Branching tape]] | |||
* [[Uniform-action Turing Machine|Uniform-action]] | |||
* [[Semi Infinite Tape Turing Machine|Semi-infinite tape]] | |||
=== [[Lambda calculus]] === | |||
* [[SKI Calculus|SK Calculus]] | |||
* [[SKI Calculus]] | |||
* [[SKI Calculus|BCKW Calculus]] | |||
* [https://esolangs.org/wiki/Iota Iota] | |||
* [https://esolangs.org/wiki/Jot Jot] | |||
=== [[Brainfuck]] === | |||
* [[Boolfuck]] | |||
* [https://esolangs.org/wiki/Bitter Bitter] | |||
* [https://esolangs.org/wiki/Smallfuck Smallfuck] | |||
* [https://esolangs.org/wiki/BitChanger BitChanger] | |||
=== Cellular automata === | |||
* Rule 110 automaton | * Rule 110 automaton | ||
* Conway's game of life | * Conway's game of life | ||
* 2-Tag system | * [[Doodle function|Doodle automaton]] | ||
* Cyclic tag | * [[Pebble Automaton|Pebble automaton]] | ||
* Tree | |||
=== Tag systems === | |||
* [[Post Tag System|2-Tag system]] | |||
* Cyclic tag system | |||
* [[Tag System|Tree Rewriting System]] | |||
* String rewriting system | |||
=== Counter machines === | |||
* [[Minsky machine]] | |||
* [[CounterScript]] | |||
=== Other === | |||
* [[General Recursive Function|General Recursive Functions]] | |||
* [[Fractran]] | |||
* [[Wang Tiles|Wang tiles]] | |||
* [[Diophantine Equation|Diophantine equations]] | |||
* [[Piecewise Affine Function|Piecewise affine function]] | |||
== See Also == | |||
Wikipedia article about computability: https://en.wikipedia.org/wiki/Computability | |||
Latest revision as of 20:05, 20 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
- Uniform-action
- Semi-infinite 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