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..." |
|||
| (2 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
== Turing-complete systems == | == Turing-complete systems == | ||
* Turing | * 2-symbol Turing machine on a blank tape | ||
* Turing machines with 2 | * Uniform-action Turing machines with 2 states and a blank tape | ||
* | * 15-state 2-symbol Turing machine | ||
* | * 9-state 3-symbol Turing machine | ||
* | * 6-state 4-symbol Turing machine | ||
* | * 5-state 5-symbol Turing machine | ||
* | * 4-state 6-symbol Turing machine | ||
* | * 3-state 9-symbol Turing machine | ||
* | * 2-state 18-symbol Turing machine | ||
* Turing machines | * 24-instruction Turing machines | ||
== 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 | ||
* 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 go to the same state | |||
Latest revision as of 15:15, 1 January 2026
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
- 2-symbol Turing machine on a blank tape
- Uniform-action Turing machines with 2 states and a blank tape
- 15-state 2-symbol Turing machine
- 9-state 3-symbol Turing machine
- 6-state 4-symbol Turing machine
- 5-state 5-symbol Turing machine
- 4-state 6-symbol Turing machine
- 3-state 9-symbol Turing machine
- 2-state 18-symbol Turing machine
- 24-instruction Turing machines
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 go to the same state