Which programs can and can't exist?

[chrstrbrts]

Hello,

Is it possible to come up with an idea for a program that can't be implemented?

Maybe another way to ask the question is: what can't computers do?

Some of the software that is released nowadays seems super advanced, pattern recognition, AI, etc. I begin to think that you can program a computer to do anything.

I'm just wondering where the limitations lay. In hardware? In software?

Is it possible to break any program down to "programmatic atoms" and analyze them to see whether or not they can be implemented on modern hardware?

Thanks.

 

[Ken g6]

It sounds like you're asking about computability - whether or not a problem can be solved by a computer. A problem which is not computable is called undecidable. There are many undecidable problems - I believe it was proved that there are infinitely many. One famously undecidable problem is the halting problem.

On the other hand, just because a problem is "undecidable" doesn't mean that there don't exist special cases which are decidable. In many cases a program could exist that says "yes" sometimes, "no" some other times, and "I don't know" most of the time.

The next step down from undecidable problems are called "hard problems". Exact solutions are known to exist for hard problems, and they can be computed. But for many medium-to-large hard problems it appears that computing an exact solution would take longer than there will exist power to do the computation in the universe. Or the storage required for the computation may be larger than the number of atoms in the universe.

Note that most "hard problems" have not been proven to require extreme amounts of time or space. It's possible that much better algorithms exist in some cases. In some cases, acceptable approximations can be computed much more easily. But in many cases the problem of whether a faster algorithm exists to solve a given problem may itself be undecidable.

Has your head exploded yet?

 

[Spungo]

Maybe another way to ask the question is: what can't computers do?

Computer generated numbers are never completely random, but one could argue that real life isn't completely random either, so it's not really an issue. Computers also have trouble with rounding errors. You can use 64 or 128 bits to approximate the square root of 2, but you'll never get it exactly.

I'm just wondering where the limitations lay. In hardware? In software?

It depends what you're trying to do. If you're trying to do something accurately, it's 99% hardware. A lot of the ideas of computation have been around for hundreds of years. The fourier transform is an example of this. A fourier transform is when one wave can be expressed as an infinite series of component waves. What does that mean? It means you can take a single wave, like a single-speaker representation of a song, and it can be broken down into all of its individual parts. It could have thousands of component waves, all of them at different frequencies and amplitudes. We've had the math to do this for more than 150 years, but it was useless information because we couldn't do anything with it. It might take months or years to do one of these calculations by hand. With proper hardware, we can finally do things we've been wanting to do for a very long time. With the right hardware, you can test thousands of light absorption frequencies at the same time. You can test thousands of sound frequencies at the same time. FT spectroscopy. A lot of medical technology is advancing due to hardware. We've had ideas floating around for a long time about how things could be tested, but there was no way to actually do the tests. The person is dead before the test results come back if it takes a year to calculate something accurately.

If you're just looking for rough approximations of things, a lot of great work has been done on the software side. This usually relates to graphics. You don't want the bank to estimate how much money is in your bank account, but it's acceptable to estimate what a video game looks like. A famous example is the fast inverse square root calculation. It's not completely accurate, but it's close enough.
http://en.wikipedia.org/wiki/Fast_inverse_square_root
Transform and lighting was another. Instead of drawing a 3D world as a bunch of overlapping layers, which is how real life works, first determine which things would be visible and only draw those things. In the world of graphics, putting your head in the sand really does make the world go away.
There are still some software optimizations out there to be discovered, but my guess is that most of them have already been found. We're mostly held back by hardware.

 

[Rakehellion]

All a computer can do is add numbers. If a problem can be expressed with numbers, it can be done on a computer.

Basically, a computer can do anything involving information. How quickly or accurately is another story.

 

[Rakehellion]

Computer generated numbers are never completely random

There are true random number generators that rely on the movement of atoms or other natural phoenomena, so computers can do that.

Computers also have trouble with rounding errors. You can use 64 or 128 bits to approximate the square root of 2, but you'll never get it exactly.

