I've read Gödel's Proof by Nagel & Newman and I feel confused about there philosophical remarks on impossibility of computer to emulate human's mind. I don't understand how does that really follows from Gödel theorems. Of course I can see direct similarities of tools Gödel used in his proof with ideas which forms fundament of todays computer science: reccurent functions, encoding and calculation of formulas as strings, etc. But what are the real conclusions of Godel's incompletness theorem in terms of computability? Can one really say that since the Theorem was prooved we know now that something can be calculated and something not?

  • 3
    $\begingroup$ This is almost certainly out of scope and not a question that's appropriate for this kind of site. Thoughts? $\endgroup$ – Suresh Venkat May 18 '11 at 14:23
  • 4
    $\begingroup$ 1. question is open ended discussion 2. not clear what you're asking 3. relation between godels incompleteness and computability is not a research discussion - $\endgroup$ – Suresh Venkat May 18 '11 at 15:21
  • 2
    $\begingroup$ I agree Suresh, but it could possibly be modified into a good question by focusing on the question, "Is there a problem which is now known to be (or not to be) computable using Gödel's Theorem?" $\endgroup$ – bbejot May 18 '11 at 15:40
  • 2
    $\begingroup$ @bbejot: even that reformulation does not seem like a research level question to me. The connection between Godel's theorem and the Halting problem is very well explored, and often covered in undergraduate texts, or wikipedia: en.wikipedia.org/wiki/… and en.wikipedia.org/wiki/… $\endgroup$ – Artem Kaznatcheev May 18 '11 at 17:59
  • 1
    $\begingroup$ izhak: Published criticisms of Penrose's The Emperor's New Mind discuss such issues in detail. The reference section of en.wikipedia.org/wiki/… is your friend. $\endgroup$ – Vijay D May 19 '11 at 0:33

I wish I could add this as a comment instead but I don't have the privilege! A good paper related to this subject is "Forbidden Information" by Leonid Levin (tough to read but it's worth the pain :-))


Not the answer you're looking for? Browse other questions tagged or ask your own question.