# Theory of Computation: Question Set – 30

#### What is the difference between P and NP?

P is the class of decision problems that can be solved in polynomial time by a deterministic Turing machine, while NP is the class of decision problems that can be solved in polynomial time by a non-deterministic Turing machine. It is currently unknown whether P equals NP, but the question is one of the most important open problems in computer science.

#### What is the difference between a Turing machine and a register machine?

A Turing machine is a theoretical model of a computer that consists of a tape, a head that can read and write symbols on the tape, and a finite set of states that control the machine’s behavior. A register machine is a theoretical model of a computer that has a finite number of registers, each of which can store a finite number of integers, and a finite set of instructions that can manipulate the registers. While Turing machines can simulate register machines, register machines cannot simulate Turing machines in general.

#### What is the difference between a recursive function and a recursive enumerable function?

A recursive function is a function that can be computed using a Turing machine that always halts, while a recursive enumerable function is a function that can be computed using a Turing machine that may not always halt. Recursive functions are a subset of recursive enumerable functions, as any function that can be computed using a Turing machine that always halts can also be computed using a Turing machine that may not always halt.

#### What is the difference between a context-sensitive grammar and a context-free grammar?

A context-sensitive grammar is a formal system that generates context-sensitive languages, which are a proper superset of context-free languages. Context-sensitive grammars use rules that can modify symbols in the input string based on the context in which they appear, while context-free grammars use rules that replace nonterminal symbols with sequences of terminal and nonterminal symbols. Context-sensitive grammars are more powerful than context-free grammars, as they can generate languages that cannot be generated by context-free grammars.

#### What is the difference between a recursive language and a recursively enumerable language?

A recursive language is a language that can be recognized by a Turing machine that always halts with a correct output, while a recursively enumerable language is a language that can be recognized by a Turing machine that may not always halt with a correct output. Recursive languages are a subset of recursively enumerable languages, as any language that can be recognized by a Turing machine that always halts with a correct output can also be recognized by a Turing machine that may not always halt with a correct output.

#### What is the difference between a universal Turing machine and a standard Turing machine?

A universal Turing machine is a theoretical model of a computer that can simulate any other Turing machine on any input, while a standard Turing machine is a theoretical model of a computer that can only recognize the languages that can be recognized by a finite automaton. Universal Turing machines are more powerful than standard Turing machines, as they can simulate any algorithm that can be performed on any other Turing machine.

#### What is the difference between a pushdown automaton and a finite automaton?

A pushdown automaton is a theoretical model of a computer that has a finite control unit, a tape, and a stack, while a finite automaton is a theoretical model of a computer that only has a finite control unit and a tape. Pushdown automata can recognize context-free languages, which are a proper superset of regular languages, while finite automata can only recognize regular languages.

#### What is the difference between a one-way function and a trapdoor function?

A one-way function is a function that is easy to compute in one direction, but computationally infeasible to compute in the opposite direction, without knowledge of some secret information. A trapdoor function is a one-way function that also has a secret “trapdoor” that can be used to efficiently compute the function in the opposite direction. Trapdoor functions are used in many cryptography applications, such as public-key encryption.