turing_machine (720B)
1 # Turing machine 2 3 ## Complexity of problems in this [machine_model] 4 5 [petersen2008sorting]: bounds on complexity of [sorting] 6 - [turing_machine_deterministic] vs [turing_machine_nondeterministic] 7 - one or more work [tapes] (and read-only input) 8 9 ## Types 10 11 - [turing_machine_nondeterministic] 12 - [turing_machine_deterministic] 13 14 ## Variants 15 16 - [turing_machine_symmetric] 17 - [turing_machine_weighted] 18 - [turing_machine_multitape] 19 20 ## Resources 21 22 - turingmachinesimulator.com by [martin_ugarte] 23 24 Up: [theoretical_computer_science] 25 26 See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity] 27 28 Aliases: Turing machines