Fog Creek Software
Discussion Board




Computability

Okay, we know we can't compute everything because of the halting problem, and we know that we can't prove everything because of Gödel.  This is probably a silly question from a novice, but it seems the stuff we know we can't compute or prove is pretty esoteric.  Are there examples or practical questions we know we can't find an answer to?

anon
Thursday, August 05, 2004

I don't know if they found the answer to Fermat's last theorem.

Alardo
Thursday, August 05, 2004

Yep - http://www.pbs.org/wgbh/nova/proof/

Greg Hurlman
Thursday, August 05, 2004

Fermat's last theorem has been solved.

Practical NP-complete problems exist, predicting the weather being a good example.  Better algorithms and faster hardware push back the horizon, but the problems remain. Manufacturing scheduling, spare parts optimization,  nuclear explosion simulation ...

Google "parallel Fortran" for more.

trollop
Thursday, August 05, 2004

>> "Manufacturing scheduling, spare parts optimization,  nuclear explosion simulation ..."

Thanks, trollop.  But I think these are examples of *hard* problems.  You *can* theoretically solve these problems even though it might take ten times longer than the Universe has existed to do so.  I'm interested in a practical example of a problem like the halting problem, that couldn't be solved even if you have the fastest supercomputer and all of eternity.

anon
Thursday, August 05, 2004

Yes this did find an answer to that, I can't remember the exact details, but there was a proven logical equivanence to another problem that could be solved.

From memory, I seem to recall that this solvable problem was something to do with hyper n-dimensional doughnuts.

Tim H
Thursday, August 05, 2004

I was taught that it is impossible to write a general computer program that can look at another computer program a say what it does.

Tim H
Thursday, August 05, 2004

NP-completeness is not the same as Gödel's provability!

NP-complete problems can be proven, often surprisingly simple (once a solution has been found). However, finding that solution is another matter. Even the algorithm is often very simple, it is just the the order of the algorithm that makes finding the solution impossible in practical terms.

Gödels theorem deals with (natural) number theory or systems of equal complexity. His theorem is about inifinite sets, rather than finite sets as used in discussions for NP-completeness.

Karel Thönissen (www.garabit.nl)
Thursday, August 05, 2004

I think the Travelling Salesman problem is a classic case here.

It should be easy, but it is not.

Apologies if this has been "solved" and I am not aware of it.

Nemesis
Thursday, August 05, 2004

The halting problem itself is not esoteric. A program to determine whether another program completes in finite time is a very useful program!  Hard realtime system, anyone?

Such analysis programs can be written for a class of object programs in a restricted language. However, the point of the halting-routine is that it is not powerful enough to make a correct analysis of every program: it fails on its own source code.

Karel Thönissen (www.garabit.nl)
Thursday, August 05, 2004

There is a big misunderstanding about Godel here. Godel is about an inherent inability to prove, logically, if a statement is true. Problems like the TSP are just about finding a method of calculating the answer that can be done in a reasonable time.

David Clayworth
Thursday, August 05, 2004

Yes there's also the problem of deciding whether or not a given string belongs to a given recursively enumerable language.

