|
|
|
|
home · studies

| Computability |
| Module Type: |
General Foundation |
| Module Code: |
423 |
| Syllabus: |
Models of Computation: Turing machines and Recursive Functions. Equivalence of the models. Unsolvability. Halting Problem. Introduction to proof techniques for unsolvability. Reductions. Rice’s theorem.
Examples using software packages such as Visual Turing, Java Computability Toolkit or JFLAP.
|
| Module Aims-Objectives: |
To understand the basic models of computation, their relations and the limits of computability. Upon completing this module students should be able to:
1.Build simple and complex Turing machines for particular problems.
2.Implement and run these machines in Visual Turing or other software packages
3.Prove given functions, sets and relations to be recursive.
4.To understand the notion of recursive unsolvability, get to know some examples of unsolvable problems and obtain a basic training in simple unsolvability proofs, via reductions or with the use of Rice’s theorem.
|
| Bibliography: |
• "Foundation of Computation", Ch. Hartonas, Ziti Publishing.
|
|
|
|
|
|
|
