Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 09 [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:54 PDT 2006

Contents

    09

      Schedule
      Date Meet'g Study(2 pts) Bring(5 pts) Topic(5 pts) Notes
      Wed Apr 26 8 Chapter 8 section 8.7+Minsky Ex The Halting Problem Start Project
      Mon May 1 9 Web2 URL Recursive Functions Acker(10 pts Bonus)
      Wed May 3 10 Chapter 9 sections 9.1, 9.2 Ex Undecidability & RE Project1 (10 pts)

      Acker

       Study the Ackermann function on page 381 -- Exercise 9.2.2. Write the simplest possible program that could possibly compute this function for small x & y. Use recursion and long ints(at least). Demo results to class. Earn a bonus of 10 points. Note: your program does not have to run fast (halt within 10 minutes) on large numbers (y>2).

      Web2

      Search the web for pages on recursive functions, partial recursive functions, primitive recursive functions, recursively enumerable, recursive languages, and recursion in general. Submit one URL.

      URLs on Recursive Function Theory

      Recursive Function theory

       [ recursiv.htm ] From: Raini Armstrong From: Stephen Collins

      Understanding a Recursive Function

       [ recursion.html ] From: Jacob Pitassi

      Recursive Functions

       [ http://plato.stanford.edu/entries/recursive-functions/ ] From: Jedidah Mwangi From: Moe Alsagri

      Recursive acronym

       [ Recursive_acronym ] From: Jason Hunt

      Recursive Function Theory

       [ node13.html ] From: Mike Schick

      Primitive Recursive Functions

       [ PrimitiveRecursiveFunction.html ] From: Minhchau Dang

      Ackerman's Functions

      I also have the Ackermann Function completed. Its in PHP/MVC and on my server at: [ http://ihsproductions.net/ackermann/ ] I also have a frames version if this one doesn't work at school. [ ackermann.html ] From: Stephen Collins

      Cosmic Recursive Fractal Flames

       [ http://flam3.com/ ] [ index.cgi?menu=galleries&menu2=two ] From: Scott McAllister

      Partial recursive functions

       [ node151.html ] From: Antonio Perez

      Complexity Zoo

       [ Complexity_Zoo ] From: Brian Strader

      Definitions to remember

        Definition of a Language

         A language is a set of strings.

        How a TM accepts a string in a language

         A TM accepts a string if, when started with a string in the language, it ends up in an accepting (F) state.

        How a TM rejects a string in a language

         A TM can reject a string by halting in a non-accepting state or by never entering an accepting state.

        Definition of Recursive Language

         A language that is recognized by a TM which always halts.

        Definition of recursively Enumerable Language

         A language that is recognized (by halting in an accepting state) but may have strings "rejected" by not terminating.

        Note: the name comes from an alternative, equivalent definition: The exists a TM that lists (enumerates) all the strings in the language -- if you wait long enough.

        [ Recursively_enumerable ]

      Wikipedia Articles

       [ Category:Recursion_theory ]

      Deadline for class 09

       Fewer points after this message

    . . . . . . . . . ( end of section 09) <<Contents | End>>

    Next Undecidability and Recursively enumerable Sets

    [ 10.html ]

    Project1

     First deadline: bring a progress report to class and present it. Grading: pass/fail. Any running set of tests will pass.

    Notes
    (URL): Submit one Universal Resource Locater 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.
    (Ex): Do as many of the relevant exercises as you have time for. You may work in a team of up to 4 students and hand in one joint solution. Bring to class one written solution to an exercise. This must not be a solution to an exercise marked with an asterisk(*) to earn full credit. One of the authors will be invited to present the solution to the class -- failure will loose points. Students taking CS646 must hand in the solution to an exercise marked with an exclamation mark(!) to earn full credit.
    (Study): Read & think about the assigned items. Submit one question by selecting 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. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read.
    (Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.

    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