• Final on Friday, May 8, at 9:00am, B101 LSRC

• Compilers do
• Can it judge a program's behavioir?
• How about, does the program halt?
• Lack of WHILE (and functions) guarantees a halt.
• Not very sophisticated
• Not Halting for All Inputs is usually considered a Bug

• Write specific code to check out more complicated cases
• Gets more and more involved...

// input an integer value for k
while (k > 1)
    if ((k/2) * 2 == k)     // is k even?
        k = k / 2;
    else
        k = 3 * k + 1;
        

• e.g. 17: 52 26 13, 40 20 10 5, 16 8 4 2 1
• No one knows whether this quits for all inputs.
• Mathematicians have proven that no one, finite program can check this property for all possible programs

• Equivalence: Define by same input > same output
• Use variation of above program; not sure it ends
• Cannot generally prove equivalence

• Sketch of proof
• Find more details in book

• Inputs: p = program, x = input data
• Returns: "Halts"
  or "Does not halt"

• Inputs: p = program
• Returns: "Halts on self" or "Does not halt on self"
• Uses: halt(p, p);
• i.e.: asking if halts when program p uses itself as data

void contrary();
{
    TextField program = new TextField(1000);
    string p, answer;
    p = program.getText();
    answer = selfhalt(p);
    if (answer == "Halts on self"
    {
	while (true)     // infinite loop
		answer = "x";
    }
    else
        return;
}

• If halt program decides it halts, it goes into infinite loop and goes on forever.
• If halt program decides it doesn't halt, it quits immediately.

• Not necessarily a very tough constraint unless you get too greedy.
• Programs can't do everything.
  • Beware of people who say they can!
• Program probably can't do things we don't know how to do...