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
1 of 5
State the halting problem
Given TM M, with alphabet Σ, together with u∈Σ*, will the computation of M with input u halt?
2 of 5
What is a Universal Turing Machine
A Universal Turing machine is TM that simulates the computations performed by an arbitrary turing machine.
3 of 5
State a consequence of 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
4 of 5
What does your answer say about the limits of computation?
There are well formed computational questions whose answers cannot be computed (using a TM)
5 of 5
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 is a Universal Turing Machine
Back
Card 4
Front
State a consequence of Church’s Thesis
Back
Card 5
Front
What does your answer say about the limits of computation?
Comments
No comments have yet been made