Artificial intelligence and undecidibility Can artificial intelligence solve problems like Post correspondence problem?
No.  The Post correspondence problem is undecidable.  That means that no computer program can solve it (in all cases).  "Artificial intelligence" is just a computer program. Actually, "artificial intelligence" is a name for something that we're not even sure how to do with a computer program; but even if we knew how to achieve it, it would still be a computer program.  Artificial intelligence isn't magic -- anything that can be done is still constrained by the laws of physics and mathematics.