|Wed Apr 26
||Chapter 8 section 8.7+Minsky
||The Halting Problem
|Mon May 1
||Acker(10 pts Bonus)
|Wed May 3
||Chapter 9 sections 9.1, 9.2
||Undecidability & RE
||Project1 (10 pts)
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).
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
[ http://plato.stanford.edu/entries/recursive-functions/ ]
From: Jedidah Mwangi
From: Moe Alsagri
[ Recursive_acronym ]
From: Jason Hunt
Recursive Function Theory
[ node13.html ]
From: Mike Schick
Primitive Recursive Functions
[ PrimitiveRecursiveFunction.html ]
From: Minhchau Dang
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 ]
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 ]
[ Category:Recursion_theory ]
Deadline for class 09
Fewer points after this message