User:Azerty/Turing Completeness: Difference between revisions
Jump to navigation
Jump to search
→Turing-complete systems: Added more problems. |
|||
| Line 5: | Line 5: | ||
== Turing-complete systems == | == Turing-complete systems == | ||
* Turing machines with 2 symbols and a blank tape | |||
* Turing machines with 2 states and a blank tape | * Turing machines with 2 states and a blank tape | ||
* Turing machines with 15 states and 2 symbols | * Turing machines with 15 states and 2 symbols | ||
* Turing machines with 9 states and 3 symbols | * Turing machines with 9 states and 3 symbols | ||
| Line 23: | Line 23: | ||
* Turing machines with minimum states with 2 defined transitions and 2 symbols 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 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 | |||
Revision as of 12:40, 29 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 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