Date: 09/04/2008
class: computational thought
taught by : Dennis Shasha
Scribe: Feng Jiang

Preface….
One after another, as the student entered the room, the inevitable truth becomes clearer.  The link to the simplified version of the homework reading fails to work.
The start of class….
We started by writing the second part of our homework(beside the reading), a paradox that we need to think up, on pieces of paper while the teacher talked about what we are planning to do today, which in the end pretty much covers only the paradox and a few brief things about the idea of first machine computer.
Paradoxes that people thought up (not set related):
1. It is the American government's policy to not negotiate with terrorist, but what if the terrorist's demand is to not negotiate? (it is agreed that “give in to demand” is better than “negotiate” because otherwise it might not be true)
2. To move a distance, one must move half of said distance, and half of that etc.  So essentially one can't move because there is an infinite number of subdivisions.
3. Answer truthfully, will the next word you say "no"?
4. I never told the truth. (However, if u told the truth at any other time, this can well be a lie because u told the truth at some point in time.  So this is an example where there is a loop hole)
5. If this is true, then 5!=5
6. Male barber who whould only shave all those who do not shave themselves.  So is he supposed to shave himself??

Now here are a few that is set related
1. R={x|R is not in x}
2. R={x|sum of the elements of x >= sum of the elements of R, x are set of numbers}
R is empty
{5} sum is 5, >=0
R contain 5, is 5
R=5, R=5, R=R
R is in R
So sum of R is sum of {5} and R={{5}}=10(and can climb even more)
{5} 5<10, Causing {5} to not be in R
So now R contains R and not 5, sum of which is 0(seeing as each R, layers and layers down etc are empty save for self, which is 0)
{5}>{R}(0) so {5} should be in R..... 
Story time!

After Russell ruined the life of Frege, he says: I can do better!  So he came up with the theory of types.  He must avoid putting self in statement, or make self different.   Hilbert, a brilliant German mathematician who posed some number of problems in logic and math that have stumped people for most of the 20th century and beyond, want math to be put on a good and solid foundation, beyond what Russell can offer.  He wanted math to be both sound and complete, meaning that anything you prove is true, being sound, and anything true can be proved, being complete. (and at this point, some guy who was not a ghost came in) 
	Hilbert made this a challenge, and Kurt Goedel, a Swiss scientist, replied.  He said that he can “encode” the following statement in the simplest logical system for arithmetic that says “this statement cannot be proved.”  Alan Turing then came in and says: “ Goedel’s proof is too abstract, I don’t like it.  I’m going to make it really concrete.”  So he made example where a computer, a person who computes, have a long string of papers, to the points of infinite, where the paper can only shift to the piece next to it, and the one next to that etc.  the computer have finite memory, and the computer, either a person or a machine, can read and write an element and then shift the tape.  Because there exist a reasonable model of computation which is individual from persons, you can make a machine to do the job.  Now if you have a program on such a machine to do the processes as a person would on the papers on string.  For example, a program that translates all letters in a given message to upper case.  However, you can apply the program to the instruction or the meaning of the program itself.

Something to think about:
Is there any problem that can be clearly stated for which no programs can possibly stop?
What did we get out of this period?
1.	We have all lied....
2.	Theory of types, avoid self referencing by making self different from those you are allowed to talk about. See index A
Homework: think about the program that will never stop, and read SPACESHIP MALFUCTION in the puzzle book.

Index A: theory of type.
Theory of types: hierarchical theory. Zeroth order logic (propositional) 
Not (X or Y) = (Not X) and (Not Y).
Propositional logic talks about individuals.
First order – Frege style logic (with for all, there exists)
Second order – quantify over sets {x | x is not in a set}. All finite sets of numbers have a finite sum.
Theory of types: An order k statement can talk about only lower order facts. E.g. a second order statement can talk about first order statements.

Index B: T(program, java code, capable only of translate 1 word… trying to fix the last part… anyone?)
import java.util.Scanner;
public class T
{   
    public static void main()
    {
        Scanner scan=new Scanner(System.in);
        System.out.println("what do u wish to translate?");
        String it=scan.next();
        for(int index=0; index<it.length(); index++)
        {
            char t=it.charAt(index);
            if(t=='a')System.out.print("A");
            else if(t=='b')System.out.print("B");
            else if(t=='c')System.out.print("C");
            else if(t=='d')System.out.print("D");
            else if(t=='e')System.out.print("E");
            else if(t=='f')System.out.print("F");
            else if(t=='g')System.out.print("G");
            else if(t=='h')System.out.print("H");
            else if(t=='i')System.out.print("I");
            else if(t=='j')System.out.print("J");
            else if(t=='k')System.out.print("K");
            else if(t=='l')System.out.print("L");
            else if(t=='m')System.out.print("M");
            else if(t=='n')System.out.print("N");
            else if(t=='o')System.out.print("O");
            else if(t=='p')System.out.print("P");
            else if(t=='q')System.out.print("Q");
            else if(t=='r')System.out.print("R");
            else if(t=='s')System.out.print("S");
            else if(t=='t')System.out.print("T");
            else if(t=='u')System.out.print("U");
            else if(t=='v')System.out.print("V");
            else if(t=='w')System.out.print("W");
            else if(t=='x')System.out.print("X");
            else if(t=='y')System.out.print("Y");
            else if(t=='z')System.out.print("Z");
            else System.out.print(it.charAt(index));
        }
    }
}