home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10199 < prev    next >
Encoding:
Text File  |  1992-08-12  |  2.1 KB  |  47 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!wjcastre
  3. From: wjcastre@magnus.acs.ohio-state.edu (W.Jose Castrellon G.)
  4. Subject: Big primes puzzles
  5. Message-ID: <1992Aug13.050021.737@magnus.acs.ohio-state.edu>
  6. Keywords: Ackermann function/Puzzle/Primes
  7. Sender: news@magnus.acs.ohio-state.edu
  8. Nntp-Posting-Host: bottom.magnus.acs.ohio-state.edu
  9. Organization: The Ohio State University,Math.Dept.(studnt)
  10. Date: Thu, 13 Aug 1992 05:00:21 GMT
  11. Lines: 34
  12.  
  13. First I'd like to thank the people that emailed me quite elegant solutions
  14. to the problem I posted last week. I was surprised to learn how many eminent
  15. mathematicias are silent netters. Thank you again.
  16.  
  17. Now a puzzle that has to do with the Ackermann function and big primes:
  18. The Ackermann function is a computable map that grows so fast, that for each
  19. primitive recursive function it eventually majorizes it; it came out as a solu-
  20. ion to a problem of Hilbert, who asked whether all intuitively computable
  21. functions could be defined by a primitive recursive scheme.
  22.  
  23. Fast growing functions were the essence of the first arithmetic statement (not
  24. directly related to logic) shown to be independent of Peano Arithmetic (Paris &
  25. Harrington, and yes!, naturally...Solovay has theorems in that area too).
  26. The following variant of Ackermann's original function is usually given
  27. that name:
  28.  
  29. =========================================================================
  30. A(0,m) = m+1
  31. A(n+1,0) = A(n,1)
  32. A(n+1,m+1) = A(n, A(n+1,m))
  33. =========================================================================
  34.  
  35. I learned of the puzzle from S.Camargo who was an undergrad T.A. at Univ. de
  36. Los Andes, and was taking a course in Recursion Theory. He posted a sign
  37. offering a 5.0 (A+) to any of his precalculus students that would:
  38.  
  39. =================================================
  40. 1. Find a closed form for A(c,n), c in {1,2,3,4}
  41. 2. Decide whether A(4,4) is a prime or not.
  42. =================================================
  43.  
  44. Of course, everybody knew the grade offer was a joke, but the question sparked
  45. interest among the sci-eng students, and fairly quickly a cosci major came up
  46. with the solution; he soon switched majors.
  47.