Non-Computable Problems: Halting problem and others

If you have not studied algorithm complexity analysis this might seem a little strange. There is actually problems that the computer can't solve no matter what happens. To make it a little easier to understand, we usually think that there is nothing a human can't do but can a human fly! We'll it's not possible. You can say the same thing about non-computable problems, it's just problems that the computer can't solve.
Halting Problem:
One example, that always pops to one's mind when asked about non computable problems, is the Halting Problem. This problem is fairly simple "Given a program and an input to the program, find whether the program will run indefinitely or not when processing that input" in other words find if a certain input will cause a program to enter an infinite loop. And the computer can do that!
There is a fairly complicated proof for that problem and you can find it here .
Other Problems:
What made me mention this class of problems is that we've been asked to find other problems that are not computable which seemed kind of interesting so I searched for a while and found some,
The Totality problem: this problem is just a generalization of the halting problem and it states "Given a program, find if this program will terminate on all its inputs or not". And it's fairly simple to proof non computable given that the halting problem is non computable too.
Also there is The Equivalence Problem which states "Given two programs find whether the two programs solves the same problems or not".
You can find more of those problems and there proofs here.
I hope that this post got you thinking about what the computer can really do!

Comments

Post a Comment

Popular posts from this blog

Sharing the Network: From Circuit Switching to Packet Switching (The Hitchhiker's Guide to Computer Networks)

Prelude ... From Circuit Switching to Packet Switching The simplest approach for two people to communicate over long distances is to connect them through a dedicate physical wire. However, how would we scale that model to a million people that individually want to be able to communicate with everyone else? One approach is to extend wires between all pairs of users, requiring hundreds of billions of wires.  This is definitely not a good way to design a network. So what's wrong with that design? First, it is unlikely that every single person in that network will want to talk to everyone else at the same time. This means that we can use fewer wires. Second, not all connections are created equal. Longer wires cost a lot more money than short ones. Our design should have short wires whenever possible. Also it will be nice if the cost of extending long wires is shared between multiple users at the same time. Let's revisit our connection strategy. Rather than extending wires betwe...
Read more

Attaching a WiFi Dongle to an AR Drone 2.0 (a.k.a. Compiling Drivers for ARM Based Devices)

Correction (4/24/2014): for your driver to work the AR Drone 2.0 you have to compile the kernel version provided by Parrot which can be found here https://devzone.parrot.com/projects/show/oss-ardrone2 One of the down sides of "out of the box" AR Drone 2.0 is that you can't control multiple drones from the same machine. Another down side is that you can't attach USB devices except flash memories and some other predefined devices due to the limited nature of the busybox deployed on the drone. To over come the first down side without manipulating the WiFi configurations of the built-in WiFi card (i.e. you don't want to mess up your new drone), you will need to overcome the second problem (i.e. install a WiFi dongle and its driver manually). In this tutorial, I try to walk you through the steps to do just that. I assume that you are working a Linux machine (seriously we are not going to compile drivers on Windows). Ubuntu is preferable ! Because the Drone has a...
Read more

Video on Demand: Part 1 (The Hitchhiker's Guide to Computer Networks)

Image
Data from the 2019 Global Internet Phenomena Report Video is the dominant type of traffic on the Internet. In 2019, video on demand constituted 60% of the total global Internet traffic. The image to the right shows the huge gap between the bandwidth demand of video streaming and the second highest application which is web traffic (think email, blogs, and news). This means that if you are in the computer networks business, you are pretty much in the business of video delivery. So the biggest question here, what is the best way to deliver video?  The "best" in this context can mean a couple of different things. It can mean delivering the best quality video for the user. Video quality does not only refer to whether a video is in HD or UHD but also whether it freezes and hangs or not. The "best" way to deliver video can also mean the most cost efficient way. If we can save 1% of the cost of delivering all videos on the Internet, we can save tens of millions of dollars i...
Read more