4/4 If you haven't seen it yet, this makes good reading:
http://www.opencode.org/h2o -brg
\_ What is the G in Gnu's Not Unix? Every recursion has a base case
right?
\_ Not all recursion has a base case. Try, e.g.,
(define (foo) (foo))
Or, more to the point,
(define (gnu) (cons (gnu) '(is not unix)))
Every example of recursion _that terminates_ has a base case,
but recursion need not terminate. See Hofstadter's _Godel,
Escher, Bach_ for some discussion of infinite or non-terminating
recursion, including in acronyms. -- schoen
\_ Every correct recursive function has a base case. The
solution to Alan Turing's Halting problem is that if you
wrote the program correctly it should eventually terminate
IMHO.
\_ How is that a solution to the halting problem? The
halting problem is trying to figure out a way to
know if you wrote your program "correctly" (your
terminology)? Your "solution" does not tell you
how you know if you wrote your program correctly.
\_ I thought the halting problem was if your program
would eventually finish.
\_ The Halting Problem is how you can _tell_. It
happens to be equivalent to one form of program
correctness testing, but it's usually stated in
terms of the decision problem for programs' halting.
\_ What do you mean by a "correct recursive function"? |