User:Azerty/Turing Completeness
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 symbols and a blank tape
- Turing machines with 2 states 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
- Turing machines with 2 symbols and a blank tape but each state must write the same symbol
- Turing machines with 2 symbols and a blank tape but each state must move in the same direction
- Turing machines with 2 states and a blank tape but each symbol must write the same symbol
- Turing machines with 2 states and a blank tape but each symbol must move in the same direction
- Turing machines with 2 states and a blank tape but each symbol must go to the same state