The final will consist of a Test 3 section plus material from the previous two outlines.
Outline of Material for Test #3, CS8813, Fall 2001
Turing Machines, Recursively Enumerable Languages, and Undecidability
- Background Definitions
- Be able to define a Turing Machine as described on page 319
- Be able to define and use an ID for a TM (page 320)
- Be able to define the language accepted by a TM, L(TM) (page 326)
- Be able to define RE languages.
- Be able to define recursive languages.
- Be able to describe and use transition diagrams for Tm's
- Be able to define and describe the operation of a multi-tape Turing machine.
- Be able to define and describe the operation of a non-deterministic Turing Machine (NTM).
- Be able to define the Diagonalization Language, Ld.
- Be able to define the Universal Language, Lu.
- Be able to define a property of RE languages.
- Be able to define/describe what it means to reduce one problem to another.
- Be able to define the Posts Correspondence Problem (PCP).
- Be able to define the Modified Posts Correspondence Problem (MPCP).
- Be able to define P, NP, NP-complete, and NP-hard.
- Constructions
- Be able to show how state storage or multiple tracks can be simulated by a TM.
- Be able to build a TM to recognize languages or perform computations similar to homework assignments.
- Be able to show that a multi-tape TM can be simulated by a TM.
- What is the running time of the multi-tape to single tape TM construction?
- Be able to describe how a TM can simulate a NTM (and thus that NTM's are no more powerful that TM's).
- Be able to show how a semi-infinite tape TM can simulate a TM.
- Be able to describe how a three counter machine can simulate a TM.
- Be able to describe how a two counter machine can simulate a three counter Machine.
- Be able to describe how a computer can simulate a TM. What is the difficult part of performing this simulation realistically?
- Be able to describe how a Turing machine can simulate a computer.
- What is the running time cost of simulating a computer on a Turing machine? Why is this question important?
- Be able to show how to encode a Turing machine as a string of 0's and 1's. (page 369)
- Be able to describe how a TM can simulate a TM from its binary code described above.
-
- Be able to reduce one problem to another for problems similar to ones covered in the text.
- Be able to provide the construction for reduction of the MPCP to PCP. Page 396
- Be able to provide the construction for the reduction of Lu to the MPCP. Page 398.
- Be able to provide the construction for showing that detecting ambiguity in CFG's is undecidable.
- Proofs, Contradictions, and Demonstrations
- Be able to prove that the complement of a recursive language is recursive.
- Be able to prove that if a language and its complement are RE then L is recursive
- Be able to prove that Ld is not RE.
- Be able to prove that Lu is RE.
- Be able to prove that Lu is not recursive
- Be able to prove Lne is RE.
- Be able to prove Lne is not recursive.
- Be able to prove that Le is not RE.
- Be able to apply Rice's theorem to demonstrate that properties of TM's are undecidable.
- Be able to prove that detecting ambiguity in CFG's is undecidable.
- Review All Homework!