CHANGES FROM INITIAL SUBMISSION
in
"Formulas for Computable and Noncomputable Functions"
Samuel Alexander
1. Added "\usepackage{amssymb}" to the LaTeX preamble to allow usage of "\nmid" (a nice-looking "does not divide" symbol)
2. By far the most major change: in response to the referee's comment:
"Definition 1 (now Definition 2), part 1: It's not obvious why the prime exponent function
should be considered an explicit formula; you might want to say a little
more about this."
...I removed the prime exponent entirely from the the definition.
Since the original submission, I've discovered that it was redundant in the first place.
I added, at the end of section 3, a separate definition for the prime exponent
function, and a lemma stating that the prime exponent function has a formula which
does not require usage of infinite series. This strengthens the results of the paper,
so I'm glad the referee pointed out this particular point!
Note that this added material is just elementary number theory and does not require any
computability theory background.
3. At referee's suggestion, changed "loose (but precise)" to simply "informal"
4. At referee's suggestion, fixed a typo in definition of recursive: a function was lacking codomain.
5. At referee's suggestion, changed "ie" to "i.e." in several spots, and removed a formula from lemma 1
which was not really needed.
6. At referee's suggestion, swapped ellipses for sigma notation in the definition of Omega(n,i).
However, this comes at a steep price because there is a very subtle trap involved here.
With ellipses, the trap was skirted, but using sigma notation it would be doing the reader
a disservice not to include a footnote warning of the danger. So I added a footenote
to say a brief word about this trap. This also entailed restructuring the paragraph following
the definition of Omega to make it more readable.
7. At referee's suggestion, changed "guess key" to "guessed key" in one spot
8. At referee's suggestion, changed "essentially get 1" to "get 1" in one place
9. At referee's suggestion, in proving lemma 3 we gave a more accurate explanation of how two
utility functions would be combined together.
10. At referee's suggestion, I changed the definition of f^tilde in lemma 4 (previously lemma 3) proof to remove a
redundant kronecker delta which was previously used in two places in an attempt to somewhat
reduce the amount of tedious gritty formula-verifying details. The tradeoff is that I added
the parenthesized comment below:
($P_2(\vec{n},m,i)$ vanishes since it is a multiple of $\bdelta(0,m)$)
11. Changed "Lemmas 2,3, and 4" to "Lemmas 3, 4, and 5" (i.e., added a necessary space there)
12. Referee suggested I change "the proper key" to "a proper key" in several places. I decided
instead to change it to "the smallest proper key". I'm very glad the referee caught this,
as I can see how it might have caused confusion! I was using "the proper key" in the sense
of "the proper key we have been discussing", but in a mathematical document this comes across
sounding like "the unique proper key", which is fiction.
13. In the example following theorem 6 I added explicit references to which constructions were
being followed when.
14. The referee pointed out I was guilty of using "exponentially" in a remark in the "everyday"
sense of the word, which is undesirable in a mathematical document! I switched
"exponentially larger functions" to "much larger functions".
15. Added a paragraph mentioning that the arithmetical hierarchy is indeed a hierarchy,
at referee's suggestion.
16. At referee's advice, I added a footnote:
\footnote{In fact, it can be shown that the sets with computable indicator
functions are exactly $\Sigma_1\cap \Pi_1$.}
17. Changed "sourcecodes" to "source codes".
18. Changed codomain of f_forall from \N to {0,1}
19. Changed "nicer" to "more nicely"
20. At referee's advice, clarified that the "new formula-related characterization" in the conclusion is referring
to the Guessing Lemma.
21. At referee's advice, I changed "analog of a weak for loop" to "analog of a for loop", since the subtle
intricacies of what might be called a "non-weak for loop" would be out of place.
22. Change "a couple simpler functions" to "a couple of simpler functions" and "closure unbounded minimization"
to "closure under unbounded minimization"
23. The referee mentioned there was some ambiguous usage of the terms "projection" and "composition" in
definition 1 and the two preceding paragraphs. Rather than just amend these, I merged the two
paragraphs into one shorter, less ambiguous one. Both paragraphs were meant as motivation for
including projection and composition in definition 1, but the projection and composition weren't
actually brought in as the "solution to our woes" until the 2nd paragraph, which caused the first
paragraph to sort of seem detached from the rest of the paper.
24. In definition 2 I added a comment to the effect that divergent infinite series are considered
undefined, as the referee suggested.
25. Changed "iff" to "if and only if" throughout
26. Moved the last paragraph inside the proof of lemma 2 to outside the
proof.
27. Explicitly mentioned what Pi_0 and Sigma_0 are: Pi_k and Sigma_k have definitions involving
the phrases "exists m_1 forall m_2 exists ... m_k" and "m_1,...,m_k". Of course for $k=0$ the
correct way to parse this is to have no m's at all, but I agree with the referee that this is
confusing, so I specifically made a comment for the k=0 case.
28. At referee's suggestion, I added an explicit example where Lemma 2 is used to
construct a gate.
29. I made the rows a little higher in the table following the definition of "key" (Def. 6), so that the
horizontal dividing line will no longer intersect the tilde's, which was making f and
tilde{f} indistinguishable in that table (at least when viewed on my PDF viewer).
30. Added a definition which defines dom f and "total function", and a remark that F_0 functions
are total.
31. The referee suggested leaving 0^0 undefined. This would however destroy the very convenient
fact that F_0 functions are total. Moreover, it would buy nothing: I've added (at the end
of section 3) a remark which shows it doesn't matter what stance we take on 0^0, the
functions which turn out to have formulas go unchanged. Furthermore, the referee also suggested
we point out explicitly the totalness of F_0 functions, so even were we to change our stance
on 0^0, that would force us to then defy that other suggestion. Furthermore, Knuth, Graham,
and Patashnik, as well as much of the mathematical community, argue vehemently that 0^0
"should" be defined to be 1.
32. At the referee's suggestion, I changed "to enjoy" to "to have" throughout, when speaking of
functions which have/enjoy or lack/do not enjoy formulas.
33. At the referee's suggestion, I moved an example from inside the proof of Lemma 4 to just
outside the proof of Lemma 4.
34. In the statement of Theorem 8 (now theorem 10), I replaced "round r off" with a less ambiguous instruction.
35. I basically rewrote the later half of the "background" discussion on the Church-Turing thesis
so as to put more emphasis on the fact that the thesis is purely informal, and to explain more
thoroughly how the thesis is applied in a mathematical document.
36. There was a subtle error in the definition of unbounded minimization, I fixed this and in
so doing also changed the symbols to be more clear. And I changed a comment below the definition
of recursive functions which talked about unbounded minimization.
37. Added an explicit definition of F_0, which seems to have somehow been mistakenly erased from the
manuscript at some point.
38. Throughout, I changed all mention of "axioms" of the definition of recursive functions to
"statements", "parts", etc. ("Axiom" is conveniently one-size-fits-all, whereas "statement" or
"part" only sound right in certain places, and in some places (mainly in the appendix) the
whole syntax of a sentence had to be changed to say the same thing without saying "axiom").
39. At referee's suggestion, I capitalized "Lemma 5", "Definition 1", "Theorem 7", etc., everywhere.
40. At referee's suggestion, where the Church-Thesis is mentioned in the appendix, I add a footnote
referring any forgetful readers back to the "background" section.
41. I changed Theorem 6 to remove the mention of the fact that we can find formulas with just one
infinite sum. This fact was added later on in the original creation of the paper, and wasn't
really a good idea. As the referee points out, it invalidates the part of Theorem 7 which says
"the converse of Theorem 6 is false". More importantly, it is a statement which depends
very delicately upon the specific structure of the definition of having a formula (Definition 1).
Definition 1 is very flexible in that it has an enormous number of possible variants which would
all give rise to the same functions actually admitting formulas. However, the "number of infinite
series" in a formula is a crude metric because it could easily be changed by changes to Definition
1 which otherwise preserve everything else.
42. At the referee's suggestion, I split Theorem 7 (now Theorem 8) into a Theorem and a Corollary.
43. At referee's suggestion, changed Definition 0 to Definition 1. This, together with the new
lemma mentioned in entry 2 of this file, necessitated a general renumbering of definitions,
lemmas, and theorems all throughout the paper.
44. Removed part of the conclusion.
45. Fixed up the bibliography to look nicer and got rid of some errors therein. Also changed it so
the bibliography would contain everything in the bibtex file, not just those books that are
explicitly cited in the paper (I wanted to ensure Cutland shows up in the references since his
book was absolutely instrumental, even though I don't explicitly cite him anywhere).