University of Virginia, Department of Computer Science
CS200: Computer Science, Spring 2004

Notes: Wednesday 24 March 2004

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))
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 mail commands replaced with print 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)

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 SymbolStateName

Turing Links
Using these Materials