Elements of Computability DCS 212
QMUL - Winter 2004
- Two lectures each week, Tuesday at 16-17 and Friday at 10-11
- Homework discussion Tuesday at 17-18
- Office hours: Thursday 2:30 - 4:30
(look at Email for possible cancellations)
- Teaching Assistant: Dr Kurt Ranalter.
Office hours on Wednesday, 2 - 4, rook 420.
Email contact: kurt@dcs.qmul.ac.uk
- You need to do a certain number of homework assignments -
assigned on Friday [or Tuesday], due next Friday [or Tuesday].
The number of required homeworks will be specified later.
Coursework will be worth 30% of the final mark;
Exam will be worth 70% of the final mark.
G.S.Boolos, J.P.Burgess and R.C.Jeffrey Computability
and Logic Fourth Edition, Cambridge UP 2002 ISBN 0521 00758 5 paperback
Also to consult:
J.E.Hopcroft, R.Motwani and J.D.Ullman Introduction
to Automata Theory, Languages, Logic and Computation 2nd Edition,
Addison Wesley ISBN 0 201 44124 1
P.Cohn Algebra, Vol 1, Chapters 1 and 2.
Handouts.
Prerequisites: Sets, Relations, Orderings, Functions, Cardinality,
Proofs by induction, etc.
Russell's paradox. Cardinality of N, Z, Q and R.
Cantor's theorem.
Read Chapters 1 and 2 of textbook.
Primitive recursive functions and relations. Ackermann function.
Read Chapters 6 and 7 of textbook.
Look at Handout 3 and at Cohn, Algebra, Vol 1, Chapter 2
- Weeks 6 and 7.
Finite State Machines, Deterministic and Non Deterministic Automata,
Regular Languages,
Pumping Lemma for Regular Languages, Context-free grammars.
Consult J.E.Hopcroft, R.Motwani and J.D.Ullman Introduction
to Automata Theory, Languages, Logic and Computation.
- Weeks 8, 9, and 10.
Turing machines, Turing-computability. Existence of non-Turing computable
functions (argument by cardinality).
Universal Turing Machines. Unsolvability of the halting problem.
Church's thesis. Decidability, semi-decidability, effective enumerability.
Evidence for Church's Thesis. Abacus machines. Turing-computable functions,
Abacus-computable functions and recursive functions are the same class.
Read G.S.Boolos, J.P.Burgess and R.C.Jeffrey Computability and Logic
Chapters 1-8.
- Weeke 11-12.
A brief account of the Completeness Theorem for 1st order logic and of
Tarski's and Goedel's Theorems.
Read Handouts. Consult Boolos, Burgess
and Jeffrey, op.cit. Chapters 9-18.
Handouts:
- Handout 1. Sets, Relations, etc pdf
ps
- Handout 2. Bijections, cardinality, etc pdf
ps
- Handout 3. Ackermann's function pdf
ps
- Handout 4. Pumping Lemma for Regular Languages
pdf ps
- Handout 5. Completeness of 1st order logic
pdf ps
- Handout 6. A Summary of Tarski's and Goedel's theorems
pdf ps
- Homework 1. (due on January 23, 2004): pdf
ps
Extended hints! pdf
ps
- Homework 2. (due on January 30, 2004): pdf
ps
Extended hints! pdf
ps
- Homework 3. (due on February 6, 2004): pdf
ps
Solutions:pdf ps
- Homework 4. (due on February 20, 2004): pdf
ps
Extended hints! pdf
ps
- Homework 5. (due on February 27, 2004): pdf
ps
- Homework 6. (due on March 12, 2004): pdf
ps
- Homework 7. (due on April 2, 2004): pdf
ps Hints!pdf
ps
Here are solutions to some questions of Homework 7:
pdf
ps
FINAL EXAM 2002 with solutions!!!
pdf ps
MOTTO:
No question is too stupid to be asked! (at least once)
TRADUZIONE ITALIANA: Il saggio sa di non sapere nulla,
il dotto sa meno di quel che crede, il furbo sa tutto!