Results 1 to 2 of 2

Math Help - Kleene Normal Form Theorem

  1. #1
    Newbie
    Joined
    Jan 2012
    Posts
    4

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. kleene-closure
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 6th 2011, 11:23 AM
  2. Replies: 1
    Last Post: September 26th 2011, 11:53 AM
  3. Disjunctive Normal Form
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2009, 07:03 PM
  4. Kleene star 2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 19th 2009, 01:09 PM
  5. Kleene Star
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2009, 01:43 PM

Search Tags


/mathhelpforum @mathhelpforum