One of the consequences of computer science theory is that humans will likely never be completely replaceable by machines. They will certainly be (and already have been) exceeded by machines in many facets but there will always remain instances where machines will have no real advantage or even a disadvantage. My argument is not based on any sentiment that humans are not machines. In fact it is just the opposite. Given that we are nothing more than computers, there are some problems that are too hard to be solved by any machine so the best they can do is to come up with heuristic approaches and this may not be any different from what humans do. There will also be things that humans do that are not worth reproducing with machines.
Computational complexity theory is about understanding the difficulty of solving problems algorithmically. In particular, it avoids questions of implementation and focuses on asymptotic relationships between the size of the problem and the resources (i.e. time and memory) needed to solve the problem. The only problems computers can reasonably solve are those where the time and memory required only grow weakly with the size of the problem and weakly means being bounded by a polynomial in the size. The difficulty of problems are classified into complexity classes. P is the set of problems solvable in polynomial time. For example, matrix multiplication is in P. Naively it would take steps for an matrix but in fact it can be done even faster using Stassen’s algorithm. Machines are basically limited to solving problems in class P (If you want to be a stickler, they are limited to a related class called BPP , which includes problems in P).
Now, there is also a class of problems that can be verified in polynomial time called NP. An example is the traveling salesman decision problem, which asks if a tour that takes a salesman through a set of cities exactly once is shorter than some given distance. While a solution is easily verified there is no known algorithm in P for solving this problem. Another example of an NP problem is theorem proving. Anyone can verify a theorem in polynomial time but there are no known sure fire ways to generate theorems. The most famous problem in computer science is whether or not P is equal to NP. That is, if a problem can be verified in polynomial time, can it also be solved in general in polynomial time. Most computer scientists believe that P is not equal to NP and there are strong reasons for why. There is a famous result by Razborov and Rudich (A. A. Razborov and S. Rudich (1997). “Natural proofs”. Journal of Computer and System Sciences 55: 24–35), that essentially says that the reason why it is so hard to prove P is not NP is that P is not NP.
So if indeed P is not NP then there are a whole class of everyday problems like scheduling airlines or proving theorems that cannot be solved efficiently by computers. Solving such problems require ad hoc approximate methods, using analogies or plain luck, which are things that humans are good at. Even if we could design a super duper fast machine that thinks exactly like humans, there may still be problems that some person sitting in a cafe will solve that the machine will not. Being faster and bigger helps but it is not always enough. This is one reason why computers will not completely replace humans.
The second reason is that there are some things that humans engage in that are unique to humans like culture, art and humour. That is not to say that a machine couldn’t also do those things but it would have to learn to be human first and there is no algorithm to do that. The only way a machine could learn to be human would be to live as a human on human time and length scales. They would have to start as little things and grow bigger, have family and friends, go to school, eat food, smell flowers, watch bad movies, have their heart broken, drive a car, and so forth. These experiences form our priors from which spring our capabilities and creativity. Perhaps there are shortcuts for machines to learn to be human but I doubt that you could capture everything without going through it. There are some things that are hard to simulate like what it feels like to take a hot shower, the smell of an old house, or the pain of a shoulder dislocation. Capturing these aspects of life are intrinsic to something like comedy. My guess is that when we do start to have intelligent machines they will develop their own culture, art and humour, which we won’t comprehend. I can see humans being eventually supplanted by machines, but replaced, no.