Live briefing
Everything about Nondeterministic Turing machine
Theoretical model of computation
In theoretical computer science and computational theory, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike the standard, deterministic, Turing machine. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Nondeterministic Turing machineA 5-minute orientation
- Pick up a classic book: An introduction to formal languages and automataThe most-reprinted book on the subject
- Read the landmark paper: Combinatorial lower bound arguments for deterministic and nondeterministic Turing machinesCited 43 times
- Go sideways: Complexity classA closely related topic
- Go sideways: Probabilistic Turing machineA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines
On the structure of one-tape nondeterministic turing machine time hierarchy
On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape turing machines
A relationship between nondeterministic Turing machines and 1-inkdot turing machines with small space
Improved simulation of nondeterministic Turing machines
A note on multi-inkdot nondeterministic Turing machines with small space
A nondeterministic Turing machine variant to compute functions
Uniform simulations of nondeterministic real time multitape turing machines
📚 Books worth reading
An introduction to formal languages and automataPeter Linz · 1990
Introduction to automata theory, languages, and computationJohn E. Hopcroft, Jeffrey D. Ullman · 1979
Languages and machinesThomas A. Sudkamp · 1988
Theory of computationDerick Wood · 1987
Theoretical foundations of computer scienceDino Mandrioli · 1987
Introduction to the theory of computationMichael Sipser · 1996
Logic and Language Models for Computer ScienceHenry Hamburger · 1997- 📕Applied Integer Linear ProgrammingAdam Furmanek · 2021
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Complexity class In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly…
- Probabilistic Turing machine In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at…
- Pushdown automaton In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown…
- Two-way finite automaton In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input. A two-way…
- Queue automaton A queue machine, queue automaton, or pullup automaton is a finite-state machine with the ability to store and retrieve data from an infinite-memory queue…
- Alternating Turing machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations…
- Read-only Turing machine A read-only Turing machine or two-way deterministic finite-state automaton (2DFA) is class of models of computability that behave like a standard Turing…
- Automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in…