Computation Theory: Projects

Project 1 [Post Correspondance Problem]

  1. Define the Post Correspondance Problem (PCP).
  2. In this part you will write an exposition for the proof that PCP is undecidable by reducing the halting problem to this problem. Read through these notes to answer the following questions:
    1. Define the MPCP.
    2. Reduce the MPCP to the PCP problem.
    3. Reduce the Halting problem for Turing Machines to the MPCP.
  3. Using the fact that the PCP is undecidable, show that the following problems (or just a few of these) are undecidable:
    1. Deciding if a CFG is ambiguous.
    2. Deciding if \(L(G_1) \cap L(G_2)\) is empty for \(G_1\) and \(G_2\) CFG languages.
    3. Deciding if \(L(G_1) \neq L(G_2)\) \(G_1\) and \(G_2\) CFG languages.
    4. Deciding if \(L(G) \neq L(R)\) for \(G\) a CFG language and \(R\) a regular language.
    5. Deciding if \(L(G) \setminus L(R)\) for \(G\) a CFG language and \(R\) a regular language.

Project 2 [Origins of Turing Machine]

Read Turing’s first paper on Turing Machines: “On Computable Numbers, with an Application to the Entscheidungsproblem” (1937) (this wikipedia page contains a commentary) and answer the following questions:

  1. Which of the theorems of the paper appeared in your course?
  2. Which of the definitions are different? In what ways?

Note: You do not have to go over the entire paper.

Project 3 [Emulation time of multi-tape Turing Machines]

  1. Show that multi-tape Turing Machines are equivalent to Turing Machines (if you did not do this as part of Supervision 2).
  2. Show that for a multi-tape Turing Machine requiring \(T(n)\) time to terminate, there exists an equivalent TM that takes \(\mathcal{O}(T(n)^2)\) time to terminate, where \(T(n)\) is the time the multi-take .
  3. (optional) Read the “On the Computational Complexity of Algorithms” paper by Hartmanis and Stearns for more details (and look at the palindrome project for why this is tight).
  4. (+) Read the “Two-tape simulation of multitape Turing machines” paper by Hennie and Stearns to see how to emulate any multi-tape TM using \(\mathcal{O}(T(n) \log T(n))\) time using a \(2\)-tape TM.

Project 4 [Palindrome lower bound]

In this project, you will investigate the \(\Omega(n^2)\) worst-case lower bound on the time to determine if a string is a palindrome. Read these notes or the paper by TODO and answer the following questions:

  1. Why does this have to be a \textit{worst-case} lower bound?
  2. What is the high-level argument for the proof?
  3. Write an exposition for the formal proof.

Project 5 [Palindrome lower bound multi-tape machine]

In this project you will investigate the lower bound on the time and space for deciding the palndrome problem in a multi-tape TM.

Read the “The recognition problem for the set of perfect squares” paper by Cobham and write an exposition for why every Turing Machine that recognises the palindrome language in \(S\) space and \(T\) time, must have \(S \cdot T = \Omega(n^2)\). (Read this thread for guidance)

Project 6 [Finding all palindromes in a string in linear time]

This project is tangentially related to Computation Theory. You will investigate an efficient algorithm for finding all palindromes in a string.

  1. Design an \(\mathcal{O}(n^3)\) algorihtm for finding all palindromes in a given string.
  2. By considering each element \(i\) as a potential center of a palindrome improve your algorithm to run in \(\mathcal{O}(n^2)\) time.
  3. Which parts of your algorithm in (2) are doing extra work? Can you avoid this? Before reading further try to improve the runtime of your algorithm.
  4. Read about Manacher’s algorithm from this article, the original paper or any good article you find online.

Project 7 [Word RAM model and sorting]:

In this project you will investigate a model that more accurately represents modern computers. It is called the word RAM model.

  1. Read through the introduction of “Blasting through the information theoretic barrier with fusion trees” (or these notes) and describe the model.
  2. Read through the introduction of “Deterministic sorting in \(\mathcal{O}(n \log \log n)\) time and linear space” to learn about more efficient algorithms for sorting in the word RAM model.

Various project ideas: