This site uses cookies. By continuing to use this site, closing this banner, or clicking "I Agree", you agree to the use of cookies.
Read our cookies policy and privacy statement for more information.

×
Stand with UkraineDonate

Morehead State University Course Info

Morehead, Kentucky

Favorite

Course Info

Search for courses by clicking on letters of the alphabet or by using a search bar. Explore course description, number of credits required and course sequences to satisfy graduation requirements.


MATH 400

Foundations of Computability

This course is an introduction to fundamental questions of computer science, mathematics and philosophy of mathematics. In particular, it is an analysis of the capabilities and limitations of computability, logic and mathematical proof. Topics include finite automata and regular languages, pushdown automata and context-free languages, the Church-Turing thesis, decidability and the Halting Problem, Gdel's Incompleteness Theorems, the Axiom of Choice and some variants and an introduction to complexity classes and NP-completeness

Units: 3.0

Hours: 3-0-3

Prerequisites:
MATH 300 - Introduction to Mathematical Proofs
or
CS 310 - Algorithms and Advanced Data Structures