HOMOLOGY OF GROUPS AND THIRD BUSY BEAVER FUNCTION

作者：Michel Pascal^*

来源：International Journal of Algebra and Computation, 2010, 20(6): 769-791.

DOI：10.1142/S0218196710005868

• Homology of groups
• busy beaver
• noncomputability
• big numbers

In 2007, Nabutovsky and Weinberger provided a solution to a long-standing problem: to find naturally defined functions that grow faster than any function with Turing degree of unsolvability 0 '. They considered the functions b(k) such that, for a natural integer N, b(k)(N) is the rank of the kth homology group H(k)(G) of maximum finite rank, among the finitely presented groups G with presentation length <= N. They proved that, for k >= 3, function b(k) grows as the third busy beaver function, and so grows faster than any function with degree of unsolvability 0 ''.
Can more be said about these functions b(k)? We give some results on the function b(2), we study the challenge of computing H(k)(G) for a finitely presented group G, and we compute b(k)(N) for small values of N.

• 出版日期2010-9