Instructors: Dr. Antonio Tomeu & Dr. Alberto Salguero, members of the Computer Science Department. University of Cadiz (Spain).

This course provides the answer to three questions about the nature of computation:

 

• What is a computer and what is not a computer?

• What problems can computers solve and what problems can computers never solve?

• What problems can computers solve efficiently and what problems can computers never solve efficiently?

 

Course textbook: Computability, Complexity and Languages; by Martin Davis, Ron Sigal and Elaine Weyuker. Get the second edition.

Semester: 5

 

 

 

Lectures:

1. Models of Computation: definition, utility and limits. Computable Functions.

2. Recursive Functions Theory.

3. Universality.

4. Computing with Strings.

5. Turing-computability.

6. Other Related Models: PRAM, Cellular Automata...

 

​

Slides (Credits: Mr. Alberto García Gonzélez, assistant student, this material is old-fashion):

1. Models of Computation: definition, utility and limits. Computable Functions (slides).

2. Recursive Functions Theory (slides).

3. Universality (slides).

4. Computing with Strings (slides).

5. Turing-computability (slides).

6. Other Related Models (slides).

​

 

 

Problems Sheets:

1. Sheet 1

2. Sheet 2

3. Sheet 3

4. Sheet 4

 

 

 

Practical Sessions & Homeworks

 

1. Working with L-Model Simulator ILC

2. Computable Functions and Predicates with ILC

3. S-Model Miicrointerpreter 

4. Working with URM-Model Simulator

5. URM-Model Miicrointerpreter

6. Computability with a 2D Cellular Automata: Conway's Game Life

7. The REC Functions Class in ILC

8. Is the Mandelbrot Set recursive?

9. Working with a Turing-Machines Simulator: JFLAP

​

 

 

Exams:

1. Theoretical Exam (model).

2. Practical Exam (model).

​

 

 

Software:

1. ILC (Interpreter for L Model Computation)

2. JFLAP (A Turing-machine Simulator)

3. URM (An Unlimited Registers Machine Simulator)

4. Applet to Simulate Turing Machines

5. Applet to Simulate Cellular Automata

 

 

 

Office Hours: coming soon...

 

 

 

Grading:

1. Partial Exams: 4 points.

2. Homeworks: 3 points.

3. Final Work: 1 point.

4. Presentation (oral) of Final Work: 1 point.

5. Contributions to glossary/wiki of the course: 1 point