21-08-2012, 04:01 PM
TURING MACHINES AND COMPLEXITY
TURING MACHINES.ppt (Size: 80 KB / Downloads: 32)
INTRODUCING TURING MACHINES
Introduced by Alan Turing in 1936.
A simple mathematical model of a computer.
Models the computing capability of a computer.
TYPES OF TURING MACHINES
Two way infinite tape
Multiple Turing Machines
Nondeterministic Turing machines
Multidimensional Turing machines
Multihead Turing Machines
Off-line Turing machines
CHURCH’S HYPOTHESIS
The assumption that the intuitive notion of “computable function” can be identified with the class of partial recursive function is known as church’s hypothesis or the church –Turing thesis
Example-Random Access Memory…..
COMPUTATIONAL COMPLEXITY
Some useful worst-case complexity classes:
DTIME(t(n)): languages accepted by a deterministic Turing Machine in time O(t(n)).
NTIME(t(n)): languages accepted by a nondeterministic Turing Machine in time O(t(n)).
DSPACE(s(n)): languages accepted by a deterministic Turing Machine in space O(s(n)).
NSPACE(s(n)): languages accepted by a nondeterministic Turing Machine in space O(s(n)).