# Thread: Kleene Normal Form Theorem

1. ## Kleene Normal Form Theorem

Prove that there is a computable relation $T(e,x,y)$ which holds if $y$ is the code number of a computation according to Turing program $P_e$ on input $x$ and that there is a computable partial function $U(y)$ which gives the output of the computation.

I could really use some help getting started on this one. Could I get a suggestion?

2. ## Re: Kleene Normal Form Theorem

Have you read the Wikipedia page? This is also discussed in "Computability and logic" by Boolos and Jeffrey, chapter 8. I have edition 3, where they show in detail how to convert a TM into a μ-recursive function. The most recent edition of the books seems to be 5, and one can view the relevant chapter on amazon.com.