This incompleteness/unprovability business in math/CS is a lot like the issue of the speed of light in physics.  The more power you give to an analytical system, the closer it gets to being able to run Windows (but you can't ever get beyond that).

Do you know about Chaitin?

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/

Kalani
Thursday, August 05, 2004

You could argue that problems relating to logic or computation are all going to be abstract to some extent. I'd say both Godel's theorem and the halting problem have practical consequences.

If you mean something like "are there specific mathematical statements we know can't be proved" then the answer is yes, but almost by definition, they are abstract.

There are also things like weather prediction (as I think someone mentioned) where even infinite computing power wouldn't really help you because of the predictions of chaos theory. Or practical questions where the answer depends on some quantum mechanical process - computation and logic won't help - the answer is unpredictable in principle.

Chaitin's meta math book is very interesting btw.

Matt Freestone
Thursday, August 05, 2004

Yeah most (all?) of the Goedel examples are pretty contrived. This might not be quite what you're looking for, but is a good example - a problem which can't be solved using the standard axioms for set theory:

Is there a set with cardinality strictly greater than that of the natural numbers, but strictly less than that of the real numbers?

(ie is the continuum hypothesis true). The solution is just to add this statement or it's negation as a new axiom - it's provably independant from the rest.
There are more examples where that one came from, if you look at Large Cardinal axioms.

Model Theory is the area of maths you should be looking into if this sort of thing interests you - there are a lot of results concerning what can and cannot be proved in different strengths of mathematical system, some of which can be quite surprising and deep.

http://mathworld.wolfram.com/NaturalIndependencePhenomenon.html

would be a good start, also appendix 2 here about the ramsey's theorem, especially the extended finite version:

http://www.ltn.lv/~podnieks/gta.html

A suitable generalisation of a simply-stated mathematical theorem about finite graphs which cannot be proven in first-order arithmetic (but can if you work in ZFC).

If that went way over your head then no worries, I can't pretend to understand many of the proofs myself. The results are interesting though.

Matt
Thursday, August 05, 2004

There are many simple problems that are trivially incomputable, such as the inverse of any many-to-one function.

E.g. Write a program that given |x| outputs x.

Devil's Advocate
Thursday, August 05, 2004

Oh and on the computability front - there are lots of generalisations you can get from the halting problem - eg (i think) Rice's theorem says that pretty much any non-trivial property of a computer program cannot be computed on the set of all programs. Although still a bit contrived I admit.

Also try http://mathworld.wolfram.com/GoodsteinsTheorem.html - perhaps a simpler/better example than the ramsey theorem, of a simply-stated mathematical problem which can't be proven using first-order arithmetic (Peano Artihmetic, which you've probably come across, is the standard first-order axiomatisation of arithmetic with zero, a successor function and the inductive principle)

Matt
Thursday, August 05, 2004

Um... If you're working with the definitions of 'function' and 'inverse' used in computability theory, then there /is no/ inverse of a 'many-to-one' function. Hence it doesn't make sense to talk about whether or not such a (non-existant) inverse is computable.

Matt
Thursday, August 05, 2004

>> the closer it gets to being able to run Windows
Oh, that is good... :):)

Alex
Thursday, August 05, 2004

Yes, look up the contiuum hypothesis.

Mathie
Thursday, August 05, 2004

Stuff like uncomputability comes up every single day in programming - its why we can't make perfect automated test benches. 

danielsn
Thursday, August 05, 2004

Devil's advocate, what you are saying is:

A number has been subtracted from itself and resulted in this value:

0

Please deduce the original number.

(You can't, because information was lost, just as with |x|).

Alex
Thursday, August 05, 2004

Well, the original poster was looking for "practical questions we know we can't find an answer to".

I suppose we can argue the practicality, but it is a simply stated problem which is clearly not computable due to its indeterminacy.

It's a trivial example, but that seems to be what the OP is looking for.

Devil's Advocate
Thursday, August 05, 2004

Alex, but the "pseudo inverse" of |x| is {x, -x} (a finite set) while the "pseudo inverse" of (- x x) is Z (an infinite set).

Kalani
Thursday, August 05, 2004

The Busy Beaver problem may or may not map onto anything really practical, but it's the classic example of a function known not to be Turing-computable.

Then again... were we supposed to try to figure out what it would mean to
throw quantum computing into this mixture?

Thomas E. Kammeyer
Thursday, August 05, 2004

OK,
here's a few more, seeing we're not bound by practical considerations or fell asleep in class:

Is there a God?  (sorry Joel).

What is the sound of one hand flapping?

Does she/he love me?

Emptiness-of-complement problem for semiextended regular expresssions. (google for some light reading).

trollop
Thursday, August 05, 2004

The sound of one hand Flapping can be computed provided we have enough information about the size and material of the hand and the medium it's flapping in and the position of the listener.

It's the sound of one hand Clapping that is the Zen paradox.

Stephen Jones
Friday, August 06, 2004

*  Recent Topics

*  Fog Creek Home