4
$\begingroup$

Is there exists a recursively enumerable set of computable total fast-growing functions $(\mathbb N \rightarrow \mathbb N)$ such, that this set has no upper boundary in the set of all such functions (up to a dominance relation)?

Clearly, you can't enumerate some set of such functions in increasing order since diagonalization gives computable upper boundary, but what if we enumerate functions in some unknown order?

$\endgroup$

1 Answer 1

4
$\begingroup$

Let $\varphi_a $ be the $ a $ th partial computable function in a standard way.

Given a recursively enumerable set $ W $, let $ f (n) $ be the maximum of $\varphi_a (b)$ over $ b\le n $ and $ a $ among the first $ n $ many numbers enumerated into $ W $. Assuming each $\varphi_a $ is total, this $ f $ is computable.

$\endgroup$
1
  • $\begingroup$ Yea, fairly easy $\endgroup$
    – Dan
    Commented Sep 28, 2014 at 14:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .