Computability

Code:

CC333

Acronym:

CC333

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2009/2010 - 1S

Active?	Yes
Responsible unit:	(X) Departamento de Ciência de Computadores
Course/CS Responsible:	Bachelor in Geology

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:AST	0	Plano de Estudos a partir de 2008	3	-	7,5	-
L:B	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:CC	40	Plano de estudos de 2008 até 2013/14	2	-	7,5	-
			3
L:F	0	Plano de estudos a partir de 2008	3	-	7,5	-
L:G	0	P.E - estudantes com 1ª matricula anterior a 09/10	3	-	7,5	-
		P.E - estudantes com 1ª matricula em 09/10	3	-	7,5	-
L:M	0	Plano de estudos a partir de 2009	3	-	7,5	-
L:Q	0	Plano de estudos Oficial	3	-	7,5	-

Teaching language

Portuguese

Objectives

Study and comparison of different (Turing-complete) models of computation, their computational power and limitations.

After completing this course students are expected to

- know the classical models of computation;
- be able to prove the equivalence of several Turing-complete models;
- know the fundamental results and methods used in the study of computability;
- be able to classify concrete examples of problems and prove their (un)decidability within several classes of computability.

Program

Language, functions and (semi-)decidable problems. Revision of some models of computation ( (DFA's, NFA's, CFL's and
PDA's) and their computational power. Register machines. Church-Turing thesis. Chomsky's hierarchy. Study of different Turing-complete models of computation (Turing machines, Recursive functions and lambda-calculus) and their equivalence. Effective enumerability of instances of a model of computation. Recursive and recursively enumerable languages. Diagonalization method and undecidability of the halting problem. Reduction 'many to one' between languages. Undecidability of theories of first order logic. Other undecidable problems.

Complementary Bibliography

Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani and Ullmann.
Recursion theory, Phillips, in Handbook of logic in computer science (vol. 1), Oxford University Press.
Foundations of Functional Programming, Lawrence C Paulson, www.cl.cam.ac.uk/~lp15/papers/Notes/Founds-FP.pdf
Computabilidade e Decidibilidade, Sabine Broda.
Introduction to the Theory of Computation, Michael Sipser.
Models of Computation - An Introduction to Computability Theory, Maribel Fernández.

Evaluation Type

Evaluation with final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	70,00
	Total:	-	0,00