User:Azerty/Turing Completeness: Difference between revisions
Jump to navigation
Jump to search
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..." |
|||
| Line 18: | Line 18: | ||
== Open problems about Turing-completenesss == | == Open problems about Turing-completenesss == | ||
* | * Turing machines with minimum states and symbols count | ||
* | * Turing machines with minimum instructions count | ||
* | * Turing machines with minimum move left transitions count | ||
* | * Turing machines with minimum states with 2 defined transitions and 2 symbols count | ||
* | * Turing machines with minimum symbols with 2 defined transitions and 2 states count | ||
Revision as of 10:37, 27 December 2025
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
- Turing machines with minimum states and symbols count
- Turing machines with minimum instructions count
- Turing machines with minimum move left transitions count
- Turing machines with minimum states with 2 defined transitions and 2 symbols count
- Turing machines with minimum symbols with 2 defined transitions and 2 states count