debugMinor
Given a total recursive function, can you always compute its fixed-point?
Viewed 0 times
totalcanyoucomputepointalwaysfunctionrecursiveitsfixed
Problem
We know from Kleene's recursion theorem that if $f$ is total recursive, there must be an integer $n$ for which $\varphi_n=\varphi_{f(n)}$. My question is: for every $f$ total recursive, is there a computable (total) procedure that computes such a point?
ie: $\exists g.\forall f.\varphi_{g(n)}=\varphi_{f(g(n))}$.
ie: $\exists g.\forall f.\varphi_{g(n)}=\varphi_{f(g(n))}$.
Solution
The proof of the recursion theorem is constructive: it gives you an algorithm to compute $n$ from $f$. See for example these notes of Rebecca Weber.
Context
StackExchange Computer Science Q#104780, answer score: 6
Revisions (0)
No revisions yet.