Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

There are effectively computable numerical functions which aren’t prim

  1. Feb 11, 2014 #1
    This is from Peter Smith's Gödel without tears.

    I don't agree with this.
    If it appears in the list of p.r. functions then it is p.r. I don't see why he thinks that if x is in the list of p.r. functions then it is not p.r.


    Attached Files:

  2. jcsd
  3. Feb 11, 2014 #2


    User Avatar
    Gold Member

    This is just a standard diagonal argument. It works by saying "Assuming δ were on the list we reach a contradiction. The only other possibility being δ not on the list the desired conclusion follows." For whatever reason this type of argument seems to give some people trouble. You might be one of those people.

    Edit: If you are one of those people, then my advice is first use the forum software to search for threads about the Cantor diagonalization argument, because it has been discussed at length on the forum before. After reading those threads, if you still have problems, then come back and ask specific questions.
    Last edited: Feb 11, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook