// Arup Guha
// 3/23/05
// Example illustrating reduction of ATM to HALT.

public class HALT {

  // doesHalt is supposed to return true if M halts on w, false otherwise.
  public static boolean doesHalt(String encodeM, String w) {
 
    if (encodeM.charAt(0) == w.charAt(1)) {
      System.out.println("H says "+encodeM+" halts on "+w);
      return true;
    }
    else {
      System.out.println("H says "+encodeM+" loops on "+w);
      return false;
    }    
  }

  // Assuming the method doesHalt works, this method SOLVES ATM!
  public static boolean ATM(String encodeM, String w) {

    // If w doesn't halt on M, w can't be in L(M).
    if (!doesHalt(encodeM, w))
      return false;

    // Since we are guaranteed that w halts on M, run it!
    else
      return run(encodeM, w);
  }

  public static boolean run(String encodeM, String w) {

    // I could really write this, but it would be very complicated.
    // All you have to know is that it simulates M on w and if it finishes
    // returns the answer.

    return (encodeM.length() > w.length());

  }

  public static void main(String[] args) {

    String encodeM = "encodeM";
    String input = "input";
    
    // We can run ATM and figure out whether input is a string in the
    // machine encoded as encodeM.
    if (ATM(encodeM, input))
      System.out.println("M accepts the input.");
    else
      System.out.println("M doesn't accept the input.");

  }
}