CPS 460 Computability and Formal Language Theory
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.
Effective Dates:
FS99 - FS99
CSE 460 Computability and Formal Language Theory
Semester:
Fall of every year, Spring of every year
Credits:
Total Credits:
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.
Not open to students with credit in:
CSE 360
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.
Effective Dates:
FS00 - FS13
CSE 460 Computability and Formal Language Theory
Semester:
Fall of every year, Spring of every year
Credits:
Total Credits:
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.
Not open to students with credit in:
CSE 360
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.
Effective Dates:
SS14 - US15
CSE 460 Computability and Formal Language Theory
Semester:
Fall of every year, Spring of every year
Credits:
Total Credits:
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.
Not open to students with credit in:
CSE 360
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.
Effective Dates:
FS15 - US17
CSE 460 Computability and Formal Language Theory
Semester:
Fall of every year
Credits:
Total Credits:
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.
Not open to students with credit in:
CSE 360
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.
Effective Dates:
FS17 - Open