Outline for May 7, 1997

1.	Greetings and Felicitations

2.	HRU result and proof

a.	General result (HRU Theorem): Whether a given state of a given protection sys-
tem is safe for a given generic right is undecidable

b.	Proof approach: reduce halting problem to safety problem

c.	Proof: T is an arbitrary Turing machine; encode T¼s state as an ACM and the head 
moves as commands of the protection system
T in state q has scanned k cells; cells k+1, ... are blank. Represent q as an ACM 
with k subjects and objects meeting the following:
1.		If cell s of tape contains symbol X, then A[s, s] contains the right X
2.		A[s, s+1] contains the right Own; this induces an ordering on the subjects
		 according to the symbols on the tape; note Own is above main diagonal
3.		A[k, k] contains the right End (signalling the farthest right the head has moved)
4.		If tape head at cell s, A[s, s] contains the right q
Initially, q0 is an ACM with one subject and one object corresponding to the first 
tape cell.
Move: d(q, X) = (p, Y, L) means in state q and head scanning symbol X, changes 
state to p, overwrites X with Y, and moves head left (R would be right). Movesrep-
resented as commands; example: above move is:
command cqX(s, s¼) 
if		Own in A[s, s¼] and
		q in A[s¼, s¼] and
		X in A[s¼, s¼] 
then
		delete q from A[s¼, s¼] 
		delete X from A[s¼, s¼] 
		enter Y into A[s¼, s¼] 
		enter p into A[s¼, s¼] 
	end.
where s¼ is current position of tape head and s is square to left. A move to the right 
has to handle the End case; 2 different commands, appropriately conditioned
Now, if T reaches its final state qf, then right qf leaked into some position of ACM; 
equivalently, if TM halts, the right qf is leaked. So if the safety question is decide-
able, so is the halting problem, which is false; so the safety problem is undecid-
able.

3.	Take-Grant: rules, initial and terminal spans, bidirectionality of t and g given subject-
only graph