If we have all these optimized programs for very specific tasks, what would be the antithesis of them?

I've asked a programmer friend of mine, and they thought a good answer had to do with multi-dimensional arrays and nested for-loops in graphics programming. I just want to see what other answers there are.

Essentially, as the title says, what is the hardest/slowest thing for a computer to do?

  • 2
    $\begingroup$ "Greatest" seems like a matter of opinion to me, so this question seems to be calling for opinion. See our help center. $\endgroup$
    – D.W.
    Sep 26 at 5:22
  • $\begingroup$ Do u mean hard to solve or can't be solved?if u mean can't then the term is non-computable or undecidable problems, meaning they can't be solved by computers no matter how Computing power u dedicate to them. The halting problem in the answer below is a good example, is there any algorithm that could 100% answers you if a running program is going to halt (end execution)or is stuck in an infinite loop & will keep running forever? It's true u can solve it for "some" programs by parsing their code and logically proves it will halts but not a decisive answer for any possible code $\endgroup$
    – ShAr
    Sep 26 at 6:02
  • $\begingroup$ Are you interested in problems that are hard for both computers and humans, or problems that are hard for computers, but not necessarily for humans? $\endgroup$
    – Discrete lizard
    Sep 26 at 12:17

I would say the halting problem, is the hardest - single most important problem in computer science.

The halting problem is an undecidable problem - meaning that no computer program can always successfully solve it and never get stuck in an infinite loop.

An important implication of the halting problem, is Rice's theorem, which can prove that some practically useful programs do not exist. For example, one cannot write a perfect anti-virus program that always managed to decide whether another given executable is malicious or not.

There are a lot of other interesting and potentially useful problems that we can't solve because of this, so I would say this is one of the most important results in the computer science computability field of study.


A computer doesn't have trouble doing anything; it does precisely what it's programmed to do. It is efficient in doing a task if and only if we come up with an efficient algorithm for it.

In that regards, we have a whole hierarchy of less and more efficient such tasks. On the bottom of the hierarchy is the problems where the machine just finishes after a couple of steps. Then there are an infinite hierarchy of problems solvable in logarithmic and polynomial time, followed by an infinite hierarchy of problems only solvable in exponential time followed by an infinite hierarchy of problems only solvable in super-exponential time (and so it goes) until you reach the limit of algorithms.

Then you get to the tasks for which there provably cannot exist any algorithm whatsoever for solving them, which is an infinite hierarchy of more and more undecidable problems. And we still have only seen a tiny tiny tiny part of all problems that exists. The majority of the problems lie above all these hierarchies.

Summing up, computers run algorithms. Some tasks have efficient algorithms, and some don't (and for some, we don't know).


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.