.Open 09
. Schedule
.Table Date
.Item Meet'g
.Item $Study(2 pts)
.Item Bring(5 pts)
.Item $Topic(5 pts)
.Item Notes
.Row Wed Apr 26
.Item 8
.Item Chapter 8 section 8.7+Minsky
.Item $Ex 
.Item The Halting Problem
.Item Start $Project
.Row Mon May 1
.Item 9
.Item $Web2
.Item $URL
.Item Recursive Functions
.Item $Acker(10 pts Bonus)
.Row Wed May 3
.Item 10
.Item  Chapter 9 sections 9.1, 9.2
.Item $Ex
.Item Undecidability & RE
.Item $Project1 (10 pts)
.Close.Table
. 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
.See http://www.earlham.edu/~peters/courses/logsys/recursiv.htm
From: Raini Armstrong
From: Stephen Collins
. Understanding a Recursive Function
.See http://www.cs.umd.edu/class/spring2002/cmsc214/Tutorial/recursion.html
From: Jacob Pitassi
. Recursive Functions
.See http://plato.stanford.edu/entries/recursive-functions/
From: Jedidah Mwangi
From: Moe Alsagri
. Recursive acronym
.See http://en.wikipedia.org/wiki/Recursive_acronym
From: Jason Hunt
.  Recursive Function Theory
.See http://www-formal.stanford.edu/jmc/basis1/node13.html
From: Mike Schick
. Primitive Recursive Functions
.See http://mathworld.wolfram.com/PrimitiveRecursiveFunction.html
From: Minhchau Dang

.  Ackerman's Functions
I also have the Ackermann Function completed. Its in PHP/MVC and on my server at:  
.See http://ihsproductions.net/ackermann/
I also have a frames version if this one doesn't work at school.
.See http://ihsproductions.net/ackermann/ackermann.html
From: Stephen Collins
.  Cosmic Recursive Fractal Flames
.See http://flam3.com/
.See http://flam3.com/index.cgi?menu=galleries&menu2=two
From: Scott McAllister
. Partial recursive functions
.See http://www.cs.wwc.edu/~aabyan/Logic/Book/book/node151.html
From: Antonio Perez
.  Complexity Zoo
.See http://qwiki.caltech.edu/wiki/Complexity_Zoo
From: Brian Strader

.Open 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.

.See http://en.wikipedia.org/wiki/Recursively_enumerable
.Close
. Wikipedia Articles
.See http://en.wikipedia.org/wiki/Category:Recursion_theory
. Deadline for class 09
Fewer points after this message


.Close 09
. Next Undecidability and Recursively enumerable Sets
.See ./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.