Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 03 [Text Version]
[About] [Contact] [Grades] [Projects] [Submit] [Schedule] [Syllabus] [Search ]
Session: [01] [02] (03) [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Thu Jun 8 13:02:48 PDT 2006

Contents

    Class 03 -- History

      Context
      Date Meet'g Study(2 pts) Bring(5 pts) Topic(5 pts) Notes
      Previous 2 Chapter 1+math Ex1 Methods
      Today 3 Preface+Web1 URL History Exam on math(50 pts)
      Next 4 Chapter 2+Chapter 6 section 6.1 Ex Automata

      (Web1): Search the WWW for pages on the theory of computability, Alan Turing, Turing Machines, tractability, Stephen Cook, Michael Rabin, etc. Submit one URL.


      (URL): Submit one Universal Resorce Locator for a relevant page on a piece of paper. Use the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class.


      (math): Chapter 1 + the big-O notation + some graph theory.

      Question about the Preface: In 1979, what educational level mainly dealt with the study of automata and language theory?

      Anecdote: 35 years of Theory

      What are some of the other more recent uses of automata and language theory, besides model-checking algorithms?

      How could the implementation of a non-deterministic turing machine change current computer architecture, if at all?

      Automata Theory

      From: Jedidah Mwangi. I chose this [ Automata_theory ] article because it explain automata theory in broad ways.

      The Theory of Computation:

      From: Juno Fernandez [ Theory_of_computation ]

      Computational Complexity Theory

      From: Jason Hunt [ Computational_complexity_theory ]

      Time Magazine article on Alan Turing

      From: James Kim [ turing.html ]

      This is a great site that documents Time Magazine's most important people of the century. It gives a brief but infomative excerpt on Alan Turing and his contributions.

      Alan Turing's Unorganized Machines

      From: Scott McAllister [ Alan_Turing%27s_Unorganized_Machines ]

      Alan Turing Internet Scrapbook

      From: Stephen Collins [ index.html ]

      Also Powerpoint Presentation on my server at [ http://ihsproductions.net/cs646/ ]

      Turing Machines

      From: Antonio Perez [ Turing1.html ]

      URL on Turing Machine

      From: Jacob Pitassi I looked up a URL on Turing Machines. Here is the URL that I came up with. I thought it was very interesting because it explians what it is and how it works and then gives some hyperlinks to Turing Machine simulators.

      [ Turing.html ]

      Michael Rabin/Rabin Cryptosystem

      From: Raini Armstrong

      A brief biography for Michael O. Rabin: [ Michael_O._Rabin ]

      And within the page, an additional link to Rabin Cryptosystems can be found: [ Rabin_cryptosystem ] (Submitted by Raini and Moe Alsagri).

      Theory of Computability

      From: Peter Villalon [ computab.html ]

      Computational Complexity Theory

       From: Brian Strader [ Quantum_computer#Quantum_computing_in_computational_complexity_theory ]

      The URL above is a subsection of an article on quantum computers and how they affect computational complexity theory.

      Zero-knowledge proof

      From: Minhchau Dang [ Zero_knowledge_proof ]

    . . . . . . . . . ( end of section Class 03 -- History) <<Contents | End>>

    Next

    [ 04.html ]

    Standard Definitions
  1. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
  2. ND::="Non-deterministic", a machine that can try out many possibilities and always guesses the right choice. Note: For a given problem a ND solution is simpler and easier to understand than a deterministic one. We study ND machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun.
  3. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
  4. RJB::=The author of this document, [ ../index.html ]
  5. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
  6. Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
  7. Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
  8. Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
  9. TBA::="To Be Announced".
  10. TM::="Turing Machine".
  11. NTM::="Nondeterministic Turing Machine".
  12. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
  13. DTM::="Deterministic Turing Machine".
  14. runtime::=run_time,
  15. run_time::="The number of steps a TM takes before it halts when start on a given input".
  16. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
  17. P::@problem=class of problems that a DTM can compute in polynomial_time.
  18. NP::@problem=class of problems that a NTM can compute in polynomial_time.
  19. polynomial_time::=An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c.

    From Logic

  20. LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html


  21. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
  22. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
  23. (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument. Typically if A and B and C then D starts with assuming A,B, and C are given. They are called the hypotheses.
  24. (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after the then in an if...then... result. This is called the conclusion.
  25. (LOGIC)|- (def): By definition of a term defined above.
  26. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
  27. (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.

End