• Continue to Read Chapter 15, Noncomputability

• Examples given here may seem strained and artificial.
• However, computers have very real limitation.

• Approach: Matching up Programs and Functions
  • E.g., assume 3 functions, only 2 programs
  • Without details, conclude one function has no program

• Have: Uncountable Infinity of Functions (cannot be put into a row)
  • Diagonalization Proof
  • Assume we can account for all functions in a list
  • Show there's at least one more than can't be in this list
• All Programs Can be Ordered
  • By size, shortest program first
  • Just use alphabetical order
• Try to Draw Lines Between Functions and Programs
  • Could draw lines from every program to every function
  • But, have proved functions uncountable...
  • Thus, There Must be Functions With Programs!

• Hard to come up with function that computer can't produce.
  • Possible example, random list of numbers
  • Use Table
  • Program must be of finite size; Requires infinite table

• Express programs as a single string (formatting messed up)
• Therefore, could write program to see if there is an IF statement in the program: answers YES or NO
• How about, does 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...