Page Preview: 85

Course Title[Course Code]:Project[PRO 400]

Faculty: Computers and Artificial Intelligence
Department: Computer Science
Program: Computer Science
Compulsory / Elective:Compulsory
Undergraduate(Forth Year-First Semester)
Lecture:( - ) Practical / Clinical:( 4 ) Tutorial:( 1 )

Course Description:
The course aims at introducing the Church’s thesis: Grammars, the M-recursive functions, and Turing computability of the M-recursive functions. The incompatibility: The halting problem, Turing enumerability, Turing acceptability, and Turing decidability, unsolvable problems about Turing machines and M-recursive functions. Computational complexity: Time-bounded Turing machines. Rate of growth of functions. NP-Completeness. The complexity hierarchy. The prepositional calculus: Syntax, Truth-assignment, Validity and satisfiability. Equivalence and normal forms. Compactness.