Turing completeness

From BusyBeaverWiki
Revision as of 09:35, 17 December 2025 by Azerty (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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-exhaustive.

  • Turing machine
  • Lambda calculus
  • Minsky machine
  • Rule 110
  • Conway's game of life
  • 2-Tag system
  • Cyclic tag
  • Tree rewrite system
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Turing_completeness&oldid=5616"