2
$\begingroup$

Like the title says, I am looking for a function f from N to N such that f(f(x)) is computable but f(f(f(x))) is not. I think it should exist, because i dont see how knowing how to calculate f(f(x)) would help you calculate f(f(f(x)), but I haven't been able to create a counterexample.

I came up with this question after solving a much easier one, finding a not computable function f(x) such that f(f(x)) is computable. One possible solution is using the fact that you can codify a pair of numbers as a single number, and then define f(x,y) = (HALT y, 0). Then, f(x) is not computable because it codifies HALT, but f(f(x)) = (0,0) so is certainly computable.

However, that previous solution relies on deleting the uncomputable information by the second iteration, and something like that wouldn't solve my new problem because f(f(f(x))) would be computable.

Improve this question
$\endgroup$
7
  • $\begingroup$ Are there functions $f$ that are not computable such that $f\circ f=\mathrm{id}$? $\endgroup$
    – Kenta Suzuki
    Commented Feb 19, 2023 at 18:07
  • $\begingroup$ That was exactly the counterexample that I sought to create, but I haven't been able to figure out how. $\endgroup$
    – manu fava
    Commented Feb 19, 2023 at 18:10
  • 9
    $\begingroup$ Some googling turns up slide 18 here: frontiersinai.com/turingfiles/March/GillesDowek1.pdf Take an undecidable set $U$ (say, encoding the halting problem), and swap $2n$ and $2n+1$ if $n \in U$, and keep them the same if $n \notin U$ $\endgroup$
    – Kevin Casto
    Commented Feb 19, 2023 at 18:18
  • $\begingroup$ Thank you, that settles it. I didn't realize it was so simple, i keep trying to make an involution that codified the busy beaver. $\endgroup$
    – manu fava
    Commented Feb 19, 2023 at 18:27
  • $\begingroup$ Extending this question, is there a characterization of the sets $S \subseteq \mathbb{N}$ such that there exist a function $f$ with $f^m$ computable if and only if $m \in S$? Kevin Casto's comment shows that $S = 2\mathbb{N}$ is possible. $\endgroup$
    – Mark Wildon
    Commented Feb 19, 2023 at 18:37

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .