SUNY Geneseo Department of Mathematics

Introduction

Wednesday, January 20

Math 304
Spring 2016
Prof. Doug Baldwin

Return to List of Lectures

(No Previous Lecture)

Welcome to Math 304
- Theory of Computability
- I’m Doug Baldwin
- Syllabus
  - Prerequisite?
    - Proofs about computability
    - Induction
    - Contradiction
  - Optional presentations
    - Pick an uncomputable problem and present it and the proof of its uncomputability
    - For 348 waivers
Example
- The impossibility of a perfect antivirus program
- “Perfect antivirus program” correctly answers the question “if I run program P, will it infect my computer with a virus?”
- Suppose it exists as computable function infectious( P )
- Then write…
```
superVirus
    if not infectious( superVirus )
        infect computer
```
- Why not run P until it infects or doesn’t?
  - You can’t tell how long to run P to be sure it won’t infect
```
P
    loop
        r = random number between 0 and 1
        if r < 0.5
            infect
```
- This argument is missing lots of technical detail, e.g., what does it mean for a function to be “computable”, can programs operate on other programs, etc.
  - And how on Earth can a program operate on itself? superVirus certainly can’t be…
```
superVirus
    if not infectious( "superVirus if not infectious( "superVirus…
```
- This course will fill in these details, and then examine what they imply about what is and isn’t computable, how many computable or uncomputable functions there are, etc.
Next
- Definition 1 of computation
- Finite automata
- Read section 1.1 from beginning through “Designing Finite Automata”
  - Pages 31 through 43

Next Lecture