Tuesday, September 2

The Halting problem: "Knowing when start a process, whether you will ever stop." This problem is unsolveable for computer programs.

From Wikipedia, the free encyclopedia.
The halting problem is a decision problem which can be informally stated as follows:

    Given a description of an algorithm and a description of its initial arguments, determine whether the algorithm, when executed with these arguments, ever halts (the alternative is that it runs forever without halting).

Alan Turing proved in 1936 that there is no general method or algorithm which can solve the halting problem for all possible inputs.

The importance of the halting problem lies in the fact that it was the first problem to be proved undecidable. Subsequently, many other such problems have been described; the typical method of proving a problem to be undecidable is to reduce it to the halting problem.

Show video on PT- Put on reserve in library!
Background: Similar triangles
Area of triangles = 1/2 bh
Area of parallelogram= bh
Scaling: a linear scale change of r gives area change of factor r^2.
3 questions: running, moat, wind power...
Proof of the PT: Similar right triangles c = a^2/c + b^2/c.
applications and other proofs.
Prop. 47 of Euclid.
Dissection Proof.
Prop 31 Book  VI  Similar shapes.
Simple proof of PT using similar triangles of the triangle.
Use in 3 dimensional space.

  • More on measurements of angles and areas of polygons.

  • Two issues that are consequences of the puzzle discussion:

    1. Rigid Motions in (or about) the plane.

    2. # Orientation preserving
        # Translations
        # Rotations
      # Orientation reversing
        # Reflections
        # Glide reflections
    3. Dissection of the plane--- Tilings of the plane.
    4.  Regular

    5. # Activity in class: 4.1  Ex. 3, 4, 5
      # Semiregular
      # One polygonal Tile