University of Virginia Computer Science
CS150: Computer Science, Fall 2005
21 October 2005
(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 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).
Where (vaccinate P) evaluates to P with all file writing commands replaced with empty commands (to make sure (is-virus? P input) is false.(define (halts? P input) (is-virus? `(begin ((vaccinate P) input) virus-code)))
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