It has been proved that a Turing Machine cannot solve the halting problem, but is it (being able to solve the halting problem) really necessary for implementing Strong AI ?

We human can understand the halting problem, and tell if a program will halt or not; but that is not our 'program language'. For example, we don't know how long we can live, precisely; we can't determine how much time we will spend for daydreaming while we are daydreaming.

From this point of view, it seems that we human cannot solve our own 'halting problem', either. So, is being able to solve the halting problem really necessary for implementing Strong AI? I don't think so. What do you think?


closed as not a real question by Neel Krishnaswami, Aaron Roth, Andrej Bauer, Jeffε, Kaveh Nov 20 '12 at 16:55

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ If "Strong AI" means coding a Turing Machine to simulate -you-, then certainly if this is possible, you cannot solve the halting problem (since you are a Turing Machine). I think at least among computer scientists, this would be the majority view of the world: that (a), strong AI is possible, and that therefore (b), humans are no better than Turing machines at solving undecidable problems. $\endgroup$ – Aaron Roth Nov 20 '12 at 14:06
  • 1
    $\begingroup$ This question cannot be answered, even in principle, without a crisp mathematical definition of "Strong AI". $\endgroup$ – Jeffε Nov 20 '12 at 15:50
  • $\begingroup$ Please check our FAQ. cstheory is not a discussion forum for soliciting opinions, it's a Q&A site with a specific scope explained in the FAQ. Closing the post as "not a real question". $\endgroup$ – Kaveh Nov 20 '12 at 17:00

This is a very soft question and AI is not my field, but I wanted to clarify about the halting problem.

It is not generally accepted that humans can tell if a program will halt. This is also more of a question of philosophy than of CS Theory - you might check out this post, and you may find discussions more to your liking on other Stackexchanges (I'm guessing that's the reason for the unexplained down-vote). If you're not convinced that it is questionable whether humans can solve the halting problem, I would recommend reading up on Gödel's incompleteness theorem, which is the more mathematical side of the halting problem, and poses questions to me that I don't believe I can answer.

  • $\begingroup$ Most humans I know cannot tell if a computer program will halt, and most are aware that they themselves will ;) $\endgroup$ – Lucas Nov 22 '12 at 16:20

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