User:Azerty/Turing Completeness

From BusyBeaverWiki
< User:Azerty
Revision as of 10:35, 27 December 2025 by Azerty (talk | contribs) (Created page with "This is a list of systems that are Turing-complete. To be Turing-complete, a system must have unbounded memory, access to that memory, and loops that can repeat forever. == Turing-complete systems == * Turing machines with 2 states and a blank tape * Turing machines with 2 symbols and a blank tape * Turing machines with 15 states and 2 symbols * Turing machines with 9 states and 3 symbols * Turing machines with 6 states and 4 symbols * Turing machines with 5 states an...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

This is a list of systems that are Turing-complete.

To be Turing-complete, a system must have unbounded memory, access to that memory, and loops that can repeat forever.

Turing-complete systems

  • Turing machines with 2 states and a blank tape
  • Turing machines with 2 symbols and a blank tape
  • Turing machines with 15 states and 2 symbols
  • Turing machines with 9 states and 3 symbols
  • Turing machines with 6 states and 4 symbols
  • Turing machines with 5 states and 5 symbols
  • Turing machines with 4 states and 6 symbols
  • Turing machines with 3 states and 9 symbols
  • Turing machines with 2 states and 18 symbols
  • Turing machines with 24 instructions

Open problems about Turing-completenesss

  • Min states and symbols count
  • Min instructions count
  • Min move left transitions count
  • Min states with 2 defined transitions and 2 symbols count
  • Min symbols with 2 defined transitions and 2 states count
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:Azerty/Turing_Completeness&oldid=5808"