You can never get an irrational number "exactly" even on paper, but you can calculate it well beyond the precision required for your needs. Or you can just define the square root of 2 as a constant.

Also, there are specialized systems, both software and hardware environments, designed to handle complex numbers, so computers can do that too.

 

[KWiklund]

Like Ken mentioned, some of what you're asking has to do with the theory of computability, which has to do with whether certain types of problems are theoretically solvable. However, in the most general case, this assumes that your computer is essentially infinite, or you're indifferent as to how long it takes to get your answer.

For practical purposes, we are generally more interested in how long something is going to take. Returning to abstract mathematics, this can be quantified in terms of a problem's algorithmic complexity (Kolmogorv Complexity). However, this is unlikely to be a suitable measure for most purposes. More usefully, computer scientists will use 'Big O' notation (and some related measures) to represent the complexity of an algorithm. In this case, the complexity scales with some function of N, where N is the size of the problem being considered. Of course, this assumes that the problem is *theoretically* solvable, but depending on how the problem scales, it may not be practically solvable. One can also apply this scaling measure to space (memory) complexity as well.

Since numerical analysis has been briefly touched on already, another potentially useful measure is the convergence of an algorithm. In this case, the measures have to do with whether a method will converge to an answer over a given range, and how long it will take. The solutions to these kinds of problems are typically derived from a branch of mathematics called 'functional analysis'.

With respect to computability, I don't know of any good books dedicated to this subject that are suitable for the layman. Roger Penrose's "The Emperor's New Mind" comes closest, although in this case computability is one of many detours enroute to Penrose's actual (and somewhat dubious) thesis.

 

[DaveSimmons]

If you visit http://www.zombo.com you'll find that they can do anything. Anything at all.

More seriously, if you are willing to wait enough years there probably will not be anything that a computer can't do eventually.

Star Trek's "computer, do something or other" is now a semi-reality in Siri and Cortana.

Moore's Law on the doubling of transistors every 2 years (http://en.wikipedia.org/wiki/Moore's_law) has meant that the work that a computer can do has also roughly doubled. So every 10 years the power of a computer increases 2^5 = 32 times. 10 years later that number increase another 32-fold.

So 20 years from now, if you take the same number of computers (cloud servers, whatever) and have them run Siri or Cortana it can do 1,024 times as much work to understand your question and give you an answer.

That also means that some task that is impractical now because it takes to long, will become much easier when a computer can do it in 1 / 1,000 th of the time.

Also, some task may be unsolvable in theory for large amounts of data because it takes exponential time, but for smaller amounts it might be solvable, or an approximation might be "close enough" for real-world use.

 

[Markbnj]

If you visit http://www.zombo.com you'll find that they can do anything. Anything at all.

There's an archaeological find.

 

[brianmanahan]

a computer cant tell me what day i am going to die on

 

[Graze]

a computer cant tell me what day i am going to die on

It can, right before it kills you!

 

[brianmanahan]

It can, right before it kills you!

 

[IHateMyJob2004]

Once you enter industry you realize that many problems can only ever be approximately right.

 

[Fallen Kell]

You should read up on lambda calculus and the theory of computability.

 

[Merad]

There are true random number generators that rely on the movement of atoms or other natural phoenomena, so computers can do that.

IIRC physicists haven't decided for sure yet if the universe is actually deterministic or non-deterministic. If it's the former then "true" randomness would technically be impossible.

 

[disappoint]

There are true random number generators that rely on the movement of atoms or other natural phoenomena, so computers can do that.

One of the things I like about programming microcontrollers with built in ADCs (analog to digital converters) is the ability to seed a random number generator with the read of an analog input pin that is left "floating" not connected to anything, so it just sees noise. Don't know why they don't have that for PCs. Or do they?

        randomSeed(analogRead(0)*analogRead(1));
        randNumber = random(200);  //generate a random number from 0 to 199

Not saying it's perfectly random (if there even is such a thing) nor that it's even the best algorithm for generating random numbers. But it worked pretty well when I've used it so far. Granted I haven't graphed a distribution chart yet but if someone wants me to do so I can do that.