University of Virginia Computer Science
CS150: Computer Science, Fall 2005

21 October 2005

CS150 Notes 25 (21 October 2005)

Upcoming Schedule

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) 150))
Why is it nonsensical to define contradict-halts?

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?

(define (halts? P input)
  (is-virus? `(begin ((vaccinate P) input)
Where (vaccinate P) evaluates to P with all file writing commands replaced with empty commands (to make sure (is-virus? P input) is false.

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


"); print ( $res[$first] ) ; print (""); ?>
CS 150: Computer Science
University of Virginia
Using these Materials