Computability Theory deals with one of the most fundamental questions in computer science, what is computing and what are the limits of what a computer can compute? Or what kind of problems can be algorithmically solved? During the course, this question will be studied. The notion of algorithm or computing will be made precise by using the mathematical model of a Turing machine throughout this course.
Assessment
This course does not involve any written exams. Students need to answer 5 assignment questions to complete the course, the answers will be in the form of written work in pdf or word. Students can write the answers in their own time. Each answer needs to be 200 words (1 Page). Once the answers are submitted, the tutor will check and assess the work.
Certification
Edukite courses are free to study. To successfully complete a course you must submit all the assignment of the course as part of the assessment. Upon successful completion of a course, you can choose to make your achievement formal by obtaining your Certificate at a cost of £49.
Having an Official Edukite Certification is a great way to celebrate and share your success. You can:
- Add the certificate to your CV or resume and brighten up your career
- Show it to prove your success
Course Credit: TU Delft
Course Curriculum
| Module: 01 | |||
| 1. Preliminaries – Automata and Languages | 00:05:00 | ||
| Module: 02 | |||
| 2.A. The Turing machine | 00:05:00 | ||
| 2.B. Variants of Turing machines | 00:05:00 | ||
| 2.C. Non-deterministic Turing machines and their equivalence to ordinary Turing machines | 00:05:00 | ||
| 2.D. Enumerators and Hilbert’s tenth problem | 00:05:00 | ||
| 2.E. The entscheidungsproblem, the Church-turing thesis, and the coding of Turing machines and problems | 00:05:00 | ||
| Module: 03 | |||
| 3.A. Infinity, hotel Hilbert, and countable and uncountable sets | 00:05:00 | ||
| 3.B. Decidable problems, the Halting Problem and its undecidability, and Universal Turing Machines | 00:05:00 | ||
| Module: 04 | |||
| 4.A. Reductions and direct reduction | 00:05:00 | ||
| 4.B. Computable functions and mapping reduction | 00:05:00 | ||
| 4.C. Rice’s Theorem and reductions via computation histories | 00:05:00 | ||
| 5. Self-reproduction | 00:05:00 | ||
| Assessment | |||
| Submit Your Assignment | 00:00:00 | ||
| Certification | 00:00:00 | ||
Course Reviews
No Reviews found for this course.
Related Courses
