turing_machine (764B)
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 - [turing_machine_read_once] 20 21 ## Resources 22 23 - turingmachinesimulator.com by [martin_ugarte] 24 25 Up: [theoretical_computer_science] 26 27 See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity], [busy_beaver] 28 29 Aliases: Turing machines