Introduction to Turing Machines and Complexity Technical Seminar Presentation:
The Turing machines are introduced by Alan Turing in the year 1936. It is a model of the computer performing mathematically, which is simple and it is used for computing the capability of the computer. This Turing machine is considered as the comprehensive, most accessible model of computation and their associated theories give us ideas for dealing with complexity issues.
The Turing machine is given by M= (Q, S,τ,δ,q0,B,F) where Q denotes the states which are finite S denotes a set of input symbols, τ represents finite state of tape symbols, where Q0 is Q is the start state, F is the set of final states.
The Turing machine helps in performing computations in a simple and efficient way so that the performance increases by saving the time in calculations. It helps us to solve the complex issues in an easy way.
The church’s hypothesis states are based on the assumption where the computable function is identified with the recursive function which is parallel called church’s hypothesis.
A Turing machine simulates RAM, while the tape is given #0*v0#1*v1#10*v2#………I*vi#……
Where vi is the contents in binary, of the i’th word.
The union theorem states that for {fi(n)|i=1,2,……………..} is a collection of functions. Also assume that for each i and n, fi(n)<fi+1(n). that states that there exists an recursive S(n) such that
DSPACE(S(n))=Ui>1 DSPACE(fi(n)).
We can conclude that the Turing machine is considered as the comprehensive, most accessible model of computation and their associated theories give us ideas for dealing with complexity issues.
Download Turing Machines and Complexity Technical Seminar Presentation with PPT for CSE Students.