Computable function with noncomputable set of fixed points

148 Views Asked by At

I'm looking for a computable function $f: \mathbb{N} \to \mathbb{N}$ such that the set of fixed points $\mathcal{F}_f = \{ e \in \mathbb{N} \mid f(e) \sim e \} = \{e \in \mathbb{N} \mid \forall x \in \mathbb{N}: \{f(e)\}(x) \simeq \{e\} (x) \}$ of $f$ is noncomputable. Here, $\{e\}(x)$ is the $e$-th partial computable function applied to $x$.

I tried finding $f$ such that $K \leq_m \mathcal{F}_f$, with $K= \{e \in \mathbb{N} \mid \{e\}(e) \downarrow \} $ the diagonal halting problem consisting of all $e \in \mathbb{N}$ such that the $e$-th partial computable function converges on input $e$. Thus I then need two computable functions $f,g: \mathbb{N} \to \mathbb{N}$ such that \begin{align*} \forall x \in \mathbb{N}: (x \in K) \Leftrightarrow (g(x) \in \mathcal{F}_f) \end{align*} i.e. \begin{align*} \forall x \in \mathbb{N}: (\{x\}(x) \downarrow) \Leftrightarrow (f(g(x)) \sim g(x)) \end{align*}

1

There are 1 best solutions below

0
On BEST ANSWER

You can do it with a constant function $f$. Let $f$ pick an index $e_0$ such that $\{ e : \{e\} \simeq \{e_0\}\,\}$ is uncomputable. (By Rice's theorem, that set is uncomputable for every $e_0$, so you can let $f$ be any constant function whatsoever, e.g. f(x) = 42 will work!)