// Arup Guha
// 3/26/02
// Example outlining the proof by contradiction that shows that the 
// Halting Problem is undecidable. In essence, I have written functions
// that mirror the constructions of TMs given in the proof. What you
// find is that no matter what you write for the TM H, the output and
// actions of this program are contradictory. This proves that it is 
// impossible to write a function H, or build a Turing Machine H.

public class TM {


  // This is an example of a Turing Machine M.
  public static boolean M(String w) {
    if (w.equals("hello")) {
      System.out.println("M halts on input "+w+" and returns true.");
      return true;
    }
    else if (w.equals("byebye")) {
      System.out.println("M halts on input "+w+" and returns false.");
      return false;
    }
    else {
      for (int i=0; i>-1;);
      return false;
    }
  }

  // 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+" halts on "+w);
      return true;
    }
    else {
      System.out.println("H says "+encodeM+" loops on "+w);
      return false;
    }    
  }

  // Hprime is supposed to loop if M halts on w, and return true
  // otherwise.
  public static boolean HPrime(String encodeM, String w) {

    if (H(encodeM,w)) {
      for (int i=0; i>-1;);
      return false;
    }
    else {
      System.out.println("Hprime says "+encodeM+" loops on "+w);
      return true; 
    }
  }
  
  // D just calls Hprime with encodeM and encodeM...in essense, D should
  // loop if M halts on M and it should return true, if M loops on M.
  public static boolean D(String encodeM) {
    return HPrime(encodeM, encodeM);
  }

  public static void main(String[] args) {

    String encodeD = "encodeD";
    D(encodeD);
    System.out.println("D loops on its own input.");

  }
}

//Output:
//H says encodeD loops on encodeD
//Hprime says encodeD loops on encodeD
//D loops on its own input.
//
//Explanation: This contradicts the fact that D must have terminated,
//             since the last print only occurs IF D terminates.
//
//If you change encodeD to any string with the same first two characters,
//then this program will print that encodeD halts on encodeD and then it
//will loop forever.