Skip to main content
Pietro's user avatar
Pietro's user avatar
Pietro's user avatar
Pietro
Unregistered
  • Member for 12 years, 9 months
awarded
awarded
comment
Kleene's fixed point theorem on recursive subsets of computable functions
The set $E$ contains now all the polynomial-time functions. The fixed-point free mapping $\varphi(k)$ can be constructed as: - recover the code of machine $T_k$ - change the halting conditions: if $T_k(x)$ is accepted, the new code rejects it, and conversely. Actually, there is a problem here for the case in which the machine does not halt. To fix it, it is sufficient to add in the enumeration two copies of the same UTM: one rejects when the time expires and the other one accepts. - return the index of the new machine It is a very "TM machine-dependent" example but it seems to work.
comment
Kleene's fixed point theorem on recursive subsets of computable functions
This simple example answer the question. In the meanwhile, I also found a more complex example, which probably implies that the constraints $f$ needs to satisfy are quite strong. My idea is the following: consider the set of polynomial-time functions obtained through $f$ in the following way. Given a pair (i,j) $f$ returns the index of a univ TM that simulates $T_i(x)$ up to $h_j(|x|)=|x|^j+ j$ steps (0 if $T_i(x)$ does not halt). We need to recode $f$ so that it takes a single integer, but that's easy obtainable by using some bijection from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$.
comment
Kleene's fixed point theorem on recursive subsets of computable functions
Thanks for pointing out this: E does not need to be recursive.
awarded
Loading…