• Final Exam Date
• Review

• 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 Mapping int To int
  • How can we show that is true?
  • Functions can be seen as columns in tables
  • Put all functions into a huge (infinite!) table
  • Show that even that cannot hold them all

  1	2	6	0	0	8	2	1	4	.	.
  4	4	7	0	1	8	4	1	7	.	.
  9	6	8	0	0	8	6	2	10	.	.
  16	8	9	1	1	8	16	3	13	.	.
  25	10	10	1	0	8	10	5	16	.	.
  36	12	11	1	1	8	36	8	19	.	.
  49	14	12	1	0	8	14	13	22	.	.
  64	16	13	1	1	8	64	21	25	.	.
  81	18	14	1	0	8	18	34	28	.	.
  .	.	.	.	.	.	.	.	.	.	.
  .	.	.	.	.	.	.	.	.	.	.

• 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...