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

Contents

    Class Meeting 08 -- Review Turing Machines and the Halting Problem

      Context

      Date Meet'g Study(2 pts) Bring(5 pts) Topic(5 pts) Notes
      Mon Apr 24 Previous Chapter 8 sections 8.5, 8.6 Ex Restricted TM
      Wed Apr 26 Today Chapter 8 section 8.7+Minsky Ex The Halting Problem Start Project
      Next 9 Web2 URL Recursive Functions Acker(10 pts Bonus)

      Chapter 8.7 -- summary of chapter 8

        Any questions?

        Wot, No exercises?

         See below

        Ex

         1. Use the web to find out about Marvin Minsky... bring your discovery to class and use the Submit "button" to send me a URL. This also counts as credit for a question on the handout.

        2. Prove that TM which doesn't always move its head can be simulated by a normal TM. In other words, we have transition that read ( newstate, new symbol, -) indicating that the head does not move but the state and symbol changes. What is the effect of the simulation on run time, number of states, etc..

        CS646 can credit for either exercise.

      Minsky

        Marvin Minsky

         [ marvin-minsky ] From: Mike Schick

        Minsky at MIT

        [ http://web.media.mit.edu/~minsky/ ] From: Jedidah Mwangi

        Marvin Minsky Biography

        [ minskybiog.html ] From: Scott McAllister

        Minsky -- Conscious Machines

         [ minsky.html ] From: Brian Wildrick

        Why People Think Computers Can't Think

        [ ComputersCantThink.txt ] From: Brian Strader

        Alienable Rights

        [ Alienable%20Rights.html ] From: Moe S.

        Minsky Quote on Education

         [ minski.html ] From: Minhchau Dang

        Minsky interviews by G4TV

          From: Jason Hunt

          Q&A: Marvin Minsky on the Future of AI, 2/27/04

           [ QA_Marvin_Minsky_on_the_Future_of_AI.html ] (text, 2 pages)

          Minsky on The Screen Savers TV show, 3/1/04

          [ pile_player.aspx?video_key=8390 ] (Flash Player video, ~10min)

        MINDS ARE SIMPLY WHAT BRAINS DO

         [ 2truth03.html ] From: Stephen Collins

        EBook -- Minsky on the Movie Set

         [ two1.html ] From: Jacob Pitassi

        The Emotion Universe

         Thoughts on why progress has been so limited in the subject of Artificial Intelligence: [ art0532.html ] From: Raini Armstrong

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

      Ch 8.7+Minsky pp -- Deadline for class 8

      Fewer points after this message arrives.

    . . . . . . . . . ( end of section Class Meeting 08 -- Review Turing Machines and the Halting Problem) <<Contents | End>>

    Next -- Recursive Function Theory


    (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. [ 09.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