Groups and the Grzegorczyk Hierarchy
Right, so I’ve written about computable groups and the Grzegorczyk hierarchy previously. Now it’s time to join the two together so we can talk about the computational complexity of certain groups.
\(E_n\) computable groups
Let \(G\) be a group with an admissible index \(i\) and corresponding multiplication function \(m\). If \(i(G)\) is \(E_n\) decidable (( there is an \(E_n\) computable function which returns \(1\) on numbers which are indices of elements of \(G\), and \(0\) otherwise )) and \(m\) is \(E_n\) computable, then \(G\) is said to be \(E_n\) computable.
We can also add the characteristic function (( \(c_A\) such that \(c_A(x) = 1\) if \(x in A\), and \(0\) otherwise )) of a particular set to the primitive functions in the Grzegorczyk hierarchy to make some arguments about group computability easier. If we have \(c_A\), the characteristic function of the set \(A\), to our hierarchy, then we say a function (or group) is \(E_n(A)\) computable ((or “\(E_n\) computable relative to \(A\)”)) if it can be obtained from composition and bounded recursion on \(E_n\) functions and \(c_A\).