A note on A.E. h-complex functions

摘要

Rabin and Blum proved the existence of 0, 1-valued recursive functions which are arbitrarily hard to compute. Their proof was partially constructive in that they effectively gave a program for a function that required computation time exceeding a given bound. However, their proof that the function required the specified time contained a non-constructive element; here we show that that element is essential.