11/15/2004 CSC 486 : Hem-Ogi 2.1 Proof… the machine M' 1.Simulate M on h z,  i :  if M rejects, then M' rejects  if f (  )  z  then M' accepts 2.Otherwise, let x =  3.Simulate M on h z,x0 i :  if it accepts let x = x0 if f(x) = z then M' accepts else repeat 3  else goto 4 4.Simulate M on h z,x1 i :  if it accepts let x = x1 if f(x) = z then M' accepts else goto 3  else goto 3 Note that we do not actually need to simulate M at this step, nor will we ever encounter the final goto (Can you tell why )
{}