Theory Of Computation

?
What is a Universal Turing Machine?
A Universal Turing Machine is a TM that can simulate the computations performed by an arbitrary TM.
1 of 9
State the Halting Problem?
Given TM M, with alphabet Σ, together with u∈Σ*, will the computation of M with input u halt?
2 of 9
What does your answer say about the limits of computation?
There are well formed computational questions whose answers cannot be computed (using a TM).
3 of 9
What would we prove about complexity classes if we discovered a polynomial time algorithm for finding satisfying truth assignments to 3SAT problems?
3SAT is an NP-complete problem, hence we have a polynomial time algorithm for solving an NP complete problem, hence P and NP would be the same class of problem.
4 of 9
State the halting problem? Is it Decidable?
Given TM M, with alphabet Σ, together with u∈Σ*, will the computation of M with input u halt? It is not decidable
5 of 9
State Church's Thesis?
An algorithmic procedure that can be carried out by a human being or by a computer can be carried out by a Turing Machine. (and vice versa).
6 of 9
Define the complexity of P?
A language L is in P if there is a deterministic Turing Machine that decides it with time complexity in O(nr) where r is independent of n. The class of all languages decidable in non-deterministic polynomial time is denoted P.
7 of 9
Define the complexity of NP?
A language L is in NP if there is a non-deterministic Turing Machine that decides it with time complexity in O(nr) where r is independent of n. The class of all languages decidable in non-deterministic polynomial time is denoted NP.
8 of 9
Define NP - Complete?
A language L is said to be NP-complete if L∈NP and every language L’∈NP is polynomial-time reducible to L.
9 of 9

Other cards in this set

Card 2

Front

State the Halting Problem?

Back

Given TM M, with alphabet Σ, together with u∈Σ*, will the computation of M with input u halt?

Card 3

Front

What does your answer say about the limits of computation?

Back

Preview of the front of card 3

Card 4

Front

What would we prove about complexity classes if we discovered a polynomial time algorithm for finding satisfying truth assignments to 3SAT problems?

Back

Preview of the front of card 4

Card 5

Front

State the halting problem? Is it Decidable?

Back

Preview of the front of card 5
View more cards

Comments

No comments have yet been made

Similar Computing resources:

See all Computing resources »See all Theory of Computation resources »