Actually I'm wrong there, I was thinking of "primitive" recursive, I meant to say that if something is not recursive then it is (intuitively) not computable at all.
The other main problem is that the theorem of a set of sentences strenghtening Peano arithmetic (minus induction) is not recursive, this makes it impossible for a machine to recursively (i.e. within a boundary) decide whether a particular sentence is true [Church's Theorem].
This means that if a computer wanted to decide whether something was true or not in a particular formal system, then the computation to do so could last forever.
Slashdot Mirror
Actually I'm wrong there, I was thinking of "primitive" recursive, I meant to say that if something is not recursive then it is (intuitively) not computable at all.
The other main problem is that the theorem of a set of sentences strenghtening Peano arithmetic (minus induction) is not recursive, this makes it impossible for a machine to recursively (i.e. within a boundary) decide whether a particular sentence is true [Church's Theorem].
This means that if a computer wanted to decide whether something was true or not in a particular formal system, then the computation to do so could last forever.