<p>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 :-))  </p>

CC BY-SA 3.0
2011-05-18T15:26:03.687Z
2011-05-18T15:26:03.687Z
Al-Alimi
<p>I've read <a href="http://rads.stackoverflow.com/amzn/click/0814758169" rel="nofollow">Gödel's Proof</a> by Nagel &amp; 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?</p>

CC BY-SA 3.0
2011-05-18T14:23:59.840Z
This is almost certainly out of scope and not a question that's appropriate for this kind of site. Thoughts?
Suresh Venkat
CC BY-SA 3.0
2011-05-18T14:49:08.220Z
I saw references to Gödel incompletness theorems in several computer science courses, [example](http://www.scottaaronson.com/democritus/lec3.html). So why is the question on the link between Gödel's theorem and computer science is out of scope?..
lithuak
CC BY-SA 3.0
2011-05-18T15:21:53.677Z
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 -
Suresh Venkat
CC BY-SA 3.0
2011-05-18T15:40:45.990Z
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?"
bbejot
CC BY-SA 3.0
2011-05-18T17:59:16.880Z
@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:
http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem 
and 
http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorem#Relationship_with_computability
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-19T00:31:54.363Z
There last two sentences post questions. The first, vague, the second, naive. Maybe the first question could be refined, but the second makes me think a research-level answer is out of scope.
Vijay D
CC BY-SA 3.0
2011-05-19T00:33:21.727Z
izhak: Published criticisms of Penrose's The Emperor's New Mind discuss such issues in detail. The reference section of http://en.wikipedia.org/wiki/Shadows_of_the_Mind:_A_Search_for_the_Missing_Science_of_Consciousness  is your friend.
Vijay D
CC BY-SA 3.0
2011-05-19T06:32:45.630Z
I agree with others. This does not look like a rigorous question in TCS since you are talking about "mind" and "philosophy". Philosophers usually have some other not explicitly stated assumptions when write about these things, and don't have rigorous mathematical proofs. I would suggest [Gödel's theorem: an incomplete guide to its use and abuse](http://books.google.com/books?id=71pK8Zz9Dd8C) by Torkel Franzén if you are interested. Also the check the references at [SEP](http://plato.stanford.edu/entries/goedel/)'s article.
Kaveh
<computability>
What meaning (value) does Gödel's Incompleteness Theorems have for computation theory?
lithuak
# What meaning (value) does Gödel's Incompleteness Theorems have for computation theory?

(Asked by: username_0 on 2011-05-18)

I've read [Gödel's Proof](http://rads.stackoverflow.com/amzn/click/0814758169) 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?

**Tags:** computability

> **Comments:**
> **username_1**: This is almost certainly out of scope and not a question that's appropriate for this kind of site. Thoughts?  
> **username_0**: I saw references to Gödel incompletness theorems in several computer science courses, [example](http://www.scottaaronson.com/democritus/lec3.html). So why is the question on the link between Gödel's theorem and computer science is out of scope?..  
> **username_1**: 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 -  
> **username_2**: 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?"  
> **username_3**: @username_2: 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: http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem  and  http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorem#Relationship_with_computability  
> **username_4**: There last two sentences post questions. The first, vague, the second, naive. Maybe the first question could be refined, but the second makes me think a research-level answer is out of scope.  
> **username_4**: izhak: Published criticisms of Penrose's The Emperor's New Mind discuss such issues in detail. The reference section of http://en.wikipedia.org/wiki/Shadows_of_the_Mind:_A_Search_for_the_Missing_Science_of_Consciousness  is your friend.  
> **username_5**: I agree with others. This does not look like a rigorous question in TCS since you are talking about "mind" and "philosophy". Philosophers usually have some other not explicitly stated assumptions when write about these things, and don't have rigorous mathematical proofs. I would suggest [Gödel's theorem: an incomplete guide to its use and abuse](http://books.google.com/books?id=71pK8Zz9Dd8C) by Torkel Franzén if you are interested. Also the check the references at [SEP](http://plato.stanford.edu/entries/goedel/)'s article.  

---

## 1 answers

### Answer by username_6 on 2011-05-18. Score: 3

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 :-))


---

