Notes: Friday 26 March 2004

Schedule

• Monday, 29 March: Problem Set 6
• Problem Set 7 will be out on 29 March and due on 7 April.
• Problem Set 8 will be out on 7 April; part I will be due on 12 April, part II will be due on 26 April (last day of class).
• Exam 2 will be handed out on 14 April and due on 19 April.

Notes
Halting Problem Input: a procedure P (described by a Scheme program), and the input to that procedure
Output: true if applying P to input halts (finishes execution), false otherwise.

(define (halts? procedure input) ...?...)

(define (contradict-halts input) (if (halts? contradict-halts null) (infinite-loop) 200))

Proof Strategy

1. Show X is nonsensical.
2. Show that if you have A and B you can make X.
3. Show that you can make A.
4. Therefore, B must not exist.

For our halting problem informal proof:

• X = __________________________
  
  
• A = __________________________
  
  
• B = __________________________
  
  

Malicious Code Problem

Input: a procedure P
Output: true if P is would do something bad, false otherwise.

Assume we have a precise definition of what something bad means (for example, format your hard drive).

Is the malicious code problem decidable?

Hint:

(define (halts? P input)
  (is-virus? `(begin ((vaccinate P) input)
		     virus-code)))

Where (vaccinate P) evaluates to P with all mail commands replaced with print commands (to make sure (is-virus? P input) is false.

Using the strategy above:

• X = __________________________
  
  
• A = __________________________
  
  
• B = __________________________
  
  

Is it possible to write a virus scanner that identifies all malicious code? (tricky, think carefully)

What is a model?

What do we need to model computation?

Finite State Machine

FSM ::= <Alphabet, States, InitialState, HaltingStates, TransitionRules>
Alphabet ::= { Symbol^* }
    A set of symbols for the input.
States ::= { StateName^* }
InitialState ::= StateName
    Must be one of the states in States.
HaltingStates ::= { StateName^* }
    Must all be states in States.
TransitionRules ::= { TransitionRule^* }
TransitionRule ::= < StateName, Symbol, StateName>
    StateName X Symbol → StateName

Draw a finite state machine that accepts input strings containing one ( followed by one ):

Draw a state machine that accepts input strings where the parentheses are balanced: (Hint: you may need infinite amounts of paper.)