COMP0017 Computability and Complexity Theory
http://www0.cs.ucl.ac.uk/staff/F.Zanasi/
Lecture one
Copyright By PowCoder代写 加微信 powcoder
1. Practicalities
Part II (15 lectures), taught by
www.cs.ucl.ac.uk/people/M.Sadrzadeh.html/
Computational Complexity Theory
Course Structure Part I (15 lectures), taught by
www.cs.ucl.ac.uk/people/F.Zanasi.html/
Computability Theory
Assessment
One final exam (100%)
Score at least 40% in the exam
Exercise sessions every week Quiz will be made available on Moodle
Two lectures (on Zoom)
Tuesday 15-17 and Friday 13-14 One exercise sheet (on Moodle)
Solutions published after the exercise session
Weekly Appointments
Two exercise sessions (on campus)
GRP1 (Monday 10-11) or GRP2 (Monday 10-11) One exercise session (on Zoom)
GRP2 (Monday 10-11)
Discussion on forums (on Moodle)
Available all week, moderated by the TAs
Teaching assistants Group 1 (GRP1 , Monday 10-11)
Group 2 (GRP2, Monday 10-11)
Group 3 (GRP3, Monday 10-11)
If you have any question, use the Moodle forum for your group. The teaching assistants (and me) will answer you.
What is in the exam?
Anything we discussed during the lectures, unless explicitly stated otherwise.
Content: slides + my explanation (you can use Sipser’s book Introduction to the Theory of Computation, for the technical details and review of what’s in the slides)
Type of questions: similar to the ones presented in exercise sessions and in the quiz, but usually simpler.
Prerequisites Basic Set theory and basic logic
How to write down a clear and rigorous mathematical proof
Proofs by contradiction
Finite state automata, grammars, formal languages
Bibliography
M. Sipser – Introduction to the Theory of Computation
A.J. Kfoury, R. N. Moll, M. A. Arbib – A Programming Approach to Computability
J. Hopcroft, J. Ullman – Introduction to Automata Theory, Languages and Computation
Questions?
2. Overview of the course
What programming languages should I learn? What software should I be able to use?
What professional capabilities should I acquire? What is important in job interviews?
Do you expect that your answer will be the same in 2, 5 or 10 years?
Pressing questions
Pressing questions
Learning is a never-ending process Programming languages will change
Tools will change
The basic concepts will not change
Basic Concepts
What is a computation?
What is a computer?
Are there limits to what a computer can do?
How should we formally approach these questions? How can we prove theorems about them?
What is a computer?
What is a computer? What distinguishes a computer from a non-computer?
What’s the essence of computation?
A theory of computation demands an abstract model of what a computing machine is.
What is a computer?
Aristotle: distinction between the essential and accidental properties of a thing
A chair can be made of wood or metal, but this is accidental to its being a chair: that is, it is still a chair regardless of the material from which it is made.
What is a computer?
Geometry: in order to formally study space, we need to abstract the essential properties of objects
What is a computer?
We will see that this question has many equivalent answers.
It’s a Turing Machine It’s a Register Machine
It’s a WHILE programming language It’s a Recursive function
Church-Turing conjecture: anything that a human can compute following an algorithm can be computed by one of these abstract models.
Basic Concepts
Are there limits to what a computer can do?
Are there limits to what a computer can do?
Can a computer beat the chess world champion?
Can a computer beat the GO world champion?
Can a computer drive a car safely?
Are there limits to what a computer can do?
There are problems that will never be solvable by a computer.
A theory of computation can supply a mathematical proof of this fact.
Unsolvable problems
Will the program P ever crash? Will the program P halt on its input?
Given a program P and a function f, does P compute f? Are any two given programs equivalent?
Unsolvable problems
most problems are undecidable.
(Cantor’s diagonalisation argument).
all the non-trivial universal problems are undecidable. (Rice’s Theorem)
Are we doomed?
No, the trick is to consider restricted classes of a
problem (e.g. replace “halt” with “halt in n seconds”).
More unsolvable problems
Is the given first-order logic formula φ satisfiable?
In algebra
When do two words represent the same element in a group?
More unsolvable problems
In algebra
When a diophantine (= multivariable polynomial) equation has integer solutions
In interior design (!)
Can a given set of tiles used to cover any n×n area?
Unsolvable problems
Unsolvable problems are ubiquitous.
The power of abstraction: the majority has been discovered to be unsolvable before the first computer was ever built.
We will learn how to give a mathematical proof that a certain problem is unsolvable.
Basic Concepts
What is a computation?
What is a computer?
Are there limits to what a computer can do?
What about resources?
A solvable problem may still be untractable (take an
unreasonable amount of time/memory space to be solved)
The second part of the course will focus on the space/ time complexity of solvable problems.
Bibliography, revisited
M. Sipser – Introduction to the Theory of Computation
A.J. Kfoury, R. N. Moll, M. A. Arbib – A Programming Approach to Computability
J. Hopcroft, J. Ullman – Introduction to Automata Theory, Languages and Computation
First week: introduction and the Turing machine
Second week: the Church-Turing thesis and other models of computation
Third week: the universal Turing machine. Undecidable problems in computation (halting and crashing)
Fourth week: Cantor’s diagonal argument and Rice’s theorem
Fifth week: undecidable problems in other fields (tiling problem, undecidability of first-order logic)
What’s next
Our first abstract model of computation:
the Turing machine
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com