User:Azerty/Turing Completeness

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