Purpose
This homework includes problems on Turing machines, equivalence of computational models, decidability, and recognizability.
Background
For this assignment, you should - read and write formal notation - recall the definition of a Turing Machine in various forms: high-level, implementation-level, and formal - design and describe a Turing machine - prove equivalence of a variant with a Turing machine - recall the definition of a decidable language - recall the definition of a recognizable language - recall the definition of a language - recall the Chomsky hierarchy of languages - argue about the decidability and recognizability of a given languages
The Problem Set
The problems are in hw3.tex which is to be compiled using a LaTeX compiler.
Submission
There are 2 parts to this assignment.
3.1 Solving the Problem Set
This is a team submission on GitHub and contributes to your Submission Score.
3.2 Feedback
Grading
Your submission will be graded for correctness of your solutions. Files that do no compile cannot be graded.
Your individual score in this homework is the product of your Submission Score and Team Factor.
Discussion
Please use the following avenues:
discuss with your buddy, the discussion forum on LMS, discuss with your peers, consult with course staff.
