Introduction

Part 1: Building Computers

Download (and unzip) TMCM labs
See xLogicCircuits Lab 1
Basic Gates: Not, Or, And
Simple Circuits: 5-Gate XOR
Your turn: 4-Gate XOR
Boolean Logic + Truth Tables
Disjunctive Normal Form (DNF)
So... Boolean Logic is Computable
Your turn: 2-of-3 in DNF
What about Arithmetic?
1. Integers in Binary
2. Binary Arithmetic As Logic!
3. Example: One-Bit Adder ("Half Adder")
4. Your turn: One-Bit Subtracter with Signed Output
5. Full Adder (three 1-bit numbers in, one 2-bit number out)
6. 4-Bit Adder (Daisy-Chained Adders)
More Advanced Circuits: Memory, Clocks, etc...
And you have... A Digital Computer!!!

Part 2: Programming Computers

Machine Language + Assembly Language (see xComputer Labs)
Higher-Level Programming Languages (See xTurtle Labs and xModels Labs)
Modern, Professional Programming Language (Java, C++, Python, Ruby, etc...)
Java examples
1. HelloWorld.java and IsPerfect.java (see Wikipedia page on Perfect Numbers)
2. Getting Started with Java
3. Getting Stated with Graphics
4. Getting Started with Events (requires JComponentWithEvents.class)

Part 3: Analyzing Computers

Time Complexity (how long will a program run?)
1. See xSortLab
2. selectionsort versus mergesort?
Computability
1. Church-Turing Thesis:
  1. If a problem is computable, then it can be computed on a Turing Machine
  2. Corollary: All "Turing-Equivalent" machines / languages (ie, basically all of them) are equally powerful.
2. See xTuringMachineLab
3. Halting Problem Warm-up:
  1. Use Cantor's Diagonal Argument to prove that |R| > |Z|
    (we say the real numbers are not "countable" -- so there are multiple infinities!)
  2. Same technique can prove Cantor's Theorem (that |power set of Z| > |Z|)
  3. Related to: Goedel's Incompleteness Theorem
4. The Halting Problem
  1. It is impossible to determine if a given program will halt over any possible input
  2. Rice's Theorem + Corollaries: Non-trivial properties of programs are undecidable