Technology

Computers Might Never Be Able To Solve These Three Problems

Excited for today's eclipse? Visit our Eclipse 2017 page to explore the science, history, and myths of the event. The Curiosity team will be viewing the eclipse alongside NASA in Carbondale, Illinois. Follow us on Facebook for live videos, trivia, and interviews today!

In computer science, an undecidable problem is one that requires a yes or no answer, but is impossible for any known computer to reliably solve. Three of these problems are the halting problem, Kolmogorov complexity, and the Wang tile problem. The halting problem refers to whether a computer can determine if a program will ever finish running, whereas Kolmogorov complexity deals with compression, and the impossibility of perfectly compressing any given file. Wang tiles are square tiles with a color on each side. Infinitely placing them next to each other so that the colors of each side match the colors on the adjacent squares is called "tiling the plane," and there is currently no computer that can predict whether a given set of Wang tiles will tile the plane. Dive deeper into these computer conundrums in the video below.

3 Problems Computers Will Never Solve

Computers can't do everything. Here are three problems that they'll never conquer.

Share the knowledge!

Key Facts In This Video

  1. The halting problems states that no computer can always determine if a program will continue to run or eventually stop. 00:32

  2. Thus far, no program can perfectly compress any given file due to Kolmogorov complexity. 01:23

  3. There can be no method that can take any given set of Wang tiles and tell you whether or not it will tile the plane. 02:05

How Cold War Computers Failed At Russian

Don't think programming computers to translate would be controversial? Think again.

The Philosophy Of Artificial Intelligence

Computers may not be able to solve some problems, but they are on the cusp of having lifelike AI. Explore the ethics of this new frontier.

If you liked this you'll love our podcast! Check it out on iTunes, Stitcher, Google Play Music, SoundCloud, search 'curiosity' on your favorite podcast app or add the RSS Feed URL.

Advertisement