// Arup Guha
// 3/26/02
// Example illustrating paradox caused by Halting Problem.
// Edited on 10/12/2010 to fit the format of Sipser.

public class TM_Sipser {

  	// H is supposed to return true if M halts on w, false otherwise.
  	public static boolean H(String encodeM, String w) {
 
    	if (encodeM.charAt(0) == w.charAt(1)) {
      		System.out.println("H says "+encodeM+" accepts "+w);
      		return true;
    	}
    	else {
      		System.out.println("H says "+encodeM+" does NOT accept "+w);
      		return false;
    	}    
  	}
 
  	// D always runs its input on itself and returns the opposite of what
  	// that machine is supposed to do with that input, according to H.
  	public static boolean D(String encodeM) {
    	return !H(encodeM, "encode"+encodeM);
  	}

  	public static void main(String[] args) {

		// What D does, is NOT consistent with what H says D will do =)
    	String encodeD = "D";
    	boolean result = D(encodeD);
    	if (!result)
    		System.out.println("D does not accepts encodeD.");
    	else
    		System.out.println("D accepts encodeD.");
  	}
}