HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

Given a total recursive function, can you always compute its fixed-point?

Submitted by: @import:stackexchange-cs··
0
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))}$.

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.