3
$\begingroup$

I am looking for a problem that can not be solved by computer but can be solved by human while computer can verify if the answer is correct or not. In fact what is the question in my head is that is there a way to clearly show the smartness in human brain compared to huge computation power of the processors.

$\endgroup$
2
$\begingroup$

We know that there are problems (like the halting problem) that absolutely cannot be solved by a computer because there is no algorithmic solution. But a human cannot solve those problems either.

We also know that there are problems that humans can solve, but which we do not know how to solve with a computer with our current state of knowledge and technology. Problems in image processing ("is there a teddy bear in this picture ?") or natural language processing ("do these two English sentences have equivalent meanings ?") fall into this category. The difficulty here is showing that any of these problems absolutely cannot ever be solved by a computer, given a clever enough program and enough processing power and time - it is not at all clear how you could establish that.

We do not know of any problem that can be solved by a human and absolutely cannot ever be solved by a computer, no matter how powerful.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very interesting. Can you please bring some more examples of the problems without algorithmic solutions? I would be more thankful if you provide some references or courses on this matter. I am working on developing a challenge and these examples are very inspiring to me. $\endgroup$ – Alkhin Dec 7 '19 at 5:04
1
$\begingroup$

This is indeed, an open problem. The Church-Turing thesis, in its most popular conception, states that anything that can be computed by a human with a pen and paper can be computed by a Turing Machine. We have not yet been able to prove or disprove this thesis, therefore no one can tell you such a problem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The Church-Turing thesis is actually unprovable. One might be able to come up with a "smarter" computational model than a Turing machine but there is no way of showing that a Turing machine is the end of a line. $\endgroup$ – ttnick Oct 29 '19 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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