Theoretical Computer Science
Theory has become the discipline that bounds AI claims: undecidability, reduction, and complexity results determine what automated verification can never guarantee, while formal language theory and information theory underpin constrained decoding, output validation, and tokenization. The course keeps its classical content intact but reframes proof and counterexample as the professional skill for accepting or rejecting work a human did not personally write.
Current catalog prerequisites — (CSC 300 or 4400).
Current description → proposed description
This course provides the student the opportunity to explore the Grand Ideas of computer science in a systematic way. Senior computer science students will be exposed to a variety of fundamental computer science concepts within a sound philosophical framework. Current events and small scale projects will augment and reinforce computer science concepts. The senior computer science assessment examination will be administered in this course. Topics include, Boolean Algebra and logic, Finite State Machines, grammars, correctness proofs, Turing Machines, analysis and discovery of algorithms, Finite Automata, coding and information theory, and aspects of creation. Students are challenged to explore the relationship between a Christian worldview and the fundamental concepts of computer science and technology.
Prerequisites: (CSC 300 or 4400).
This senior course invites students to explore the Grand Ideas of computer science within a systematic and philosophically grounded framework. Topics include Boolean algebra and logic, finite state machines and finite automata, formal grammars, correctness proofs, Turing machines, computability and complexity, the analysis and discovery of algorithms, and coding and information theory. The course treats these foundations as the instruments by which claims about intelligent systems are tested: undecidability and complexity results bound what any automated verifier or reasoning agent can guarantee, formal language theory explains constrained generation and parser-level validation of machine output, and entropy and source coding illuminate tokenization, compression, and the predictive behavior of generative models. Students practice proof, reduction, and counterexample as the discipline for accepting or rejecting work they did not write themselves. Throughout, they examine the relationship between a Christian worldview and computation, considering creation, human creativity, the limits of formal systems, and the accountability that remains with the person who deploys a system that generates code or text. The senior computer science assessment examination is administered in this course.
What changes
- Computability and complexity framed as hard limits on automated verification
- Formal language theory tied to constrained generation and parser-level output validation
- Information theory connected to tokenization, compression, and model perplexity
- Proof, reduction, and counterexample as the standard for accepting AI-generated work
- Christian reflection on creation extended to machine creativity and personhood claims
6 proposed outcomes, mapped to 9 program outcomes
Each outcome below is written to be observable and assessable, and each is mapped to the program learning outcomes for which it produces evidence.
Students will be able to construct formal proofs of correctness, language classification, and decidability for programs and grammars, including artifacts produced by automated code generators, using Boolean logic, formal grammars, finite automata, and Turing machine models.
The CLO requires students to draw defensible conclusions about machine-generated artifacts by formal analysis, which is the qualitative analytical work PLO 6.2 names, with the proof itself as the evidence.
Students will be able to evaluate claims that an automated tool can verify, decide, or optimize a given class of problem, applying undecidability, reduction, and complexity-class results to determine which guarantees are obtainable in principle and which are not, and to assess the societal risk of deploying systems whose safety or correctness guarantees are asserted rather than proved.
Testing a proposed automated solution against what reduction and complexity results show is obtainable in principle is the evaluative half of PLO 4.2, and the CLO's explicit clause on the societal risk of deploying systems with asserted rather than proved guarantees is the ethical and societal analysis required by PLO 4.1.
Students will be able to analyze the asymptotic time and space complexity of algorithms they design and of implementations produced by AI coding assistants, differentiating proved guarantees from empirical benchmark performance and selecting invariants, counterexamples, and property-based tests proportionate to the strength of the claim being made.
Deriving asymptotic bounds for machine-produced implementations to reach conclusions about their behavior is the quantitative analysis PLO 6.2 describes, and separating benchmark numbers from proved properties is the accurate interpretation and explanation of AI outcomes named in PLO 6.1.
Students will be able to analyze the information-theoretic foundations of computation, including entropy, source coding, and channel capacity, and their bearing on tokenization, compression, and the predictive behavior of generative language models.
Explaining entropy and source coding as the basis of tokenization and perplexity equips students to interpret and explain AI outputs (PLO 6.1), and the CLO's quantitative work with information measures to reach conclusions about model behavior is the analysis described in PLO 6.2.
Students will be able to articulate, in writing and in an oral presentation to a non-specialist audience, why a given computational problem is intractable or undecidable and what that implies for the promises made on behalf of autonomous systems.
The CLO names both a written artifact and an oral presentation explaining what is and is not provable, which is the written and spoken communication required by PLO 5.1, and it directs that explanation to a non-specialist audience, which is the translation of technical AI knowledge for informed public judgment in PLO 5.3.
Students will be able to critique, from a Christian worldview, claims about machine creativity, intelligence, and personhood in light of the limits of formal systems and the accountability that remains with them as practitioners for work they deploy but did not write.
The critique is grounded in biblical teaching on creation and the image of God as it bears on claims of machine creativity (PLO 1.1), the CLO's first-person clause asks students to evaluate their own accountability as practitioners who deploy generated work, which is the stewardship and vocation of PLO 1.3, and the assessment of claims of machine intelligence and personhood is the moral evaluation of AI developments in PLO 6.3.
Program outcomes this course reaches
Filled cells are program learning outcomes with at least one supporting course learning outcome in this course. Sparse coverage is expected — no single course carries all eighteen.