Description:
Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. The relationships among various models of computation, language classes, and problems. Church's thesis and the limits of computability. Proofs of program properties including correctness.
Semester:
Fall of every year, Spring of every year
Credits:
Total Credits: 3 Lecture/Recitation/Discussion Hours: 3
Restrictions:
Open only to students in the Department of Computer Science and Engineering or Computer Engineering major or LBS Computer Science coordinate major or the LBS Computer Science field of concentration or the Computer Science disciplinary teaching minor.
Description:
Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. The relationships among various models of computation, language classes, and problems. Church's thesis and the limits of computability. Proofs of program properties including correctness.
Semester:
Fall of every year, Spring of every year
Credits:
Total Credits: 3 Lecture/Recitation/Discussion Hours: 3
Restrictions:
Open to students in the Department of Computer Science and Engineering or in the Computer Engineering Major or in the Lyman Briggs Computer Science Coordinate Major or in the Lyman Briggs Computer Science Major or in the Computer Science Disciplinary Teaching Minor.
Description:
Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. The relationships among various models of computation, language classes, and problems. Church's thesis and the limits of computability. Proofs of program properties including correctness.
Semester:
Fall of every year, Spring of every year
Credits:
Total Credits: 3 Lecture/Recitation/Discussion Hours: 3
Restrictions:
Open to students in the Computer Engineering Major or in the Computer Science Major or in the Lyman Briggs Computer Science Coordinate Major or in the Lyman Briggs Computer Science Major or in the Computer Science Disciplinary Teaching Minor.
Description:
Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. The relationships among various models of computation, language classes, and problems. Church's thesis and the limits of computability. Proofs of program properties including correctness.
Semester:
Fall of every year
Credits:
Total Credits: 3 Lecture/Recitation/Discussion Hours: 3
Restrictions:
Open to juniors or seniors in the College of Engineering or in the Computer Science Minor or in the Lyman Briggs Computer Science Coordinate Major or in the Lyman Briggs Computer Science Major or in the Computer Science Disciplinary Teaching Minor.
Description:
Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. The relationships among various models of computation, language classes, and problems. Church's thesis and the limits of computability. Proofs of program properties including correctness.