CS200: Computer Science, Spring 2004

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 (contradicthalts input) (if (halts? contradicthalts null) (infiniteloop) 200))Proof StrategyFor our halting problem informal proof:
 Show X is nonsensical.
 Show that if you have A and B you can make X.
 Show that you can make A.
 Therefore, B must not exist.
Malicious Code Problem
 X = __________________________
 A = __________________________
 B = __________________________
Input: a procedure PIs the malicious code problem decidable?
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).
Hint:Where (vaccinate P) evaluates to P with all mail commands replaced with print commands (to make sure (isvirus? P input) is false.(define (halts? P input) (isvirus? `(begin ((vaccinate P) input) viruscode)))Using the strategy above:
Is it possible to write a virus scanner that identifies all malicious code? (tricky, think carefully)
 X = __________________________
 A = __________________________
 B = __________________________
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 → StateNameDraw 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.)
cs200staff@cs.virginia.edu Using these Materials 